数据结构图的存储表示.pptx
图,数据结构,图的概念和操作图的存储：邻接矩阵，邻接表图的遍历：宽度优先，深度优先生成树：DFS 生成树，BFS 生成树最小生成树：Prim 算法，Kruskal 算法最短路径问题：单源点最短路径和 Dijkstra 算法所有顶点之间的最短路径和 Floyd 算法AOV 网，拓扑排序AOE 网，关键路径,主要内容,*,第七章 图,*,无向图、有向图、带权图（网）,2023/4/25,3,第七章 图,Graph(V,E)V=v|v 某数据对象顶点的有穷非空集合；E=(u,v)|u,v V 或 E=|x,y V是顶点之间关系的有穷集合，也叫边（或弧）集合。称u、v互为邻接点。,图的概念,2023/4/25,4,第七章 图,与之相关联的边或弧的数目有向图：D(v)=ID(v)+OD(v)ID(v)：入度（in-degree），即入边数；OD(v)：出度（out-degree），即出边数。,顶点的度,*,第七章 图,v,ADT Graph:Graph(self)#图的创建vertex_num(self)#获取顶点总数vertices(self)#获取图的顶点集合add_vertex(self,v)#添加顶点add_edge(self,v1,v2)#添加v1到v2的边get_edge(self,v1,v2)#获取边(v1,v2)的信息，例如权out_edges(self,v)#获取从v发出的所有“边”（v的所有邻接点）degree(self,v)#求v的度,图的基本操作,*,*,第七章 图,图的存储,2023/4/25,第七章 图,7,顶点集顶点信息表顶点总数关系集顶点之间关系，即边集或弧集边或弧的总数图的类型有向、无向、带权、不带权,应存储的内容,*,*,第七章 图,邻接矩阵Adjacent Matrix,2023/4/25,9,第七章 图,无向图的邻接矩阵：对称,2023/4/25,10,第七章 图,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,有向图的邻接矩阵：非对称,2023/4/25,11,第七章 图,Python等长list的list：0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,有向带权图的邻接矩阵,2023/4/25,12,第七章 图,Python等长list的list：0,3,5,8,inf,0,1,4,9,inf,0,2,6,inf,inf,0,带权图的无穷大：inf=float(inf),class Graph:def _init_(self,mat):vnum=len(mat)#对传入的mat做了拷贝构造 self._mat=mati:for i in range(vnum)self._vnum=vnum,图的建立邻接矩阵,2023/4/25,13,第七章 图,获取顶点v的所有“邻接点”,2023/4/25,14,g1.out_edges(1)=(0,1),(4,1),(5,1),g3.out_edges(2)=(0,9),(3,2),def 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)#(邻接点，边权)return edges,获取顶点v的所有“邻接点”（邻接边、出边）,2023/4/25,15,第七章 图,邻接表 Adjacent List（邻接矩阵的压缩）,2023/4/25,16,第七章 图,无向图的邻接表,2023/4/25,17,第七章 图,g1.out_edges(1)=(0,1),(4,1),(5,1),Python中list的list：(1,1),(4,1),(0,1),(4,1),(3,1),(5,1),(2,1),(5,1),(0,1),(1,1),(1,1),(2,1),(3,1),有向图的邻接表,2023/4/25,18,第七章 图,g2.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/25,19,第七章 图,方便找到入边！,有向带权图的邻接表,2023/4/25,20,第七章 图,g3.out_edges(2)=(0,9),(3,2),Python中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(mat)#所有顶点的(邻接点，边权)对的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的所有“邻接点”（邻接边、出边）,2023/4/25,第七章 图,22,课本中对无权、有权图统一处理了，具体应用中可针对图的类型做专门的定义，使得无权图的邻接点集是单纯的点集，不是（u,1）形式的边对。通常对图的表示和操作，直接使用list的list型的对象即可，不需要封装成专门Graph类型。,说明,2023/4/25,第七章 图,23,由文件中读入图信息UCSD_Algorithms on Graph,2023/4/25,第七章 图,24,2023/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)#有向图去除此句！,无权图的读入,*,第七章 图,*,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.append(w),有向带权图的读入,2023/4/25,第七章 图,27,import sys#导入sys模块input=sys.stdin.read()这里要在 console窗口 中，转到文件所在的目录，执行命令：python*.py graph.txt其中：*.py 是包含代码段的文件 graph.txt是图信息文件，和*.py在同一目录下也可以：python*.py然后手工输入图信息，以Ctrl+Z结束输入。,将标准输入stdin重定向到文件,2023/4/25,第七章 图,28,
