These are two common searches used in graph theory; depth-first-search and breadth-first-search.
Type of Search
Both searches are uninformed searches, meaning they are:
- Brute-Force
- Exhaustive
- Blind (systematic without taking in other information)
Depth-First-Search (DFS)
A dfs works by following a path in a tree or graph until the very end. E.g. going from the top to the bottom of a tree in one go.
Classification
- Complete: No. It fails in in infinite-depth states, as it keeps going around and around in an infinite loop.
- Time-Complexity: $O(b^m)$ (terrible with a high m, but can be good in dense trees)
- Space-Complexity:$O(bm)$ = linear space
- Optimality: No, it can find suboptimal solutions first.
Breadth-First-Search (BFS)
A bfs works by traversing a tree or graph layer by layer. This creates multiple paths at once, allowing us to find the shortest path from a to b, rather than any path from a to b.
A bfs works by adding the first node to a queue, and then until the goal node is found the top node is popped up, examined and then all of its children pushed onto the end.
Classification
- Complete: Yes (if b is finite then the shallowest goal at d will be found)
- Time-Complexity: $O(b^{d+1})$
- Space-Complexity: $O(b^{d+1}) = b + b^2 + b3 + ... b^{d-1} + b^d$
- every node has to be kept in memory
- Optimality: Yes, if all actions have the same cost then it will find the first valid result (if not all actions have the same cost it may go down a seemingly good but actually bad path).
Comparison
Whilst a dfs can be implemented in two ways (with a stack or recursively), a bfs can only be sensibly implemented with a queue. Because of this stack/queue implementation, it is possible to swap from a dfs to a bfs simply by changing whether it is a stack or a queue that we use.
Generalised Implementation
function call: xfs (g, v, numVertices, &[p|q]ush); void xfs (Graph g, vertex v, int numVertices, void (*insert)(Staque, int)) { Staque s = createStaque(); insert(s,v); int *seen = calloc(numVertices, sizeof(int)); // int goal; int i; int visitedNum = 1; Edge e = createEdge(); while ((!isEmpty(s))) { v = pop(s); // If the vertex hasn't been seen we traverse it if (!seen[v]) { // Set the seen array to mark at what stage we visited this node seen[v] = visitedNum; visitedNum++; // For every node we check if there is an edge between [v][it] for (i = 0; i < numVertices; i++) { newEdge(e, v, i); // If there is, and it hasn't been seen yet // We insert it into the staque. if ((isEdge (g, e)) && (!seen[i])) { insert(s, i); } } } } printf ("Seen: "); for (i = 0; i < numVertices; i++) { printf ("%d ", seen[i]); } printf ("\n"); free(seen); deleteEdge(e); deleteStaque(s); }