Breadth and depth first search - part 1
Breadth and depth first search - part 2
As an extra, today I'm posting the C++ code of the breadth and depth first search algorithms. Take a look at part 1 and part 2 of this series.
When I had to hand in the work for the artificial intelligence discipline, the teacher wanted the code in C++ and I had already started developing the code in C#. The result was two versions of the same functions. The good part is that I could master both languages while developing such a code.
The code presented here uses an adjacency matrix to represent the links between the cities that are part of the Romania map shown bellow.
The following is the adjacency matrix:
// Adjacency matrix int map[21][21] = { /* A B C D E F G H I L M N O P R S T U V Z */ {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1}, // Arad {2,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0}, // Bucharest {3,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0}, // Craiova {4,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, // Dobreta {5,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, // Eforie {6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0}, // Fagaras {7,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, // Girgiu {8,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0}, // Hirsova {9,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0}, // Iasi {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0}, // Lugoj {1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Mehadia {2,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, // Neamt {3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1}, // Oradea {4,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}, // Pitesti {5,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0}, // Rimnicu Vilcea {6,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0}, // Sibiu {7,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Timisoara {8,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0}, // Urziceni {9,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0}, // Vaslui {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0} // Zerind };
Note that the first commented line represents the initial letter of each city's name. The mapping done with the adjacency matrix refers to these letters so that it's easier to understand. For example, getting the first entry of the adjacency matrix that refers to Arad: we have that Arad has paths that lead us to Sibiu, Timisoara and Zerind, thus we put a value of 1 on the columns that represent those cities, in this case, the columns beneath the letters S, T and Z. That's how the mapping is done. We put a value of 0 on the other columns to state that there is no path that leads us to those cities.
The code also has a hand made version of the stack and queue data structures. Each one of these structures is on its proper header file and are inline functions. See their implementations:
// Queue struct Queue { int start, end, tot; int info[max + 1]; }; void StartQueue(Queue *q) { q->tot = 0; q->start = 1; q->end = 0; } int IsQueueEmpty(Queue *q) { return q->tot == 0 ? 1 : 0; } int IsQueueFull(Queue *q) { return q->tot == max ? 1 : 0; } int Adc(int x) { return x == max ? 1 : x + 1; } void Enqueue(Queue *q, int x) { if(!IsQueueFull(q)) { q->end = Adc(q->end); q->info[q->end] = x; q->tot++; } } int Dequeue(Queue *q) { int ret = 0; if(!IsQueueEmpty(q)) { ret = q->info[q->start]; q->start = Adc(q->start); q->tot--; } return ret; } // End Queue |
// Stack struct Stack { int topo; int info[max + 1]; }; void StartStack(Stack *s) { s->topo = 0; } int IsStackEmpty(Stack *s) { return s->topo==0 ? 1 : 0; } int IsStackFull(Stack *s) { return s->topo == max ? 1 : 0; } void Push(Stack *s, int x) { if(!IsStackFull(s)) { s->topo++; s->info[s->topo] = x; } } int Pop(Stack *s) { int ret = 0; if(!IsStackEmpty(s)) { ret = s->info[s->topo]; s->topo--; } return ret; } // End Stack |
The Breadth First Search and Depth First Search functions are written in the same fashion of the C# code, but with little modifications.
void BreadthFirstSearch(int origin, int destination) { Queue *q = new Queue(); StartQueue(q); Enqueue(q, origin); while(IsQueueEmpty(q) == 0) { int u = Dequeue(q); if(u == destination) { printf("Path found."); break; } else { visited[u] = 1; for(int v = 1; v <= 20; v++) { if(map[u][v] != 0) { if(visited[v] == 0) { visited[v] = 1; parents[v] = u; if(v != destination) { if(!IsQueueFull(q)) { Enqueue(q, v); ShowPath(v); printf("\n"); } else { printf("Queue full."); break; } } else { ShowPath(v); return; } } } } } } }
void DepthFirstSearch(int origin, int destination) { Stack *s = new Stack(); StartStack(s); Push(s, origin); while(IsStackEmpty(s) == 0) { int u = Pop(s); if(u == destination) { printf("Path found."); break; } else { visited[u] = 1; for(int v = 1; v <= 20; v++) { if(map[u][v] != 0) { if(visited[v] == 0) { visited[v] = 1; parents[v] = u; if(v != destination) { if(!IsStackFull(s)) { Push(s, v); ShowPath(v); printf("\n"); } else { printf("Stack full."); break; } } else { ShowPath(v); return; } } } } } } }
To show the travelled paths there is a recursive function called ShowPath:
void ShowPath(int u) { if(parents[u] != 0) ShowPath(parents[u]); printf(" %s", cities[u]); }
You see, I had finalized the C# code and even sent the code to the teacher, but I received his reply stating that he wanted the code in C++. I complained with him! I told him about the easiness that modern programming languages as C# offers us when writing code.
Today, the data structures (queue and stack) "hand made" in this code are present in modern and optimized fashions inside standard libraries. We just need to instantiate an object from that specific class, in this case, stack or queue, and tada, we get lots of functions that do the hard work. But the point here is not the easiness. What the teacher wanted to force us to do was to comprehend how those data structures really function.
Nothing is better than writing the data structures by yourself. Although I didn't agree at the time, I thank him for forcing me to learn. Needless to say, these are basic data structures and are used in a great amount of code. You'll see these data structures during your entire developer life.
Visual Studio C++ Console Application
You can get the Microsoft Visual Studio Project and the app executable at:
http://leniel.googlepages.com/BreadthDepthFirstSearchCPlusPlus.zip
