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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| """
图
Copyright ©conghaoyuan@gmail.comm
"""
class Graph:
def __init__(self, Vertex=None) -> None:
if Vertex is None:
Vertex = {}
self.Vertex = Vertex
def findVertexs(self):
return list(self.Vertex.keys())
def findEdges(self):
edegename = []
for vrtx in self.Vertex:
for evrtx in self.Vertex[vrtx]:
e = [vrtx, evrtx]
if e not in edegename:
edegename.append(e)
return edegename
def addVertex(self, vrtx):
if vrtx not in self.Vertex:
self.Vertex[vrtx] = []
def addEdge(self, edge):
(vrtx1, vrtx2) = tuple(edge)
if vrtx1 in self.Vertex:
self.Vertex[vrtx1].append(vrtx2)
else:
self.Vertex[vrtx1] = [vrtx2]
def dfs(self, vertex, visited=None, lists=None):
if visited is None:
visited = set()
if lists is None:
lists = []
visited.add(vertex)
if vertex not in lists:
lists.append(vertex)
for next in set(self.Vertex[vertex]) - visited:
self.dfs(next, visited, lists)
return lists
def subgraph(self):
vertexs = set(self.findVertexs())
visted = set()
lists = []
for vertex in vertexs:
if vertex in visted:
continue
sub_list = self.dfs(vertex)
lists.append(sub_list)
visted.update(set(sub_list))
return lists
if __name__ == "__main__":
graph = Graph()
vertexs = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M']
edges = [
['A', 'B'],['A', 'C'],['A', 'F'],['A', 'L'],
['B', 'A'],['B', 'M'],
['C', 'A'],
['D', 'E'],
['E', 'D'],
['F', 'A'],
['G', 'H'],['G', 'I'],['G', 'K'],
['H', 'G'],['H', 'K'],
['I', 'G'],
['J', 'L'],['J', 'M'],
['K', 'H'],['K', 'G'],
['L', 'A'],['L', 'J'],['L', 'M'],
['M', 'L'],['M', 'J'],['M', 'B'],
]
for vrtx in vertexs:
graph.addVertex(vrtx)
for edge in edges:
graph.addEdge(edge)
print(graph.Vertex)
print(graph.dfs('A'))
print(graph.subgraph())
|
