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)