Graph search

We often imagine looking for a book on a shelf or a file in a folder when we think about searching. However, what about searching in more complex areas like maps or social networks? This is where graph search algorithms come into play. In this topic, we'll dive into two fundamental graph search techniques: depth-first search (DFS) and breadth-first search (BFS). We'll see how these methods may help us traverse graphs and find paths between nodes. We'll also study simple code examples that illustrate how these search techniques work.

Graph to search

First, let's create a test unweighted graph. We will use it for the following:

• Depth-first search (DFS)

• Breadth-first search (BFS)

• Pathfinding

Below, you'll find the implementation of a graph using the Map type, where the key represents a node and the value represents its neighbors. We then execute the dfs(), bfs(), and pathFinding() algorithms, which are discussed further in this topic. All examples use pseudocode, which you can implement yourself in any programming language.

function main() {
    // Creating a Map data structure to represent a graph
    graph = new Map()
    // Put into the map a node as a key and its neighbors as a value
    graph.put("A", ["B", "C", "H"])
    graph.put("B", ["D", "E", "G"])  
    graph.put("C", ["F", "A"])      
    graph.put("D", ["B"])
    graph.put("E", ["F", "B"])
    graph.put("F", ["C", "E"])
    graph.put("G", ["B"])
    graph.put("H", ["A"])

    // Executing DFS, BFS, and path finding algorithms
    dfs(graph, "A")
    bfs(graph, "A")
    pathFinding(graph, "A", "F")
}

Here is a picture of that graph:

Depth-first search (DFS) vs breadth-first search (BFS)

Imagine you're exploring a labyrinth. You decide to follow a path at each intersection until it reaches a dead end, then you retrace your steps and choose a new path. This is the essence of depth-first search: it explores each branch as deeply as possible. When DFS reaches the bottom of the graph, it ascends back up to the neighbor of the first visited node and start exploring again, following a path as deeply as possible. DFS repeats this process until all nodes have been visited.

On the contrary, breadth-first search takes a different approach. It tries to explore the graph broadly, level by level. Starting at one point, you explore all paths one step away, then all paths two steps away, and so on. This method is excellent for finding the shortest path on a map or in networks where all moves have the same cost.

In the following table, you can examine the main differences between these two algorithms:

Time and memory complexity

Let's define the time and memory complexity for both algorithms considering a graph G=(V,E), where V represents the vertices and E represents the number of edges.

The time complexity is O(V + E). Every vertex is explored exactly once, and every edge is considered once for undirected graphs.
The memory complexity is O(V). In the worst case, you might need to hold all vertices in the queue (for BFS) or in the stack (for DFS). Also, be mindful of the recursive call stack in the case of a recursive implementation.

Depth-first search (DFS) implementation

Here's how it can be implemented using a stack and an iterative approach.

function dfs(graph, startNode) {
    visited = new Set()   // A set to keep track of visited nodes    
    stack = new Stack()   // A stack to hold nodes to visit
    stack.push(startNode) // Start by adding the initial node to the stack

    while (!stack.isEmpty()) {
        currentNode = stack.pop()
        if (!visited.contains(currentNode)) { // Check if currentNode was visited
            print(currentNode)                // Perform an action with currentNode
            visited.add(currentNode)          // Mark the currentNode as visited

            neighbours = graph.get(currentNode)
            for (neighbour in neighbours) {
                if (!visited.contains(neighbour)) {
                    stack.push(neighbour) // Corrected to include the closing parenthesis
                }
            }
        }
    }
}

function dfs(graph, startNode) {
    visited = new Set() // A set to keep track of visited nodes
    recursionDFS(graph, startNode, visited) // Call helper function
}

function recursionDFS(graph, startNode, visited) {
    print(startNode + " ") // Perform an action with node
    visited.add(startNode) // Mark the node as visited
        
    neighbours = graph.get(startNode)
    if (neighbours == null) {
        return
    }

    // Add unvisited neighbors call recursion function 
    for (neighbour : neighbours) {
        if (!visited.contains(neighbour)) {
            recursionDFS(graph, neighbour, visited)
        }
    }
}

The process is described much more clearly in the picture:

From the output, you may see the path of exploring goes as deep as possible. After visiting the deepest node, DFS comes back to visit the neighbors of the previous nodes. For our example:

1. Start at node A and push it to the stack.

2. Pop A from the stack, print it, and mark it as visited.

3. Push A's neighbors B, C, and H to the stack (the order might vary based on the implementation, but in this example, we push the neighbors in the order they appear in the list).

4. Pop H from the stack, since it's the last one pushed, print it, and mark it as visited. H has only one neighbor A, but since A is already visited, we do nothing.

5. Pop C from the stack, print it, and mark it as visited. Push C's unvisited neighbors to the stack.

6. Pop F from the stack, print it, and mark it as visited. Push F's unvisited neighbors to the stack.

7. Pop E from the stack, print it, and mark it as visited. Push E's unvisited neighbors to the stack. Since B is already in the stack, we do nothing.

8. Pop B from the stack, print it, and mark it as visited. Push B's unvisited neighbors D and G to the stack.

9. Pop G from the stack, print it, and mark it as visited. G has only one neighbor B, but B is already visited, so we do nothing.

10. Pop D from the stack, print it, and mark it as visited. D has only one neighbor B, but B is already visited, so we do nothing.

The stack is now empty, and the DFS is complete. It visits the nodes in the following order:

A H C F E B G D

Breadth-first search (BFS) implementation

Below is the BFS algorithm implementation using a queue and an iterative approach.

function bfs(graph, startNode) {
    visited = new Set()       // A set to keep track of visited nodes
    queue = new Queue()       // A queue to hold nodes to visit
    queue.enqueue(startNode)  // Start by adding the initial node to the queue
    visited.add(startNode)    // Mark the start node as visited

    while (!queue.isEmpty()) {           // While there are nodes to visit
        currentNode = queue.dequeue()    // Remove the node from the front of the queue
        print(currentNode)               // Perform an action with node

        neighbours = graph.get(currentNode)

        // Enqueue all unvisited neighbors to the queue to repeat process
        for (neighbour in neighbours) {
            if (!visited.contains(neighbour)) {
                visited.add(neighbour)       // Mark the neighbor as visited
                queue.enqueue(neighbour)     // Add to the queue for later visitation
            }
        }
    }
}

function bfs(graph, startNode) {
    visited = new Set()          // A set to keep track of visited nodes
    queue = new Queue()          // A queue to hold nodes to visit
    visited.add(startNode)       // Mark the start node as visited
    queue.enqueue(startNode)     // Enqueue the start node

    recursiveBFS(queue, visited) // Start the recursive BFS
}

function recursiveBFS(queue, visited) {
    if queue.isEmpty() {
        return // Base case: if the queue is empty, we are done
    }

    currentNode = queue.dequeue() // Dequeue the next node to visit
    print(currentNode)            // Perform an action with the node
    neighbours = graph.get(currentNode)

    // Enqueue all unvisited neighbours and mark them as visited
    for (neighbour in neighbours) {
        if (!visited.contains(neighbour)) {
            visited.add(neighbour)    // Mark the neighbour as visited
            queue.enqueue(neighbour)  // Enqueue the neighbour
        }
    }

    recursiveBFS(queue, visited) // Recursively call BFS on the updated queue
}

BFS visits the nodes in the following order:

A B C H D E G F

Below is the picture illustrating the process:

You may see that the path of visited nodes differs from DFS. This is because the breadth-first approach requires us to visit all the neighbors of the current node first, and only then visit their neighbors.

Here is a picture showing the depth level for each node for a better understanding:

1. Start at node A and enqueue it to the queue.

2. Mark A as visited.

3. Dequeue A from the queue and print it.

4. Enqueue A's neighbors B, C, and H to the queue and mark them as visited.

5. Dequeue B from the queue and print it.

6. Enqueue B's unvisited neighbors D, E, and G to the queue and mark them as visited.

7. Dequeue C from the queue and print it.

8. Enqueue C's unvisited neighbor F to the queue and mark it as visited.

9. Dequeue H from the queue and print it.

10. Dequeue D from the queue and print it.

11. Dequeue E from the queue and print it.

12. Dequeue G from the queue and print it.

13. Dequeue F from the queue and print it.

Pathfinding

Traversal is a process of visiting all the nodes in a graph, while pathfinding involves finding a way from one specific node to another. Both DFS and BFS can be used to traverse a graph or find a path between two nodes.

However, BFS has an advantage of finding the shortest path in an unweighted graph.

BFS explores all the neighbors at the current depth before moving on to nodes on the next level. In contrast, DFS may take a long, convoluted path that may not be optimal. Moreover, If the target node is close to the source node, BFS might find it faster because it starts by searching the closest nodes first. DFS might travel deep into a graph before finding nodes that are actually close to the source.

To adapt BFS for pathfinding, you need to keep track of the paths and then return one as you reach the target node. In the code example below, we'll search for a node G, starting from node A:

function pathFinding(graph, start, goal) {
    // Excluding the case when start node is goal node
    if (start.equals(goal)) {
        return [start]
    }

    // Use Set() data structure to keep track of nodes and avoid revisiting 
    visited = new Set()
    visited.add(start)

    // To store the paths, use Queue, where elements are Map type
    // Key is a current node and value is a path list
    queue = new Queue([(start, [start])])

    // Add the start node to the queue with a path containing only the start node
    queue.add(start, [start])

    // Loop until the queue is empty
    while (!queue.isEmpty()) {
        pair = queue.poll()
        node = pair.getKey()
        path = pair.getValue()

        for (String next : graph.get(node)) {
            // If the neighbor hasn't been visited yet
            if (!visited.contains(next)) {
                // If the neighbor is the goal, return the path
                if (next.equals(goal)) {
                    path.add(next)
                    print("Path from " + start + " to " + goal + ": " + path)
                    return
                }
                // Mark the neighbor as visited
                visited.add(next)
                // Add the neighbor to the queue with the updated path
                newPath = new [path]
                newPath.add(next)
                queue.add(next, newPath)
            }
        }
    }
    // Return null if no path was found
    print("Path from " + start + " to " + goal + " does not exist")
}

The output is the path from the start to the goal node:

Shortest path from A to F: [A, C, F]

In the picture below, you can see the order in which the nodes were visited.

We used BFS as the core approach and it behaved similarly:

1. BFS starts from A and visits all the neighbors, checking to determine if each one is the goal node.

2. With no neighbors of A left, BFS moves to the next node, B, and then visits all of B's neighbors.

3. With no neighbors of B left, BFS moves to a node on the next depth level, which is C.

4. BFS visits C's neighbors and finds the goal node F.

5. Therefore, the shortest path from A to F is A -> C -> F.

Conclusion

In summary, both DFS and BFS are essential algorithms for traversing and searching graphs. DFS dives deep into a graph, exploring paths to their end before backtracking, while BFS works across the breadth of a graph, visiting all nodes at one level before moving to the next. Here are some key points to remember:

• Use DFS when you need to explore all possible paths or when a solution may be deeply hidden.

• Opt for BFS to find the shortest path or for problems that require visiting nodes in the order of their proximity.

Understanding these distinctions may help you choose the right tool for tasks like pathfinding, connectivity checking, or networks' analyses.