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 ({‖ V ‖}^{2})$	$O ({‖ V ‖}^{2})$
Time Complexity (Adjacency List)	$O (‖ V ‖ + ‖ E ‖)$	$O (‖ V ‖ + ‖ E ‖)$
Worst-case Space Complexity	$O (‖ V ‖)$	$O (‖ V ‖)$

Example

Graph

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

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