数据结构7图.ppt
《数据结构7图.ppt》由会员分享,可在线阅读,更多相关《数据结构7图.ppt(40页珍藏版)》请在三一办公上搜索。
1、第七章.图(Chapter 7.Graph),7.1 图的定义及基本操作,图型结构是一种非常重要的、比线性和树型结构更复杂的非线性数据结构,可广泛用于描述自然界各种关系。,右图所示即为一图型结构:,图的一些基本术语:,顶点(vertex),数据元素所构成的结点通常称为顶点。,弧(arc),若两个顶点间有关系 E,则称 为一条弧。,弧头(head-又称终端点 terminal node),若 为一条弧,则顶点 y 称为弧头。,弧尾(tail-又称初始点 initial node),若 为一条弧,则顶点 x 称为弧尾。,有向图(directed graph),若 E,并不总有 E,则称此图为有向图
2、。,无向图(undirected graph),若 E,总有 E,则称此图为无向图。,边(edge),无向图中两条弧和可用一条边(x,y)来表示。,完全图(completed graph),具有 n*(n-1)/2 条边的无向图称为完全图。,有向完全图(completed directed graph),具有 n*(n-1)条弧的有向图称为有向完全图。,稀疏图(sparse graph),边数很少的图称为稀疏图。,权(weight),有些图的边或弧具有一定的大小,称之为权。,网(network),带权值的图又称为网或网络。,子图(subgraph),由图的部分顶点和边组成的新图称为原图的子图。
3、,生成子图(spanning subgraph),由图的全部顶点和部分边组成的子图称为原图的生成子图。,稠密图(dense graph),边数很多的图称为稠密图。,邻接点(adjacent),若边(vi,vj)E,则 vi 与 vj 互为邻接点。,依附(incident),若边(vi,vj)E,则称边(vi,vj)依附于顶点 vi 和 vj。,相关联(correlative),若边(vi,vj)E,又称边(vi,vj)与顶点 vi 和 vj 相关联。,顶点的度(degree),与顶点相关联的边数称为该顶点的度,又分为入度和出度。,顶点的入度(indegree),以顶点为头的弧数称为该顶点的入度
4、。,顶点的出度(outdegree),以顶点为尾的弧数称为该顶点的出度。,路径(path),由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。,回路(loop-又称环 cycle),起点和终点为同一顶点的路径称为回路。,连通(connected),无向图中顶点vi到vj间有路径存在,则称vi和vj是连通的。,连通图(connected graph),无向图中任意两顶点间均存在路径,则称该图为连通图。,连通分量(connected component),无向图中的极大连通子图称为原图的连通分量。,强连通图(strongly connected graph),有向图中任意两顶点间均存在路径
5、,则称该图为强连通图。,强连通分量(strongly connected component),有向图中的极大强连通子图称为原图的强连通分量。,生成树(spanning tree),连通图的极小连通生成子图称为原图的生成树。,有向树(directed tree),恰有一个顶点入度为0,其余顶点入度均为1的有向图。,生成森林(spanning forest),由多棵有向树构成的有向图的生成子图称为生成森林。,最小代价生成树(minimum cost spanning tree),连通网中由最小权值的边构成的生成树。,图的基本操作:,INITIATE,GETVERTEX,FIRSTADJ,NEXT
6、ADJ,INSVERTEX,TRAVERSE,INSARC,DELVERTEX,DELARC,7.2 图的存储结构,顺序存储结构:,1、邻接矩阵(adjacency matrix),CONST vtxnum=user_supply;TYPE vtx=1.vtxnum;bit=0.1;graph=ARRAY vtx,vtx OF bit;,2、关联矩阵(correlated matrix),CONST vtxnum=user_supply;edgenum=user_supply;TYPE vtx=1.vtxnum;edge=1.edgenum;bit=-1.1;graph=ARRAY vtx,e
7、dge OF bit;,链式存储结构:,1、邻接表(adjacency list),按结点出度建立:,TYPE arcptr=arcnode;vexnode=RECORD vexdata:vextype;firstarc:arcptr END;arcnode=RECORD adjvex:vtx;info:edgetype;nextarc:arcptr END;adjlist=ARRAY vtx OF vexnode;,2、逆邻接表(inverse adjacency list),按结点入度建立:,定义同邻接表,3、十字链表(orthogonal list),按结点入度和出度建立:,TYPE a
8、rclk=anode;vnode=RECORD data:vextype;firstin,firstout:arclk END;anode=RECORD tailvex,headvex:vtx;hlink,tlink:arclk END;ortholist=ARRAY vtx OF vnode;,4、邻接多重表(adjacency multilist),邻接多重表是无向图的一种存储结构:,TYPE edgelk=enode;vnode=RECORD data:vextype;firstedge:arclk END;enode=RECORD mark:0.1;ivex,jvex:vtx;ilin
9、k,jlink:edgelk END;adjmulist=ARRAYvtx OF vnode;,7.3 图的遍历,深度优先遍历(depth_first search),即按某种搜索顺序对图中每个结点访问且仅访问一次。,从图中某一顶点 v0 出发,访问该顶点,并依次从v0的所有未被访问过的邻接点中任意选取一个顶点作为新的出发点,用同样的方法访问其它所有顶点,直到所有与v0 连通的顶点均被访问到为止;若此时仍有顶点尚未被访问,则从未被访问过的顶点中任意选取一个顶点作为新的出发点,反复此过程,直至图中所有顶点均被访问过一遍为止。,A,B,F,E,H,C,D,G,PROC Traverse(g:gra
10、ph;VAR visited:ARRAY vtx OF boolean);For v:=1 To vtxnum Do visited v:=false;For v:=1 To vtxnum Do If Not visitedv Then dfs(g,v)ENDP;,PROC dfs(g:graph;v:vtx);visit(v);visited v:=true;w:=FIRSTADJ(g,v);While w0 Do Begin If Not visited w Then dfs(g,w);w:=NEXTADJ(g,v,w)EndENDP;,广度优先遍历(breadth_first searc
11、h),从图中某一顶点v0出发,访问该顶点,并依次访问v0的所有未被访问过的邻接点,然后将所有这些邻接点作为新的出发点,用同样的方法访问其它所有顶点,直到所有与v0 连通的顶点均被访问到为止;若此时仍有顶点尚未被访问,则从未被访问过的顶点中任意选取一个顶点作为新的出发点,反复此过程,直至图中所有顶点均被访问过一遍为止。,A,B,C,F,H,D,G,E,PROC Traverse(g:graph;Var visited:ARRAY vtx OF boolean);For v:=1 To vtxnum Do visited v:=false;For v:=1 To vtxnum Do If Not
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
链接地址:https://www.31ppt.com/p-3787969.html