Archived
dfs backedge detection
An old note — I haven't updated it since I wrote it.
When performing a DFS traversal, it can be useful finding backedges, i.e edges to nodes we would have visited, had we not done so already. A simple way of doing this, is to mutate your undirected graph to a directed graph during the DFS traversal.
1class Graph:
2 def __init__(self, adjlist):
3 self.visited = set()
4 self.adjlist = adjlist
5
6 def dfs(self, parent, node):
7 if node in self.visited:
8 print(f"backedge: {parent} -> {node}")
9 return
10 print(f"{node}")
11 self.visited.add(node)
12 for neighbour in self.adjlist[node]:
13 self.adjlist[neighbour].remove(node)
14 self.dfs(node, neighbour)
15
16
17g = {}
18g[1] = [4, 2]
19g[2] = [1, 3]
20g[3] = [4, 5, 6, 2]
21g[4] = [1, 3]
22g[5] = [3, 6]
23g[6] = [5, 3]
24
25
26g1 = Graph(g)
27g1.dfs(0, 1)
At which point, the only nodes that get visited twice during the DFS are via backedges.
11
24
33
45
56
6backedge: 6 -> 3
72
8backedge: 2 -> 1
