dfs

🏠

Super simple DFS.

 1 class Graph:
 2     def __init__(self):
 3         self.visited = set()
 4 
 5     def dfs(self, node):
 6         if node in self.visited:
 7             return
 8         print(node)
 9         self.visited.add(node)
10         for neighbour in self.adjlist[node]:
11             self.dfs(neighbour)
12 
13 
14 g = {}
15 g[1] = [2, 6]
16 g[2] = [7, 3, 1]
17 g[3] = [4, 2]
18 g[4] = [5, 7, 3]
19 g[5] = [4, 7, 6]
20 g[6] = [5, 1]
21 g[7] = [5, 4, 2]
22 
23 g1 = Graph()
24 g1.adjlist = g
25 g1.dfs(1)

Pasted image 19.png

Output:

1 1
2 2
3 7
4 5
5 4
6 3
7 6

See also:

dfs backedge detection
bfs