数据结构第七章幻灯片.ppt

《数据结构第七章幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章幻灯片.ppt（133页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第七章第1页，共133页，编辑于2022年，星期六 图结构图结构：是研究数据元素之间的多对多的关系。在是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。物理、化学、电讯、计算机科学以及数学的其它分支。第2页，共133页，编辑于2022年，星期六7.1 图的基本概念图

2、的基本概念7.1.1图的定义和术语图的定义和术语 一个图一个图(G)定义为一个偶对定义为一个偶对(V,E)，记为，记为G=(V,E)。其中：。其中：V是是顶点顶点(Vertex)的非空有限集合，记为的非空有限集合，记为V(G)；E是无序集是无序集V&V的一个子集，记为的一个子集，记为E(G)，其元素是图的，其元素是图的弧弧(Arc)。将顶点集合为空的图称为空图。其形式化定义为：将顶点集合为空的图称为空图。其形式化定义为：G=(V，E)V=v|v dataobjectE=|v,w Vp(v,w)P(v,w)表示从顶点表示从顶点v到顶点到顶点w有一条直接通路。有一条直接通路。第3页，共133页，编

3、辑于2022年，星期六弧弧(Arc)：表示两个顶点表示两个顶点v和和w之间存在一个关系，用之间存在一个关系，用顶点偶对顶点偶对表示。通常根据图的顶点偶对将图分为有向图和表示。通常根据图的顶点偶对将图分为有向图和无向图。无向图。有向图有向图(Digraph)：若图若图G的关系集合的关系集合E(G)中，顶点中，顶点偶对偶对的的v和和w之间是之间是有序有序的，称图的，称图G是有向图。是有向图。在有向图中，若在有向图中，若 E(G)，表示从顶点，表示从顶点v到顶点到顶点w有有一条一条弧弧。其中：其中：v称为称为弧尾弧尾(tail)或或初始点初始点(initialnode)，w称为称为弧头弧头(head

4、)或或终端点终端点(terminalnode)。无向图无向图(Undigraph)：若图若图G的关系集合的关系集合E(G)中，顶中，顶点偶对点偶对的的v和和w之间是之间是无序无序的，称图的，称图G是无向图。是无向图。第4页，共133页，编辑于2022年，星期六在无向图中，若在无向图中，若 E(G)，有，有 E(G)，即，即E(G)是对称，则用无序对是对称，则用无序对(v,w)表示表示v和和w之间的一条之间的一条边边(Edge)，因此，因此(v,w)和和(w,v)代表的是同一条边。代表的是同一条边。例例1：设有有向图：设有有向图G1和无向图和无向图G2，形式化定义分别是：，形式化定义分别是：G1

5、=(V1，E1)V1=a,b,c,d,eE1=,G2=(V2，E2)V2=a,b,c,dE2=(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)它们所对应的图如图它们所对应的图如图7-1所示。所示。第5页，共133页，编辑于2022年，星期六 完全图完全图：对于对于无向图无向图，若图中顶点数为，若图中顶点数为n，用，用e表示边表示边的数目，则的数目，则e 0，n(n-1)/2。具有。具有n(n-1)/2条边的无向图称条边的无向图称为完全为完全无向无向图。图。完全无向图另外的定义是：完全无向图另外的定义是：对于无向图对于无向图G=(V，E)，若，若 vi，vj V，当，当vi

6、vj时，有时，有(vi,vj)E，即，即图中任意两个不同的顶点间都有一条无向边图中任意两个不同的顶点间都有一条无向边，这，这样的无向图称为样的无向图称为完全图完全图。abcd(b)无向图无向图G2 图图7-1图的示例图的示例(a)有向图有向图G1 acbde第6页，共133页，编辑于2022年，星期六有向完全图有向完全图：对于有向图，若图中顶点数为对于有向图，若图中顶点数为n，用，用e表示弧的数目，则表示弧的数目，则e 0，n(n-1)。具有。具有n(n-1)条边的有向图称条边的有向图称为有向完全图。为有向完全图。完全有向图另外的定义是：完全有向图另外的定义是：对于有向图对于有向图G=(V，E

7、)，若，若 vi，vj V，当，当vivj时，有时，有 E E，即，即图中任意两个不同的顶点间都有一条图中任意两个不同的顶点间都有一条弧弧，这样的有向图称为，这样的有向图称为有向完全图有向完全图。有很少边或弧的图（有很少边或弧的图（enn）的图称为）的图称为稀疏图稀疏图，反之称为，反之称为稠密图稠密图。权权(Weight)：与图的边和弧相关的数。权可以表示从一个与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。顶点到另一个顶点的距离或耗费。第7页，共133页，编辑于2022年，星期六子图和生成子图子图和生成子图：设有图设有图G=(V，E)和和G=(V，E)，若，若V V且且E

8、 E，则称图，则称图G是是G的的子图子图；若；若V=V且且E E，则称图，则称图G是是G的一个的一个生成子图生成子图。顶点的邻接顶点的邻接(Adjacent)：对于无向图对于无向图G=(V，E)，若边若边(v,v)E，则称顶点，则称顶点v和和v互为互为邻接点邻接点，即，即v和和w相邻接。相邻接。边边(v,v)依附依附(incident)与顶点与顶点v和和v。对于有向图对于有向图G=(V，E)，若有向弧，若有向弧 E，则称顶点，则称顶点v“邻接到邻接到”顶点顶点w，顶点，顶点w“邻接自邻接自”顶点顶点v，弧，弧与与顶点顶点v和和w“相关联相关联”。顶点的度、入度、出度顶点的度、入度、出度：对于无

9、向图对于无向图G=(V，E)，vi V，图，图G中中依附依附于于vi的边的数目称为顶点的边的数目称为顶点vi的的度度(degree)，记为记为TD(vi)。第8页，共133页，编辑于2022年，星期六 显然，在无向图中，所有顶点度的和是图中边的显然，在无向图中，所有顶点度的和是图中边的2倍。倍。即即TD(vi)=2ei=1,2,n，e为图的边数。为图的边数。对有向图对有向图G=(V，E)，若，若 vi V，图，图G中中以以vi作为起点作为起点的的有向边有向边(弧弧)的数目称为顶点的数目称为顶点vi的的出度出度(Outdegree)，记为，记为OD(vi)；以以vi作为终点作为终点的有向边的有向

10、边(弧弧)的数目称为顶点的数目称为顶点vi的的入度入度(Indegree)，记为，记为ID(vi)。顶点。顶点vi的的出度出度与与入度入度之和称为之和称为vi的的度度，记为，记为TD(vi)。即。即TD(vi)=OD(vi)+ID(vi)路径路径(Path)、路径长度、回路、路径长度、回路(Cycle)：对无向对无向图图G=(V，E)，若从顶点，若从顶点vi经过若干条边能到达经过若干条边能到达vj，称顶点，称顶点vi和和vj是是连通连通的，又称顶点的，又称顶点vi到到vj有有路径路径。对有向图对有向图G=(V，E)，从顶点，从顶点vi到到vj有有有向路径有向路径，指的是从，指的是从顶点顶点vi

11、经过若干条有向边经过若干条有向边(弧弧)能到达能到达vj。第9页，共133页，编辑于2022年，星期六或或路径路径是图是图G中连接两顶点之间所经过的顶点序列。即中连接两顶点之间所经过的顶点序列。即Path=vi0vi1vim，vij V且且(vij-1,vij)Ej=1,2,m或或Path=vi0vi1vim，vij V且且 Ej=1,2,m路径上边或有向边路径上边或有向边(弧弧)的数目称为该的数目称为该路径路径的的长度长度。在一条路径中，若在一条路径中，若没有重复相同没有重复相同的顶点，该路径称为的顶点，该路径称为简单路简单路径径；第一个顶点和最后一个顶点相同的路径称为；第一个顶点和最后一个

12、顶点相同的路径称为回路回路(环环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为不重复出现的回路称为简单回路简单回路(简单环简单环)。第10页，共133页，编辑于2022年，星期六连通图、图的连通分量连通图、图的连通分量：对无向图对无向图G=(V，E)，若，若 vi，vj V，vi和和vj都是连通的，则称图都是连通的，则称图G是是连通图连通图，否则称，否则称为为非连通图非连通图。若。若G是非连通图，则是非连通图，则极大的连通子图极大的连通子图称为称为G的的连通分量连通分量。对有向图对有向图G=(V，E)，若，若 vi

13、，vj V，都有，都有以以vi为起点为起点，vj为终点为终点以及以以及以vj为起点，为起点，vi为终点的有向路径，称图为终点的有向路径，称图G是是强强连通图连通图，否则称为，否则称为非强连通图非强连通图。若。若G是非强连通图，则是非强连通图，则极大极大的强连通子图的强连通子图称为称为G的的强连通分量强连通分量。“极大极大”的含义：指的是对子图再增加图的含义：指的是对子图再增加图G中的其它顶点，中的其它顶点，子图就不再连通。子图就不再连通。第11页，共133页，编辑于2022年，星期六生成树、生成森林生成树、生成森林：一个连通图一个连通图(无向图无向图)的生成树的生成树是一个极小连通子图，它是一

14、个极小连通子图，它含有图中全部含有图中全部n个顶点个顶点和只有足以构和只有足以构成一棵树的成一棵树的n-1条边条边，称为图的，称为图的生成树生成树，如图，如图7-2所示。所示。关于无向图的生成树的几个结论：关于无向图的生成树的几个结论：一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1条边；条边；如果一个图有如果一个图有n个顶点和小于个顶点和小于n-1条边，则是非连条边，则是非连通图；通图；adbc图图7-2图图G2的一棵生成树的一棵生成树如果多于如果多于n-1条边，则一定有环；条边，则一定有环；有有n-1条边的图不一定是生成树。条边的图不一定是生成树。第12页，共133页，编辑

15、于2022年，星期六 有向图的有向图的生成森林生成森林是这样一个子图，由若干棵是这样一个子图，由若干棵有向树有向树组组成，含有图中全部顶点。成，含有图中全部顶点。有向树有向树是只有一个顶点的入度为是只有一个顶点的入度为0，其余顶点的入度均为，其余顶点的入度均为1的的有向图，如图有向图，如图7-3所示。所示。网网：每个边每个边(或弧或弧)都附加一个权值的图，称为都附加一个权值的图，称为带权图带权图。带权的连通图带权的连通图(包括弱连通的有向图包括弱连通的有向图)称为称为网或网络网或网络。网络是。网络是工程上常用的一个概念，用来表示一个工程或某种流程，工程上常用的一个概念，用来表示一个工程或某种流

16、程，如图如图7-4所示。所示。图图7-3有向图及其生成森林有向图及其生成森林abcdedce(a)有向图有向图(b)生成森林生成森林acbcb354126abcde3图图7-4带权有向图带权有向图第13页，共133页，编辑于2022年，星期六7.1.2 图的抽象数据类型定义图的抽象数据类型定义 图是一种数据结构，加上一组基本操作就构成了图的抽象图是一种数据结构，加上一组基本操作就构成了图的抽象数据类型。数据类型。图的抽象数据类型定义如下：图的抽象数据类型定义如下：ADTGraph数据对象数据对象V：具有相同特性的数据元素的集合，称为顶：具有相同特性的数据元素的集合，称为顶点集点集。数据关系数据

17、关系R：R=VRVR=|v,w Vp(v,w)，表示表示从从v到到w的弧，的弧，P(v,w)定义了弧定义了弧的信息的信息第14页，共133页，编辑于2022年，星期六基本操作基本操作P：Create_Graph()：图的创建操作图的创建操作。初始条件：无。初始条件：无。操作结果：生成一个没有顶点的空图操作结果：生成一个没有顶点的空图G。GetVex(G,v)：求图中的顶点求图中的顶点v的值。的值。初始条件：图初始条件：图G存在，存在，v是图中的一个顶点。是图中的一个顶点。操作结果：生成一个没有顶点的空图操作结果：生成一个没有顶点的空图G。DFStraver(G,V)：从：从v出发对图出发对图G

18、深度优先遍历。深度优先遍历。初始条件：图初始条件：图G存在。存在。操作结果：对图操作结果：对图G深度优先遍历，每个顶点访问且只访深度优先遍历，每个顶点访问且只访问一次。问一次。第15页，共133页，编辑于2022年，星期六 BFStraver(G,V)：从：从v出发对图出发对图G广度优先遍历。广度优先遍历。初始条件：图初始条件：图G存在。存在。操作结果：对图操作结果：对图G广度优先遍历，每个顶点访问且只广度优先遍历，每个顶点访问且只访问一次。访问一次。ADTGraph详见详见p156157。第16页，共133页，编辑于2022年，星期六7.2 图的存储结构图的存储结构 图的存储结构比较复杂，其

19、复杂性主要表现在：图的存储结构比较复杂，其复杂性主要表现在：任意顶点之间可能存在联系，无法以数据元素任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。在存储区中的物理位置来表示元素之间的关系。图中顶点的度不一样，有的可能相差很大，若图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又元，反之按每个顶点自己的度设计不同的结构，又会影响操作。会影响操作。图的常用的存储结构有：图的常用的存储结构有：邻接矩阵邻接矩阵、邻接链表邻接链表、十字链十字链表表

20、、邻接多重表邻接多重表。第17页，共133页，编辑于2022年，星期六7.2.1邻接矩阵邻接矩阵(数组数组)表示法表示法基本思想基本思想：对于有对于有n个顶点的图，用一维数组个顶点的图，用一维数组vexsn存储顶点信息，用二维数组存储顶点信息，用二维数组Ann存储顶点之间关系的信息。存储顶点之间关系的信息。该二维数组称为该二维数组称为邻接矩阵邻接矩阵。在邻接矩阵中，以顶点在。在邻接矩阵中，以顶点在vexs数组数组中的下标代表顶点，邻接矩阵中的元素中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶存放的是顶点点i到顶点到顶点j之间关系的信息。之间关系的信息。第18页，共133页，编辑于2022年

21、，星期六1无向图的数组表示无向图的数组表示(1)无权图的邻接矩阵无权图的邻接矩阵 无向无权图无向无权图G=(V，E)有有n(n1)个顶点，其邻接矩阵是个顶点，其邻接矩阵是n阶对称方阵，如图阶对称方阵，如图7-5所示。其元素的定义如下：所示。其元素的定义如下：1若若(vi,vj)E，即，即vi,vj邻接邻接0若若(vi,vj)E，即，即vi,vj不邻接不邻接Aij=(a)无向图无向图 abcd图图7-5无向无权图的数组存储无向无权图的数组存储(b)顶点矩阵顶点矩阵vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c)邻接矩阵邻接矩阵第19页，共133页，编辑于2022年，

22、星期六(2)带权图的邻接矩阵带权图的邻接矩阵 无向带权图无向带权图G=(V，E)的邻接矩阵如图的邻接矩阵如图7-6所示。其元素的所示。其元素的定义如下：定义如下：(a)带权无向图带权无向图(b)顶点矩阵顶点矩阵图图7-6无向带权图的数组存储无向带权图的数组存储(c)邻接矩阵邻接矩阵354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij若若(vi,vj)E，即，即vi,vj邻接，权值为邻接，权值为wij 若若(vi,vj)E，即，即vi,vj不邻接时不邻接时Aij=第20页，共133页，编辑于2022年，星期六(3)无向图邻接矩阵的特性无向图邻接

23、矩阵的特性 邻接矩阵是邻接矩阵是对称方阵对称方阵；对于顶点对于顶点vi，其，其度数度数是第是第i行的非行的非0元素的个数；元素的个数；无向图的无向图的边数边数是上是上(或下或下)三角形矩阵中非三角形矩阵中非0元素个数。元素个数。2有向图的数组表示有向图的数组表示(1)无权图的邻接矩阵无权图的邻接矩阵 若有向无权图若有向无权图G=(V，E)有有n(n1)个顶点，则其邻接矩个顶点，则其邻接矩阵是阵是n阶对称方阵阶对称方阵，如图，如图7-7所示。元素定义如下：所示。元素定义如下：1若若 E，从，从vi到到vj有弧有弧Aij=0若若 E从从vi到到vj没有弧没有弧第21页，共133页，编辑于2022年

24、，星期六(a)有向图有向图acbde图图7-7有向无权图的数组存储有向无权图的数组存储(b)顶点矩阵顶点矩阵vexsabcde(c)邻接矩阵邻接矩阵0 1 1 0 10 0 0 0 00 0 0 1 11 1 0 0 00 0 0 1 0(2)带权图的邻接矩阵带权图的邻接矩阵 有向带权图有向带权图G=(V，E)的邻接矩阵如图的邻接矩阵如图7-8所示。其元素所示。其元素的定义如下：的定义如下：wij若若 E，即，即vi,vj邻接，权值为邻接，权值为wij 若若 E，即，即vi,vj不邻接时不邻接时Aij=第22页，共133页，编辑于2022年，星期六图图7-8带权有向图的数组存储带权有向图的数组

25、存储(b)顶点矩阵顶点矩阵vexsabcde(c)邻接矩阵邻接矩阵 6 2 3 3 1 4 5 (a)带权有向图带权有向图 354126abcde3 有向图邻接矩阵的特性有向图邻接矩阵的特性 对于顶点对于顶点vi，第，第i行的非行的非0元素的个数是其元素的个数是其出度出度OD(vi)；第第i列的非列的非0元素的个数是其元素的个数是其入度入度ID(vi)。邻接矩阵中非邻接矩阵中非0元素的个数就是图的弧的数目。元素的个数就是图的弧的数目。第23页，共133页，编辑于2022年，星期六3图的邻接矩阵的操作图的邻接矩阵的操作 图的邻接矩阵的实现比较容易，定义两个数组分别存储图的邻接矩阵的实现比较容易，

26、定义两个数组分别存储顶点信息顶点信息(数据元素数据元素)和和边或弧的信息边或弧的信息(数据元素之间的关系数据元素之间的关系)。其其存储结构形式定义存储结构形式定义如下：如下：#defineINFINITYMAX_VAL/*最大值最大值*/*根据图的权值类型，分别定义为最大整数或实数根据图的权值类型，分别定义为最大整数或实数*/#defineMAX_VEX30/*最大顶点数目最大顶点数目*/typedefenumDG,AG,WDG,WAGGraphKind;/*有向图，无向图，带权有向图，带权无向图有向图，无向图，带权有向图，带权无向图*/第24页，共133页，编辑于2022年，星期六#defi

27、neVEX_NUM20typedefcharVextype；typedefstructVextypevexsVEX_NUM;intadjVEX_NUMVEX_NUM;/*邻接矩阵邻接矩阵*/intn,e;/*顶点数和边数顶点数和边数*/Mgragh;第25页，共133页，编辑于2022年，星期六lvoidCreateMGraph(Mgragh*G)linti,j,k,w;charch;lprintf(请输入顶点数和边数请输入顶点数和边数:n);lscanf(%d,%d,&(G-n),&(G-e);/*输入输入*/lprintf(请输入顶点信息请输入顶点信息:n);lfor(i=0;in;i+)

28、scanf(%c,&(G-vexsi);for(i=0;in;i+)for(j=0;jn;j+)lG-adjij=0;/*初始化邻接矩阵初始化邻接矩阵*/printf(输入每条边对应的两个顶点的序号输入每条边对应的两个顶点的序号:n);for(k=0;ke;k+)scanf(%d,%d,&i,&j);/*输入输入e条边条边*/G-adjij=1;lG-adjji=1;/*对对称加入称加入,无向图的邻接矩阵存储建立无向图的邻接矩阵存储建立*/l/*CreateMGraph*/第26页，共133页，编辑于2022年，星期六7.2.2 邻接链表法邻接链表法 基本思想：基本思想：对图的每个顶点建立一个

29、单链表，存储该顶对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第第i个单链表表示依附于顶点个单链表表示依附于顶点Vi的边的边(对有向图是以顶点对有向图是以顶点Vi为头或尾的弧为头或尾的弧)。第27页，共133页，编辑于2022年，星期六1结点结构与邻接链表示例结点结构与邻接链表示例 链表中的结点称为链表中的结点称为表结点表结点，每个结点由三个域组成，如，每个结点由三个域组成，如图图7-9(a)所示。其中邻接点域所示。其中邻接点域(adjvex)指示与顶点指示与顶点Vi邻接的顶邻接的顶点在图中

30、的位置点在图中的位置(顶点编号顶点编号)，链域，链域(nextarc)指向下一个与顶点指向下一个与顶点Vi邻接的表结点，数据域邻接的表结点，数据域(info)存储和边或弧相关的信息，存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。省略此域。每个链表设一个表头结点每个链表设一个表头结点(称为称为顶点结点顶点结点)，由两个域组成，由两个域组成，如图如图7-9(b)所示。链域所示。链域(firstarc)指向链表中的第一个结点，指向链表中的第一个结点，数据域数据域(data)存储顶点名或其他信息。存储顶点名或其

31、他信息。adjvexnextarcinfo表结点表结点：datafirstarc顶点结点顶点结点：图图7-9邻接链表结点结构邻接链表结点结构第28页，共133页，编辑于2022年，星期六在图的邻接链表表示中，所有在图的邻接链表表示中，所有顶点结点顶点结点用一个向量用一个向量以以顺序结构形式存储，可以随机访问任意顶点的链表，该向量顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为称为表头向量表头向量，向量的下标指示顶点的序号。，向量的下标指示顶点的序号。用邻接链表存储图时，对无向图，其邻接链表是唯一的，用邻接链表存储图时，对无向图，其邻接链表是唯一的，如图如图7-10所示；对有向图，其邻接

32、链表有两种形式，如图所示；对有向图，其邻接链表有两种形式，如图7-11所示。所示。图图7-10无向图及其邻接链表无向图及其邻接链表v1v2v3v4v501234MAX_VEX-1v1v2v3v4 v521302031420423第29页，共133页，编辑于2022年，星期六(a)有向图有向图v1v2v3v4v5130142301234MAX_VEX-1v12v20v33v41 v51(b)正邻接链表，出度直观正邻接链表，出度直观202201234MAX_VEX-1v11v22v31v42 v51304(c)逆邻接链表，入度直观逆邻接链表，入度直观图图7-11有向图及其邻接链表有向图及其邻接链表

33、第30页，共133页，编辑于2022年，星期六2邻接表法的特点邻接表法的特点表头向量中每个分量就是一个单链表的头结点，表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；分量个数就是图中的顶点数目；在边或弧稀疏的条件下，用邻接表表示比用邻接在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；矩阵表示节省存储空间；在无向图，顶点在无向图，顶点Vi的度是第的度是第i个链表的结点数；个链表的结点数；对对有向图有向图可以建立可以建立正邻接表正邻接表或或逆邻接表逆邻接表。正邻接。正邻接表是以顶点表是以顶点Vi为出度为出度(即为弧的起点即为弧的起点)而建立的邻接而建立的邻接表

34、；逆邻接表是以顶点表；逆邻接表是以顶点Vi为入度为入度(即为弧的终点即为弧的终点)而而建立的邻接表；建立的邻接表；在有向图中，第在有向图中，第i个链表中的结点数是顶点个链表中的结点数是顶点Vi的的出出(或入或入)度；求入度；求入(或出或出)度，须遍历整个邻接表；度，须遍历整个邻接表；第31页，共133页，编辑于2022年，星期六 在邻接表上容易找出任一顶点的第一个邻接点和在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；下一个邻接点；3结点及其类型定义结点及其类型定义typedefstructnode/*边结点边结点*/intadjvex;/*邻接点域邻接点域*/structnode*n

35、extarc;/*指向下一个边结点的指针域指向下一个边结点的指针域*/EdgeNode;typedefstructvnodeVextypevertex;EdgeNode*firstedge;VertexNode;typedefstructVertexNodeadjlistMAXSIZE;intn,e;ALGraph;第32页，共133页，编辑于2022年，星期六利用上述的存储结构描述，可方便地实现图的基本操作。利用上述的存储结构描述，可方便地实现图的基本操作。图的创建图的创建voidCreateALGraph(ALGraph*G)/*建立有向图的邻接表存储建立有向图的邻接表存储*/inti,j

36、,k;EdgeNode*s;printf(“请输入顶点数和边数：请输入顶点数和边数：n”);scanf(“%d,%d”,&(G-n),&(G-e);第33页，共133页，编辑于2022年，星期六printf(“请输入顶点信息：请输入顶点信息：n”);for(i=0;in;i+)scanf(“%c”,&(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;printf(“请输入边的信息：请输入边的信息：n”);for(k=0;ke;k+)/*建立边表建立边表*/scanf(“%d,%d”,&i,&j);/在在头结头结点和点和边结边结点之点之间间插入插入新的新

37、的边结边结点点s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=j;s-nextarc=G-adjlisti.firstedge;G-adjlisti.firstedge=s;/*CreateALGraph*/第34页，共133页，编辑于2022年，星期六7.2.3 十字链表法十字链表法十字链表十字链表(OrthogonalList)是有向图的另一种链是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。到的一种链表。在这种结构中，每条弧的弧头结点和弧尾结点都存放在在这种

38、结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将链表中，并将弧结点弧结点分别组织到分别组织到以弧尾结点为头以弧尾结点为头(顶点顶点)结点结点和和以弧头结点为头以弧头结点为头(顶点顶点)结点结点的链表中。这种结构的结点逻的链表中。这种结构的结点逻辑结构如图辑结构如图7-12所示。所示。弧结点弧结点tailvex headvex hlink tlink info顶点结点顶点结点Data firstin firstout图图7-12十字链表结点结构十字链表结点结构第35页，共133页，编辑于2022年，星期六data域：存储和顶点相关的信息；域：存储和顶点相关的信息；指针域指针域firstin

39、：指向：指向以该顶点为弧头以该顶点为弧头的第一条弧所对应的第一条弧所对应的弧结点；的弧结点；指针域指针域firstout：指向：指向以该顶点为弧尾以该顶点为弧尾的第一条弧所对应的第一条弧所对应的弧结点；的弧结点；尾域尾域tailvex：指示弧尾顶点在图中的位置；：指示弧尾顶点在图中的位置；头域头域headvex：指示弧头顶点在图中的位置；：指示弧头顶点在图中的位置；指针域指针域hlink：指向弧头相同的下一条弧；：指向弧头相同的下一条弧；指针域指针域tlink：指向弧尾相同的下一条弧；：指向弧尾相同的下一条弧；Info域：指向该弧的相关信息；域：指向该弧的相关信息；第36页，共133页，编辑于

40、2022年，星期六结点类型定义结点类型定义#defineINFINITYMAX_VAL/*最大值最大值*/#defineMAX_VEX30/最大顶点数最大顶点数typedefstructArcNodeinttailvex,headvex;/尾结点和头结点在图中的位置尾结点和头结点在图中的位置InfoTypeinfo;/与弧相关的信息与弧相关的信息,如权值如权值structArcNode*hlink,*tlink;ArcNode;/*弧结点类型定义弧结点类型定义*/typedefstructVexNodeVexTypedata;/顶点信息顶点信息ArcNode*firstin,*firstout

41、;VexNode;/*顶点结点类型定义顶点结点类型定义*/第37页，共133页，编辑于2022年，星期六typedefstructintvexnum;VexNodexlistMAX_VEX;OLGraph;/*图的类型定义图的类型定义*/图图7-13所示是一个有向图及其十字链表所示是一个有向图及其十字链表(略去了表结点的略去了表结点的info域域)。从这种存储结构图可以看出，从一个顶点结点的从这种存储结构图可以看出，从一个顶点结点的firstout出发，沿表结点的出发，沿表结点的tlink指针构成了正邻接表的链表结指针构成了正邻接表的链表结构，而从一个顶点结点的构，而从一个顶点结点的first

42、in出发，沿表结点的出发，沿表结点的hlink指针指针构成了逆邻接表的链表结构。构成了逆邻接表的链表结构。第38页，共133页，编辑于2022年，星期六V0V1V2V30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3图图7-13有向图的十字链表结构有向图的十字链表结构第39页，共133页，编辑于2022年，星期六7.2.4 邻接多重表邻接多重表邻接多重表邻接多重表(AdjacencyMultilist)是无向图的另一是无向图的另一种链式存储结构。种链式存储结构。邻接表是无向图的一种有效的存储结构，在无向图的邻邻接表是无向图的一种有效的存储结构，在无向图的邻接表中，

43、一条边接表中，一条边(v,w)的两个表结点分别初选在以的两个表结点分别初选在以v和和w为头为头结点的链表中，很容易求得顶点和边的信息，但在涉及到结点的链表中，很容易求得顶点和边的信息，但在涉及到边的操作会带来不便。边的操作会带来不便。邻接多重表的结构和十字链表类似，邻接多重表的结构和十字链表类似，每条边用一个结点每条边用一个结点表示表示；邻接多重表中的顶点结点结构与邻接表中的完全相同，；邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点包括六个域如图而表结点包括六个域如图7-14所示。所示。datafirstedge顶点结点顶点结点图图7-14邻接多重表的结点结构邻接多重表的结点结构表结

44、点表结点markivexilinkjvexjlinkinfo第40页，共133页，编辑于2022年，星期六Data域：存储和顶点相关的信息；域：存储和顶点相关的信息；指针域指针域firstedge：指向依附于该顶点的第一条边所对：指向依附于该顶点的第一条边所对应的表结点；应的表结点；标志域标志域mark：用以标识该条边是否被访问过；：用以标识该条边是否被访问过；ivex和和jvex域：分别保存该边所依附的两个顶点在图域：分别保存该边所依附的两个顶点在图中的位置；中的位置；info域：保存该边的相关信息；域：保存该边的相关信息；指针域指针域ilink：指向下一条依附于顶点：指向下一条依附于顶点i

45、vex的边；的边；指针域指针域jlink：指向下一条依附于顶点：指向下一条依附于顶点jvex的边；的边；第41页，共133页，编辑于2022年，星期六结点类型定义结点类型定义#defineINFINITYMAX_VAL/*最大值最大值*/#defineMAX_VEX30/*最大顶点数最大顶点数*/typedefemnuunvisited,visitedVisitting;typedefstructEdgeNodeVisittingmark;/访问标记访问标记intivex,jvex;/该边依附的两个结点在图中的位置该边依附的两个结点在图中的位置InfoTypeinfo;/与边相关的信息与边相关

46、的信息,如权值如权值structEdgeNode*ilink,*jlink;/分别指向依附于这两个顶点的下一条边分别指向依附于这两个顶点的下一条边EdgeNode;/*弧边结点类型定义弧边结点类型定义*/第42页，共133页，编辑于2022年，星期六typedefstructVexNodeVexTypedata;/顶点信息顶点信息ArcNode*firsedge;/指向依附于该顶点的第一条边指向依附于该顶点的第一条边VexNode;/*顶点结点类型定义顶点结点类型定义*/typedefstructintvexnum;VexNodemullistMAX_VEX;AMGraph;图图7-15所示是

47、一个无向图及其邻接多重表。所示是一个无向图及其邻接多重表。第43页，共133页，编辑于2022年，星期六邻接多重表与邻接表的区别邻接多重表与邻接表的区别：后者的同一条边用两个表结点表示，而前者只用一个表后者的同一条边用两个表结点表示，而前者只用一个表结点表示结点表示；除标志域外，邻接多重表与邻接表表达的信息除标志域外，邻接多重表与邻接表表达的信息是相同的，因此，操作的实现也基本相似。是相同的，因此，操作的实现也基本相似。图图7-15无向图及其多重邻接链表无向图及其多重邻接链表v1v2v3v4v1v2v3v40123 0 1 0 2 2 1 2 3 0 3第44页，共133页，编辑于2022年，

48、星期六7.3 图的遍历图的遍历 图的遍历图的遍历(TraveringGraph)：从图的某一顶点出从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的操作的基础。算法是各种图的操作的基础。复杂性：复杂性：图的任意顶点可能和其余的顶点相邻图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。又回到原顶点。解决办法：解决办法：在遍历过程中记下已被访问过的顶在遍历过程中记下已被访问过的顶点。设置一个辅助向量点。设置一个辅助向量Vis

49、ited1n(n为顶点数为顶点数)，其初值为其初值为0，一旦访问了顶点，一旦访问了顶点vi后，使后，使Visitedi为为1或或为访问的次序号为访问的次序号。图的遍历算法有图的遍历算法有深度优先搜索算法深度优先搜索算法和和广度优先搜索算法广度优先搜索算法。采用的数据结构是采用的数据结构是(正正)邻接链表邻接链表。第45页，共133页，编辑于2022年，星期六7.3.1深度优先搜索算法深度优先搜索算法 深度优先搜索深度优先搜索(DepthFirstSearch-DFS)遍历类遍历类似似树的先序遍历树的先序遍历，是，是树的先序遍历的推广树的先序遍历的推广。1 算法思想算法思想设初始状态时图中的所有

50、顶点未被访问，则：设初始状态时图中的所有顶点未被访问，则：从图中某个顶点从图中某个顶点vi出发出发，访问，访问vi；然后找到；然后找到vi的的一个邻接顶点一个邻接顶点vi1；：从：从vi1出发，深度优先搜索访问和出发，深度优先搜索访问和vi1相相邻接且未邻接且未被访问的所有顶点；被访问的所有顶点；：转：转，直到和，直到和vi相相邻接的所有顶点都被访问为邻接的所有顶点都被访问为止止 第46页，共133页，编辑于2022年，星期六图图7-17无向图深度优先搜索遍历无向图深度优先搜索遍历(a)无向图无向图Gv1v2v3v4v5(b)G的邻接链表的邻接链表01234MAX_VEX-1v1v2v3v4