使用python实现数据结构-图_python 图数据结构实现

| 使用python实现数据结构-图 |

两种存储形式（邻接矩阵、邻接表）

深度优先遍历DFS和广度优先遍历BFS

Dijkstra算法实现（邻接矩阵、邻接表）

Floyd算法实现

class VertexNode():
    def __init__(self, vertex_name, first_edge=None):
        """
        顶点属性结构体
        :param vertex_name: 顶点编号或标识
        :param first_edge: 该顶点出发的第一条边，初始化为None
        """
        super().__init__()
        self.first_edge = first_edge
        self.Vertexindex = vertex_name


class EdgeCList():
    def __init__(self, adjvex, next_adjvex=None, weight=1):
        """
        边表节点结构体
        :param adjvex: 与顶点关联的邻接点
        :param next_adjvex: 与顶点关联的其它邻接点，默认为None
        :param weight:顶点到该连接点的权重
        """
        super().__init__()
        self.weight = weight
        self.adjvex = adjvex
        self.next = next_adjvex


class Graph():
    def __init__(self, vertex_num, edge_num, edge_list, init_valueofNone=0, dirflag=False, wflag=False, vertex_name=None):
        """
        # 图构建，坐标起始值为0
        :param vertex_num: 顶点数量
        :param edge_num: 边数量
        :param edge_list:解释边关系的矩阵或列表[edge_num, 3]or[edge_num, 2], (vi, vj, wij) or (vi, vj) vi<->vj or vi->vj
        :param init_valueofNone:对于无关系的邻接矩阵填充的值(0或者None)
        :param dirflag:是否是有向图，默认无向图
        :param wflag:是否为有权图，默认无权图
        :param vertex_name:顶点名字或标识， 默认为None，即采用序号，只做信息储存，构建邻接表邻接矩阵还是采用编号执行
        """
        super().__init__()
        self.vertex_name = vertex_name      # 默认为空，采用顶点编号来决定
        self.wflag = wflag
        self.dirflag = dirflag
        self.init_valueofNone = init_valueofNone
        self.edge_list = edge_list
        self.vertex_num = vertex_num
        self.edge_num = edge_num
        self.adjmatrix = self.create_adjmatrix(vertex_num, self.edge_list)
        self.adjclist = self.create_adjclist(vertex_num, self.edge_list)

    def create_adjmatrix(self, vertex_num, edge_list):
        # 创建邻接矩阵
        # 构建vn*vn的空矩阵
        adjmatrix = [[self.init_valueofNone] * vertex_num for _ in range(vertex_num)]
        for i in range(self.vertex_num):
            adjmatrix[i][i] = 0     # 自己到自己长度为0

        # 依据邻接关系矩阵初始化邻接矩阵
        # 无权图:关系填充1（宽度为2代表无权，3代表有权）
        for item in edge_list:
            if self.wflag:
                weight = item[2]
            else:
                weight = 1
            adjmatrix[item[0]][item[1]] = weight
            if not self.dirflag:
                adjmatrix[item[1]][item[0]] = weight
        return adjmatrix

    def create_adjclist(self, vertex_num, edge_list):
        # 创建邻接表(头储存的是VertexNode变量，其他节点储存的是EdgeCList变量)
        # 使用列表储存邻接表, [vertex_num, vni] vni为与该顶点相连的边数

        # 初始化邻接表表头
        adjclist = {}   # 如果vertex标识为序号可以采用列表，这里采用字典
        for i in range(vertex_num):
            adjclist[i] = VertexNode(i)

        # 初始化边表
        for item in edge_list:
            if self.wflag:
                weight = item[2]
            else:
                weight = 1
            edgei = EdgeCList(adjvex=item[1], weight=weight)
            edgei.next = adjclist[item[0]].first_edge
            adjclist[item[0]].first_edge = edgei
            if not self.dirflag:
                edgej = EdgeCList(adjvex=item[0], weight=weight)
                edgej.next = adjclist[item[1]].first_edge
                adjclist[item[1]].first_edge = edgej
        return adjclist

    def DFS_list(self, firstnode=0, visited_nodes=list()):
        # 深度优先算法，传入初始顶点，输出初始遍历顶点顺序
        """
        :param visited_nodes: 每一次执行该操作应该将当前遍历信息传入下一次循环，不然永久循环
        :param firstnode: 初始顶点
        :return: 顶点的遍历序列即 visited_nodes 集合是无序的，因此需要用列表作为栈来使用
        1、使用列表构建一个栈，每当遍历到这个顶点时，将该顶点存入栈中，依次查询该顶点的边表
        2、当查询到该顶点的第一条边的另一顶点时循环调用DFS(递归条件是不在visited_nodes中)，跳出循环时将该点从栈中取出
        3、循环需要改变的变量是指向下一顶点
        4、循环终止条件为该顶点的邻接点为None
        """
        visited_nodes.append(firstnode)     # 由于只有不在该列表中才会循环调用DFS，所以该列表中的元素直接具有不重复性
        current_vex = self.adjclist[firstnode].first_edge   # 循环节点从栈顶提取
        while current_vex is not None:
            if current_vex.adjvex not in visited_nodes:
                self.DFS_list(current_vex.adjvex, visited_nodes=visited_nodes)
            current_vex = current_vex.next
        return visited_nodes

    def BFS_list(self, firstnode=0, visited_nodes=list()):
        # 广度优先算法，传入初始顶点，输出初始遍历顶点顺序
        # 对于广度优先，首先遍历一遍与起始顶点相连的所有顶点[vi0,vi1,...,vik]
        # 再从vi0遍历其所有邻接点
        # 存在从最浅到达最深或从最深到达最浅才用递归，这里符合条件吗？
        # 从栈底删除已经遍历的值，并从栈底取下一次需要遍历的值，那么最外层循环结束的条件为栈为空
        visited_nodes.append(firstnode)
        stack = [firstnode]

        # 每一层循环的判断条件是该起始顶点的所有邻接点被遍历，所以循环判断条件是边表的末端为None
        while len(stack) > 0:
            current_vex = self.adjclist[stack[0]].first_edge
            while current_vex is not None:
                # 当没被访问过时，添加到遍历队列和stack中，便于下一次循环使用
                if current_vex.adjvex not in visited_nodes:
                    visited_nodes.append(current_vex.adjvex)
                    stack.append(current_vex.adjvex)
                current_vex = current_vex.next
            # 栈底删除
            del stack[0]
        return visited_nodes

    def DFS_matrix(self, firstnode=0, visited_nodes=list()):
        # 深度优先算法，使用邻接矩阵实现，只考虑遍历顺序连接关系，不考虑权值
        """
        :param visited_nodes: 每一次执行该操作应该将当前遍历信息传入下一次循环，不然永久循环
        :param firstnode: 初始顶点
        :return: 顶点的遍历序列即 visited_nodes 集合是无序的，因此需要用列表作为栈来使用
        """
        visited_nodes.append(firstnode)  # 由于只有不在该列表中才会循环调用DFS，所以该列表中的元素直接具有不重复性
        # 以firstnode作为行标志，顺序搜索该行中第一个不为0的点(该点没被访问过)
        # 循环结束的标志：在改行再也找不到没有被访问过的非0点
        for j in range(self.vertex_num):
            current_vex = self.adjmatrix[firstnode][j]
            if current_vex == 1 and j not in visited_nodes:
                self.DFS_matrix(j, visited_nodes=visited_nodes)     # 递归由行坐标变为列坐标
        return visited_nodes

    def BFS_matrix(self, firstnode=0, visited_nodes=list()):
        # 广度优先算法，使用邻接矩阵实现
        visited_nodes.append(firstnode)
        stack = [firstnode]

        # 每一行遍历完后删除stack栈底，并取栈底作为新的起始顶点，循环结束条件还是stack为空
        while len(stack) > 0:
            for j in range(self.vertex_num):
                current_vex = self.adjmatrix[stack[0]][j]
                if current_vex == 1 and j not in visited_nodes:
                    stack.append(j)
                    visited_nodes.append(j)
            # 栈底删除
            del stack[0]
        return visited_nodes

    def Dijkstra_matrix(self, source):
        """
        使用带权的邻接矩阵存储结构
        数组dist[n]:每个分量dist[i]代表当前所找的从源点v到终点vi的最短路径的长度， 初始态：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为None
        数组path[n]:path[i]是一个列表，表示当前所找的从源点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i] = v_index 否则path[i] = -1
        数组s[n]:存放源点和已经生成的终点，其初态为只有一个源点v
        1、初始化：dist、path、s
        2、while(s中的元素个数<n)
            2.1 在dist[n]中求最小值，其下标为k;
            2.2 输出dist[j]和path[j]
            2.3 修改数组dist和path
            2.4 将顶点vk添加至数组s中
        :param source: 原顶点
        :param target: 目标顶点
        :return: weight of shortest_path、shortest_path
        Dijkstra算法在已知源点的情况下，可以一次性求解除源点到其他各点的最短路径
        """
        # 初始化
        s = [source]
        dist = []
        path = []
        for i in range(self.vertex_num):
            dist.append(self.adjmatrix[source][i])
            if self.adjmatrix[source][i] != None:
                path.append(source)
            else:
                path.append(-1)     # 代表无路径

        # 开始循环(终止条件是所有点都遍历过)
        while len(s) < self.vertex_num:
            # 在dist[n]中求最小值，其下标为k, vk为下一个遍历点
            mindist = None
            k = s[-1]
            for i in range(self.vertex_num):
                if i in s:
                    continue    # 最短路径比较只在不在s数组中的元素的路径值中确定，在s数组就代表已经找到了从源点到该点的最短路径
                if mindist is None and dist[i] is not None:
                    mindist = dist[i]
                    k = i
                elif mindist is not None and dist[i] is not None:
                    if dist[i] < mindist:
                        k = i
                        mindist = dist[i]
                else:
                    pass
            if k == s[-1]:
                break       # 代表当前起始点与其他各点均不相连

            # 以vk作为起点，更新dist和path
            for i in range(self.vertex_num):
                if i not in s:
                    if self.adjmatrix[k][i] != None and dist[k] != None:
                        current_dist = dist[k] + self.adjmatrix[k][i]
                        if dist[i] is None:
                            dist[i] = current_dist
                            path[i] = k
                        else:
                            if current_dist < dist[i]:
                                dist[i] = current_dist
                                path[i] = k
            s.append(k)
        return dist, path

    def Dijkstra_list(self, source):
        # 使用邻接表实现该算法
        # 1 初始化
        s = [source]
        dist = [None] * self.vertex_num
        path = [-1] * self.vertex_num
        dist[source] = 0

        VG = self.adjclist[source].first_edge
        while VG is not None:
            dist[VG.adjvex] = VG.weight
            path[VG.adjvex] = source
            VG = VG.next

        # 开始循环
        while len(s) < self.vertex_num:
            # dist值判断
            k = s[-1]
            min_dist = None
            for i in range(self.vertex_num):
                if i in s:
                    continue
                if min_dist is None and dist[i] is not None:
                    min_dist = dist[i]
                    k = i
                elif min_dist is not None and dist[i] is not None:
                    if dist[i] < min_dist:
                        min_dist = dist[i]
                        k = i
                else:
                    pass
            if k == s[-1]:
                break   # 说明该点到其他点无路径
            # 比较并修改dist和path
            VG = self.adjclist[k].first_edge
            current_dist = [None] * self.vertex_num     # 存储k到其他点的代价值
            current_dist[k] = 0
            while VG is not None:
                current_dist[VG.adjvex] = VG.weight
                VG = VG.next

            for i in range(self.vertex_num):
                if i not in s:
                    if dist[k] is not None and current_dist[i] is not None:
                        cd = dist[k] + current_dist[i]
                        if dist[i] is None:
                            dist[i] = cd
                            path[i] = k
                        else:
                            if cd < dist[i]:
                                dist[i] = cd
                                path[i] = k
            s.append(k)
        return dist, path



    def display_s2t(self, source, target, type=0):
        """
        :param source:
        :param target:
        :param type: 0 is using matrix and 1 is using list
        :return:
        """
        if type == 1:
            dist, path = self.Dijkstra_list(source)
        else:
            dist, path = self.Dijkstra_matrix(source)    # 获取以source为起点到各点的路径
        # 以target未开始，source为结束在path中查找经过的顶点路径
        if dist[target] is None:
            return None, -1     # s->t之间五路径
        else:
            path_s2t = [target]
            weight_s2t = dist[target]
            while target != source:
                path_s2t.append(path[target])
                target = path[target]
            path_s2t.reverse()
            return weight_s2t, path_s2t

    def Floyd_matrix(self):
        """
        与Dijkstra算法（无法确定最后终点，一步步前进式探索）是从初始节点逐步探索其它节点之后再从最短路径继续探索所有点的方式不同，
        Floyd是确定初始点和终点，不断在中间添加中间节点的方式来搜索路径
        dist:行为起点，列为终点，保存两者之间的最短路径权值；
        path:行为起点，列为终点，保存两者之间的最短路径序列,如[a, b, c]
        """
        # 最初的邻接矩阵即为dist矩阵的初始态
        dist = self.adjmatrix       # 使用None代表无路径
        path = dict()       # 使用字典存储，key=str(vi)+str(vk),value = [vi, vk]
        # 最初的path
        for i in range(self.vertex_num):
            for j in range(self.vertex_num):
                keyv = str(i) + str(j)
                if i == j:
                    path[keyv] = [i]
                elif self.adjmatrix[i][j] is None:
                    path[keyv] = []
                else:
                    path[keyv] = [i, j]
        # dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])   # 利用前一步信息再不断加入新中间节点进行判断
        # path[str(i) + str(j)] = min(path[str(i) + str(j)], path[str(i) + str(k)]+path[str(k) + str(j)])
        for k in range(self.vertex_num):
            for i in range(self.vertex_num):
                for j in range(self.vertex_num):
                    if dist[i][j] is None:
                        if dist[i][k] is None or dist[k][j] is None:
                            pass
                        else:
                            dist[i][j] = dist[i][k]+dist[k][j]
                            path[str(i)+str(j)] = path[str(i)+str(k)] + path[str(k)+str(j)][1:]
                    else:
                        if dist[i][k] is None or dist[k][j] is None:
                            pass
                        else:
                            if dist[i][k]+dist[k][j] < dist[i][j]:
                                dist[i][j] = dist[i][k]+dist[k][j]
                                path[str(i)+str(j)] = path[str(i)+str(k)] + path[str(k)+str(j)][1:]
        return dist, path


if __name__ == "__main__":
    vertex_num = 8
    edge_num = 9
    edge_list = [[1,3],
                 [1,2],
                 [2,5],
                 [2,4],
                 [3,7],
                 [3,6],
                 [4,8]]
    # 起始点是从0开始，所以要索引-1对于边关系列表而言
    edge_list = [[i-1, j-1] for [i, j] in edge_list]
    Mgraph = Graph(vertex_num=vertex_num,
                   edge_num=edge_num,
                   edge_list=edge_list)
    ansd = Mgraph.DFS_list(7)     # 以8为起始顶点
    # 深度遍历结果与边关系在邻接表中存入的顺序有关，按照头插入原则，可能后次序的关系先被打印出，
    # 如果要按照最小值先搜索的原则，那么可以在邻接表生成函数中添加一个排序函数之后再进行插入
    print([i+1 for i in ansd])
    ansb = Mgraph.BFS_list(1)  # 以2为起始顶点
    print([i + 1 for i in ansb])

    # 邻接矩阵由于编号顺序访问，所以总是先遍历小索引；而邻接表则与边表存入顺序有关，后存入先被访问
    ansdm = Mgraph.DFS_matrix(7)  # 以8为起始顶点
    print([i + 1 for i in ansdm])

    ansbm = Mgraph.BFS_matrix(1)  # 以2为起始顶点
    print([i + 1 for i in ansbm])

    # Dijkstra算法验证
    vertex_num = 7
    edge_num = 8
    edge_list = [[1, 2, 8],
                 [1, 4, 1],
                 [2, 3, 9],
                 [4, 3, 4],
                 [4, 5, 6],
                 [3, 5, 1],
                 [7, 6, 2],
                 [7, 1, 1],
                 [4, 7, 3]]
    # 起始点是从0开始，所以要索引-1对于边关系列表而言
    edge_list = [[i - 1, j - 1, w] for [i, j, w] in edge_list]
    DMgraph = Graph(vertex_num=vertex_num,
                    edge_num=edge_num,
                    edge_list=edge_list,
                    dirflag=True,
                    wflag=True,
                    init_valueofNone=None)
    # print(DMgraph.adjmatrix)
    source = 1
    target = 5
    wp, path = DMgraph.display_s2t(source=source-1, target=target-1, type=1)
    if wp is None:
        print("there is no route between source and target!")
    else:
        print(f"from source to target, the weight is {wp}")
        print([i+1 for i in path])

    # 测试Floyd
    dist, path = DMgraph.Floyd_matrix()
    # print(path)
    wp = dist[source-1][target-1]
    pathst = path[str(source-1)+str(target-1)]
    if wp is None:
        print("there is no route between source and target!")
    else:
        print(f"from source to target, the weight is {wp}")
        print([i + 1 for i in pathst])
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
'
运行
运行

运行案例结果：

[8, 4, 2, 5, 1, 3, 6, 7]
[2, 4, 5, 1, 8, 3, 6, 7]
[8, 4, 2, 1, 3, 6, 7, 5]
[2, 1, 4, 5, 3, 8, 6, 7]
from source to target, the weight is 6
[1, 4, 3, 5]
from source to target, the weight is 6
[1, 4, 3, 5]
1
2
3
4
5
6
7
8