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
|
from collections import defaultdict
class :
'''
a class of directed graph
'''
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,l,r):
self.graph[l].append(r)
def __repr__(self):
a_list = ''
for k,v in self.graph.items():
a_list += repr(k) + ': ' + repr(v) + 'n'
return a_list
def DFSUtil(self,v,visited):
visited[v] = True
print(v)
for i in self.graph[v]:
if not visited[i]:
self.DFSUtil(i,visited)
def DFS(self,start):
visited = [False] * len(self.graph)
self.DFSUtil(start,visited)
if __name__ == '__main__':
graph = Graph()
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(2, 3)
graph.addEdge(3, 3)
print('the adjacency list of this graph: ')
print(graph)
print('DFS result with vertex 2 as start point:')
graph.DFS(2)
|
近期评论