[CS Fundamentals] DFS and BFS

---

In this article, I will introduce the basic concept of Depth-First Search(DFS) and Breadth-First Search(BFS). Both focuses searching, but the difference is the way of doing it.

---

DFS

To understand DFS, you need to know stack and recursive function. I will explain how they are related to each other as I go through the example below.

Example:

We have a graph above, and let’s say the starting node is 1, and 1 is connected to 2, 3, 8. In DFS, we move to the node that holds the smalles value. In this case, it is 2. Now, 2 is only connected to 7. 7 is connected to 8 and 6, but 6 is the smallest, so we move to 6. Now we have reached the deepest part of the graph. So far, we have a stack that looks like this:

We can say stack = [1,2,7,6] currently. Now we are at 6, however, the only connected node is 7, and it is already visited (i.e. searched), so we pop 6 from the stack.

If you keep doing that recursively until all the nodes are visited, DFS ends.

Now, let’s write this in Python:

def dfs(graph, visited, v):
    visited[v] = True

    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(graph, visited, i)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, visited, 1)

Le’ts have a look at 2D list graph. I set the index 0 as an empty list because the smallest value in our graph is 1, so it is much easier to deal with index if I set index 0 as []. Furthermore, graph[1] = [2, 3, 8]. This means that the node 1 is connected to node 2, 3 and 8.

Notice that we need to keep track of the nodes that are visited by using visited list. Also, notice th use of recursive function, so we can search until all the nodes are visited.

---

BFS

BFS is not much different from DFS. It uses queue rather than stack, and it searches nodes widely.

Like the previous DFS example, the graph is the same, and the starting node is 1. We have three nodes that are directly connected to 1, which are 2, 3, 8. So, I am going to add them to my queue.

queue = [2, 3, 8]

We pop the left-most element from the queue, and move to that node. It is 2, so we do the same thing as we did on node 1. We have two nodes that are directly connected to 2, which are 1 and 7. 1 was visited previously, so we add 7 to queue.

queue = [3,8,7]

We pop the left-most element from the queue, and do the same thing.

queue = [8,7,4,5] and so on..

Let’s write this in Python:

from collections import deque

def bfs(graph, visited, v):
    Q = deque([start])
    visited[v] = True

    while Q:
        v = Q.popleft()
        for i in graph[v]:
            if not visited[i]:
                Q.append(i)
                visited[i] = True

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, visited, 1)