python构造图的方法

只要各顶点及边都确定了,就可以构建出图。

一、图类

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
class Graph:
def __init__(self, vertices=[], matrix=[]):
'''
图的初始化
'''
self.vertices = vertices
self.matrix = matrix
self.edges_dict = {} # {(tail, head): weight}
self.edges_array = [] # (tail, head, weight)

if self.matrix == []:
self.matrix = [[0 for col in range(len(self.vertices))] for row in range(len(self.vertices))]

self.add_edges_from_matrix()

def add_vertex(self, key):
'''
添加顶底
'''
if key not in self.vertices:
self.vertices.append(key)

for i in range(len(self.vertices)-1):
self.matrix[i].append(0)

nRow = [0] * len(self.vertices)
self.matrix.append(nRow)

def add_edge(self, tail, head, cost=1):
'''
添加边
'''
if tail not in self.vertices:
self.add_vertex(tail)

if head not in self.vertices:
self.add_vertex(head)

self.matrix[self.vertices.index(tail)][self.vertices.index(head)] = cost

self.edges_dict[(tail, head)] = cost
self.edges_array.append((tail, head, cost))

def add_edges_from_list(self, edges_list):
'''
从列表中获取边集
'''
self.edges_dict = {}
self.edges_array = []

for i in range(len(edges_list)):
self.add_edge(edges_list[i][0], edges_list[i][1], edges_list[i][2])
self.edges_array.append([edges_list[i][0], edges_list[i][1], edges_list[i][2]])

def add_edges_from_matrix(self):
'''
从邻接矩阵中获取边集
'''
self.edges_dict = {}
self.edges_array = []

for i in range(len(self.matrix)):
for j in range(len(self.matrix)):
if 0 < self.matrix[i][j] < float('inf'):
self.edges_dict[self.vertices[i], self.vertices[j]] = self.matrix[i][j]
self.edges_array.append([self.vertices[i], self.vertices[j], self.matrix[i][j]])

二、构建图

1、邻接矩阵构建无向图

1
2
3
4
5
6
7
8
9
10
11
12
13
nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

matrix = [[0, 1, 1, 1, 1, 1, 0, 0], # a
[0, 0, 1, 0, 1, 0, 0, 0], # b
[0, 0, 0, 1, 0, 0, 0, 0], # c
[0, 0, 0, 0, 1, 0, 0, 0], # d
[0, 0, 0, 0, 0, 1, 0, 0], # e
[0, 0, 1, 0, 0, 0, 1, 1], # f
[0, 0, 0, 0, 0, 1, 0, 1], # g
[0, 0, 0, 0, 0, 1, 1, 0]] # h

my_graph = Graph(nodes, matrix)
print(my_graph.edges_array)

2、邻接矩阵构建有向图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

inf = float('inf')
matrix = [[0, 2, 1, 3, 9, 4, inf, inf], # a
[inf, 0, 4, inf, 3, inf, inf, inf], # b
[inf, inf, 0, 8, inf, inf, inf, inf], # c
[inf, inf, inf, 0, 7, inf, inf, inf], # d
[inf, inf, inf, inf, 0, 5, inf, inf], # e
[inf, inf, 2, inf, inf, 0, 2, 2 ], # f
[inf, inf, inf, inf, inf, 1, 0, 6 ], # g
[inf, inf, inf, inf, inf, 9, 8, 0 ]] # h

my_graph = Graph(nodes, matrix)
print(my_graph.edges_array)

3、邻接表构建图

1
2
3
4
5
6
7
8
9
nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

edge_list = [('A', 'F', 9), ('A', 'B', 10), ('A', 'G', 15), ('B', 'F', 2),
('G', 'F', 3), ('G', 'E', 12), ('G', 'C', 10), ('C', 'E', 1),
('E', 'D', 7)]

my_graph = Graph(nodes)
my_graph.add_edges_from_list(edge_list)
print(my_graph.edges_array)
0%