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);
 
}