数据结构7图.ppt

《数据结构7图.ppt》由会员分享，可在线阅读，更多相关《数据结构7图.ppt（40页珍藏版）》请在优知文库上搜索。

1、第七章. 图 （Chapter 7. Graph)7.1 图的定义及基本操作 图型结构是一种非常重要的、比线性和树型结构更复杂的非线性数据结构，可广泛用于描述自然界各种关系。右图所示即为一图型结构：ABCEFDGraph = （V,R）其中：V= ai | aiD0, i=1,2,n, n0 R= E E= | P(x, y)（x, yV) 其中 D0 为某一数据对象， V 为顶点集，E 为边集。图的一些基本术语：图的一些基本术语：顶点（顶点（vertex）数据元素所构成的结点通常称为顶点。弧（弧（arc）若两个顶点间有关系 E ，则称 为一条弧。弧头（弧头（head-又称终端点又称终端点 t

2、erminal node）若 为一条弧，则顶点 y 称为弧头。弧尾（弧尾（tail-又称初始点又称初始点 initial node）若 为一条弧，则顶点 x 称为弧尾。有向图（有向图（directed graph）若 E ，并不总有 E，则称此图为有向图。无向图（无向图（undirected graph）若 E ，总有 E，则称此图为无向图。边（边（edge）无向图中两条弧和可用一条边（ x,y ）来表示 。完全图（完全图（completed graph）具有 n*(n-1)/2 条边的无向图称为完全图。有向完全图（有向完全图（completed directed graph）具有 n*(n-

3、1) 条弧的有向图称为有向完全图。稀疏图（稀疏图（sparse graph）边数很少的图称为稀疏图。权（权（weight）有些图的边或弧具有一定的大小，称之为权。网（网（network）带权值的图又称为网或网络。子图（子图（subgraph）由图的部分顶点和边组成的新图称为原图的子图。生成子图（生成子图（spanning subgraph）由图的全部顶点和部分边组成的子图称为原图的生成子图。稠密图（稠密图（dense graph）边数很多的图称为稠密图。邻接点（邻接点（adjacent）若边（vi,vj） E，则 vi 与 vj 互为邻接点。依附（依附（incident）若边（vi,vj） E

4、，则称边（vi,vj）依附于顶点 vi 和 vj 。相关联（相关联（correlative）若边（vi,vj） E，又称边（vi,vj）与顶点 vi 和 vj 相关联。顶点的度（顶点的度（degree）与顶点相关联的边数称为该顶点的度，又分为入度和出度 。顶点的入度（顶点的入度（indegree）以顶点为头的弧数称为该顶点的入度 。顶点的出度（顶点的出度（outdegree）以顶点为尾的弧数称为该顶点的出度 。路径（路径（path）由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。回路（回路（loop-又称环又称环 cycle）起点和终点为同一顶点的路径称为回路。连通（连通（conne

5、cted）无向图中顶点vi到vj间有路径存在，则称vi和vj是连通的。连通图（连通图（connected graph）无向图中任意两顶点间均存在路径，则称该图为连通图。连通分量（连通分量（connected component）无向图中的极大连通子图称为原图的连通分量。强连通图（强连通图（strongly connected graph）有向图中任意两顶点间均存在路径，则称该图为强连通图。强连通分量（强连通分量（strongly connected component）有向图中的极大强连通子图称为原图的强连通分量。生成树（生成树（spanning tree）连通图的极小连通生成子图称为原图的生

6、成树。有向树（有向树（directed tree）恰有一个顶点入度为0 ，其余顶点入度均为1的有向图。生成森林（生成森林（spanning forest）由多棵有向树构成的有向图的生成子图称为生成森林。最小代价生成树（最小代价生成树（minimum cost spanning tree）连通网中由最小权值的边构成的生成树。图的基本操作图的基本操作：INITIATEGETVERTEXFIRSTADJNEXTADJINSVERTEXTRAVERSEINSARCDELVERTEXDELARC7.2 图的存储结构顺序存储结构：顺序存储结构：ABCEFD1、邻接矩阵（、邻接矩阵（adjacency ma

7、trix)A B C D E F0 0 0 0 0 11 0 1 0 0 00 0 0 1 0 00 0 0 0 1 00 1 0 0 0 00 0 0 0 1 0ABCDEFAij =0 (vi,vj) E1 (vi,vj) ECONST vtxnum = user_supply;TYPE vtx = 1 . vtxnum; bit = 0 . 1; graph = ARRAY vtx , vtx OF bit; 2、关联矩阵（、关联矩阵（ correlated matrix)Bij =1 vi 是是 ej 的弧头的弧头0 vi 与与 ej 不相关联不相关联-1 vi 是是 ej 的弧尾的弧

8、尾ABCEFDe1e2e3e4e5e6e7e1 e2 e3 e4 e5 e6 e7 1 0 0 0 0 0 -1-1 -1 0 0 1 0 0 0 1 -1 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 1 -1 1 0 0 0 0 0 0 -1 1ABCDEFCONST vtxnum = user_supply; edgenum = user_supply;TYPE vtx = 1. vtxnum; edge = 1. edgenum; bit = -1. 1; graph = ARRAY vtx , edge OF bit; 链式存储结构：链式存储结构：1、邻接表（、邻接表（a

9、djacency list)ABCEFD6 A12 E51B234 C35 D4F65 firstarcvexdata头结点头结点adjvex infonextarc弧结点弧结点按结点出度建立：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

10、adjacency list)firstarcvexdata头结点头结点adjvex infonextarc弧结点弧结点按结点入度建立：ABCEFD2312341E5B2C3D4F63 12A122A125 32 31 14 26 4定义同邻接表ABCEFD3、十字链表（、十字链表（orthogonal list)按结点入度和出度建立：firstoutdata头结点头结点firstintailvex headvex hlink弧结点弧结点tlinkD445A11 6B22 123 E552 F665 C334 TYPE arclk = anode; vnode = RECORD data :

11、vextype; firstin , firstout : arclk END; anode = RECORD tailvex , headvex : vtx; hlink , tlink : arclk END; ortholist =ARRAY vtx OF vnode; ABCEFD4、邻接多重表（、邻接多重表（adjacency multilist)邻接多重表是无向图的一种存储结构：TYPE edgelk = enode; vnode = RECORD data : vextype; firstedge : arclk END; enode = RECORD mark : 0 . 1;

12、 ivex, jvex : vtx; ilink , jlink : edgelk END; adjmulist =ARRAYvtx OF vnode; data头结点头结点firstedgemark ivex边结点边结点ilink jvex jlinkD4A1B26 1E5F6C312233 44 55 62 523ABCEFDGH7.3 图的遍历深度优先遍历（深度优先遍历（depth_first search）即按某种搜索顺序对图中每个结点访问且仅访问一次。 从图中某一顶点 v0 出发，访问该顶点，并依次从v0的所有未被访问过的邻接点中任意选取一个顶点作为新的出发点，用同样的方法访问其它所

13、有顶点，直到所有与v0 连通的顶点均被访问到为止；若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点，反复此过程，直至图中所有顶点均被访问过一遍为止。ABCDGFEHA BFEH C D GPROC 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 visitedv Then dfs ( g , v )ENDP;PROC dfs ( g : graph; v :

14、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;ABCEFDGH广度优先遍历（广度优先遍历（breadth_first search） 从图中某一顶点v0出发，访问该顶点，并依次访问v0的所有未被访问过的邻接点，然后将所有这些邻接点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0 连通的顶点均被访问到为止；若此时仍有顶点尚未被访问，则从未被

15、访问过的顶点中任意选取一个顶点作为新的出发点，反复此过程，直至图中所有顶点均被访问过一遍为止。ABCDGFEHA BC FH D G EPROC 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 visitedv Then bfs ( g , v )ENDP;PROC bfs ( g : graph; v : vtx ); visit ( v ); visited v:=true; INIQ

16、UEUE(Q); ENQUEUE(Q, v); While Not EMPTY(Q) Do Begin v:= DEQUEUE(Q); w:=FIRSTADJ ( g , v ); While w0 Do 【 If Not visited w Then 【 visit ( w); visited w:=true; ENQUEUE(Q,w) 】; w:= NEXTADJ ( g , v , w) 】 EndENDP;作作 业业20. 自选存储结构，编写一算法判断无自选存储结构，编写一算法判断无向图中任意给定的两个顶点间是否存在向图中任意给定的两个顶点间是否存在一条长度为一条长度为 k 的简单路径（的简单路径（ 即不含回即不含回路的路径）。路的路径）。21. 自选存储结构，试给出求有向图中自选存储结构，试给出求有向图中所有简单回路（即其中不再含有回路的所有简单回路（即其中不再含有回路的回路）的算法。回路）的算法。7.4 图的连通性及最小代价生成树无向图的连通分量：无向图的连通分量： 一次调用深度或广度优先搜索（dfs、bfs）所得到的顶点集即为连通分量的顶点集。有向图的强连通分量：有向图的