Graph Traversal

Types of Edges[1]

Item	DFS	BFS
Data Structure	Stack	Queue
Vertex Order	one sequence	two sequences
Edge Type (Undirected Graph)	tree edge, back edge	tree edge, cross edge
Time Complexity (Adjacency Matrix)	$O({\parallel V\parallel }^2)$	$O({\parallel V\parallel }^2)$
Time Complexity (Adjacency List)	$O(\parallel V\parallel +\parallel E\parallel )$	$O(\parallel V\parallel +\parallel E\parallel )$
Worst-case Space Complexity	$O(\parallel V\parallel )$	$O(\parallel V\parallel )$

Example

Adjacency Matrix

	0	1	2	3	4	5	6
0	0	1	1	0	0	0	0
1	1	0	1	1	0	0	0
2	1	1	0	0	1	0	0
3	0	1	0	0	1	0	0
4	0	0	1	1	0	1	0
5	0	0	0	0	1	0	1
6	0	0	0	0	0	1	0

Adjacency List

• 0: 1 -> 2
• 1: 0 -> 2 -> 3
• 2: 0 -> 1 -> 4
• 3: 1 -> 4
• 4: 2 -> 3 -> 5
• 5: 4 -> 6
• 6: 5

DFS

def dfs(matrix):
    # taking adjacency matrix
    stack = [0]
    visited = set()
    visited.add(0)
    while stack:
        cur = stack.pop()
        # do something
        print(cur)
        for i, adj in enumerate(matrix[cur]):
            if adj and i not in visited:
                visited.add(i)
                stack.append(i)

BFS

from collections import deque

def bfs(lists):
    # taking adjacency list
    q = deque([0])
    visited = [False] * len(lists)
    visited[0] = True
    while q:
        cur = q.popleft()
        # do something
        print(cur)
        for i in lists[cur]:
            if not visited[i]:
                visited[i] = True
                q.append(i)

Level Order Traversal

from collections import deque

def lot(lists) -> int:
    # taking adjacency list
    q = deque([0])
    visited = [False] * len(lists)
    visited[0] = True
    lv = 0
    while q:
        lv += 1
        print(f'level {lv}')
        for _ in range(len(q)):
            cur = q.popleft()
            # do something
            print(cur)
            for i in lists[cur]:
                if not visited[i]:
                    visited[i] = True
                    q.append(i)
    return lv

Tests

---

1. Image is from https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ ↩︎