COMP1927 - XFS (Uninformed Searching)

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.

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

}
```
page revision: 4, last edited: 15 Mar 2012 12:55