Code/dfs.py at master · Shruti-codes/Code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from collections import defaultdict

graph = defaultdict(list)
l =[0]*20
f =[0]*20
color = ["white"]*20
parent = [float("inf")]*20
low = [float("inf")]*20
time = 0
root = 5
Art = []
path = []

def edge(graph,u,v):
    graph[u].append(v)


def dfs(v):
	for u in graph[v]:
		if(color[u]=="white"):
			dfs_visit(u)


def dfs_visit(u):
	global time
	time = time + 1
	nchild =0
	color[u] = "gray"
	l[u] = time
	path.append(u)

	for i in graph[u]:
		if(color[i]=="gray" and parent[i]!=u):
			print("cycle exists")

		if(color[i]=="white"):
			nchild = nchild +1
			parent[i] = u
			dfs_visit(i)
			low[u] = min(low[u], low[i])
			if(nchild>1 and parent[u] == -1 ):
				Art.append(u)
			elif (parent[u] != -1 and low[i] >= l[u]):
				Art.append(u)
		elif(i!=parent[u]):
			low[u] = min(low[u], l[i])

	color[u] = "black"
	time = time +1
	f[u]=time
	return nchild


edge(graph,1,2)
edge(graph,1,3)
edge(graph,2,5)
edge(graph,4,8)
edge(graph,2,3)
edge(graph,2,6)
edge(graph,3,6)
edge(graph,5,6)
edge(graph,1,4)
edge(graph,4,7)
edge(graph,7,8)

dfs(1)

print("Articulation point")
print(Art)

print("dfs")
print(path)