数据结构图的存储表示.pptx

《数据结构图的存储表示.pptx》由会员分享，可在线阅读，更多相关《数据结构图的存储表示.pptx（28页珍藏版）》请在第壹文秘上搜索。

1、图图 数据结构数据结构l图的概念和操作图的概念和操作l图的存储：邻接矩阵，邻接表图的存储：邻接矩阵，邻接表l图的遍历：宽度优先，深度优先图的遍历：宽度优先，深度优先l生成树：生成树：DFS 生成树，生成树，BFS 生成树生成树l最小生成树：最小生成树：Prim 算法，算法，Kruskal 算法算法l最短路径问题：最短路径问题：n单源点最短路径和单源点最短路径和 Dijkstra 算法算法n所有顶点之间的最短路径和所有顶点之间的最短路径和 Floyd 算法算法lAOV 网，拓扑排序网，拓扑排序lAOE 网，关键路径网，关键路径主要内容主要内容*第七章第七章 图图*无向图、无向图、有向图、带权图（

2、网）有向图、带权图（网）2023-4-253第七章第七章 图图ABCDEFABCDEABCD86394125lGraph( V, E )nV = v | v 某数据对象某数据对象 顶点的有穷非空集合；顶点的有穷非空集合；nE = (u, v) | u, v V 或或 E = | x, y V 是顶点之间关系的有穷集合，也叫边（或弧）集合。是顶点之间关系的有穷集合，也叫边（或弧）集合。 称称u、v互为邻接点。互为邻接点。图的概念图的概念2023-4-254第七章第七章 图图uvuvl与之相关联的边或弧的数目与之相关联的边或弧的数目l有向图：有向图：D(v)=ID(v)+OD(v)nID(v)：

3、入度（入度（in-degree），即入边数；），即入边数；nOD(v)：出度（：出度（out-degree），即出边数。），即出边数。顶点的度顶点的度 *第七章第七章 图图vlADT Graph: nGraph(self) # 图的创建图的创建nvertex_num(self) # 获取顶点总数获取顶点总数nvertices(self) # 获取图的顶点集合获取图的顶点集合nadd_vertex(self, v) # 添加顶点添加顶点nadd_edge(self, v1, v2) # 添加添加v1到到v2的边的边nget_edge(self, v1, v2) # 获取边获取边(v1, v2)的

4、信息，例如权的信息，例如权nout_edges(self, v) # 获取从获取从v发出的所有发出的所有“边边” （v的所有邻接点）的所有邻接点）ndegree(self, v) # 求求v的度的度图的基本操作图的基本操作*第七章第七章 图图图的存储图的存储2023-4-25第七章第七章 图图7l顶点集顶点集n顶点信息表顶点信息表n顶点总数顶点总数l关系集关系集n顶点之间关系，即边集或弧集顶点之间关系，即边集或弧集n边或弧的总数边或弧的总数l图的类型图的类型n有向、无向、带权、不带权有向、无向、带权、不带权应存储的内容应存储的内容*第七章第七章 图图邻接矩阵邻接矩阵Adjacent Matri

5、x2023-4-259第七章第七章 图图无向图的邻接矩阵：对称无向图的邻接矩阵：对称2023-4-2510第七章第七章 图图Python等长等长list的的list： 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 ABCDEF001000100110011100101110010000001010有向图的邻接矩阵：非对称有向图的邻接矩阵：非对称2023-4-2511第七章第七章 图图Python等长等长list的的list： 0, 1, 0, 0, 1, 0, 0

6、, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0 ABCDE0010000010011100001000010有向带权图的邻接矩阵有向带权图的邻接矩阵2023-4-2512第七章第七章 图图Python等长等长list的的list： 0, 3, 5, 8, inf, 0, 1, 4, 9, inf, 0, 2, 6, inf, inf, 0 062094108530ABCD86394125带权图的无穷大：带权图的无穷大：inf = float(inf)class Graph: def _init_(self, mat): vnum =

7、 len(mat) # 对传入的对传入的mat做了拷贝构造做了拷贝构造 self._mat = mati: for i in range(vnum) self._vnum = vnum图的建立图的建立邻接矩阵邻接矩阵2023-4-2513第七章第七章 图图获取顶点获取顶点v的所有的所有“邻接点邻接点”2023-4-2514ABCDEFABCD86394125g1.out_edges(1) = (0, 1), (4, 1), (5, 1) g3.out_edges(2) = (0, 9), (3, 2) 0010001001100111001011100100000010100620941085

8、30def out_edges(self, v): 获取获取v的所有的所有(邻接点邻接点，边权边权)对，以对，以list形式返回形式返回 assert 0 = v self._vnum # 用用assert替代异常替代异常 return Graph._out_edges(self._mat, v) staticmethod def _out_edges(mat, v): edges = row = matv for i in range(len(row): if rowi != 0 and rowi != inf: edges.append(i, rowi) # (邻接点邻接点，边权边权) r

9、eturn edges获取顶点获取顶点v的所有的所有“邻接点邻接点”（邻接边、出边）（邻接边、出边）2023-4-2515第七章第七章 图图邻接表邻接表 Adjacent List（邻接矩阵的压缩）（邻接矩阵的压缩）2023-4-2516第七章第七章 图图无向图的邻接表无向图的邻接表2023-4-2517第七章第七章 图图ABCDEFABCDEF01234514045123355210g1.out_edges(1) = (0, 1), (4, 1), (5, 1) Python中中list的的list： (1, 1), (4, 1), (0, 1), (4, 1), (3, 1), (5, 1

10、), (2, 1), (5, 1), (0, 1), (1, 1), (1, 1), (2, 1), (3, 1) 有向图的邻接表有向图的邻接表2023-4-2518第七章第七章 图图ABCDE012341423102ABCDEg2.out_edges(3) = (0, 1), (1, 1) Python中中list的的list： (1, 1), (4, 1), (2, 1), (3, 1), (0, 1), (1, 1) (2, 1) 有向图的逆邻接表有向图的逆邻接表2023-4-2519第七章第七章 图图ABCDE01234ABCDE4013204方便找到入边！方便找到入边！有向带权图的邻

11、接表有向带权图的邻接表2023-4-2520第七章第七章 图图g3.out_edges(2) = (0, 9), (3, 2) ABCD0123ABCD863941256031528312409023Python中中list的的list： (1, 3), (2, 5), (3, 8), (2, 1), (0, 4), (0, 9), (3, 2), (0, 6) # 课本采用了继承方式，逻辑上不是太好！课本采用了继承方式，逻辑上不是太好！class GraphA(Graph): def _init_(self, mat): # mat是等长是等长list的的list vnum = len(ma

12、t) # 所有顶点的所有顶点的(邻接点，边权邻接点，边权)对的对的list self._mat = Graph._out_edges(mat, i) for i in range(vnum) self._vnum = vnum 图的建立图的建立邻接表邻接表2023-4-25第七章第七章 图图21 def out_edges(self, v): 获取获取v的所有的所有(邻接点，边权邻接点，边权)对，以对，以list形式返回形式返回 assert 0 = v self._vnum return self._matv 获取顶点获取顶点v的所有的所有“邻接点邻接点”（邻接边、出边）（邻接边、出边）20

13、23-4-25第七章第七章 图图22l课本中对无权、有权图统一处理了，具体应用中课本中对无权、有权图统一处理了，具体应用中可针对图的类型做专门的定义，使得无权图的邻可针对图的类型做专门的定义，使得无权图的邻接点集是单纯的点集，不是（接点集是单纯的点集，不是（u, 1）形式的边对。）形式的边对。l通常对图的表示和操作，直接使用通常对图的表示和操作，直接使用list的的list型的对型的对象即可，不需要封装成专门象即可，不需要封装成专门Graph类型。类型。说明说明2023-4-25第七章第七章 图图23由文件中读入图信息由文件中读入图信息UCSD_Algorithms on Graph2023-

14、4-25第七章第七章 图图242023-4-25第七章第七章 图图25 input = sys.stdin.read() data = list(map(int, input.split() n, m = data0:2 data = data2: edges = list(zip(data0:(2 * m):2, data1:(2 * m):2) adj = for _ in range(n) for (a, b) in edges: adja - 1.append(b - 1) adjb - 1.append(a - 1) # 有向图去除此句！有向图去除此句！无权图的读入无权图的读入*第七

15、章第七章 图图* input = sys.stdin.read() data = list(map(int, input.split() n, m = data0:2 data = data2: edges = list(zip(zip(data0:(3 * m):3, data1:(3 * m):3), data2:(3 * m):3) data = data3 * m: adj = for _ in range(n) cost = for _ in range(n) for (a, b), w) in edges: adja - 1.append(b - 1) costa - 1.appe

16、nd(w)有向带权图的读入有向带权图的读入2023-4-25第七章第七章 图图27import sys # 导入导入sys模块模块input = sys.stdin.read()这里要在这里要在 console窗口窗口 中，转到文件所在的目录，执行命令：中，转到文件所在的目录，执行命令：python *.py graph.txt其中：其中：*.py 是包含代码段的文件是包含代码段的文件 graph.txt是图信息文件，和是图信息文件，和*.py在同一目录下在同一目录下也可以：也可以： python *.py然后手工输入图信息，以然后手工输入图信息，以Ctrl+Z结束输入。结束输入。将标准输入将标准输入stdin重定向到文件重定向到文件2023-4-25第七章第七章 图图28