图及其应用(new).ppt

《图及其应用(new).ppt》由会员分享，可在线阅读，更多相关《图及其应用(new).ppt（204页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图及其应用图及其应用(new)第第10章章 图及其应用图及其应用 2 图图图图(Graph)(Graph)：是一种网状数据结构。是顶点集：是一种网状数据结构。是顶点集V和连和连接这些顶点的弧集接这些顶点的弧集(边集边集)VR所组成的结构记为所组成的结构记为:G=(V,VR）有向图：有向图：有向图：有向图：若若图中的边是顶点的有序对图中的边是顶点的有序对图中的边是顶点的有序对图中的边是顶点的有序对,则称此图为则称此图为有向图。有向图。有向边又称为弧有向边又称为弧有向边又称为弧有向边又称为弧,通常用尖括弧表示一条有向通常用尖括弧表示一条有向边边,vi,vj表示从顶点表示从顶点vi到到vj的一段弧的

2、一段弧,vi称为边的始点称为边的始点(或弧尾或弧尾),vj称为边的终点称为边的终点(或弧头或弧头),vi,vj和和 vj,vi代表两条不同的弧。代表两条不同的弧。132第第10章章 图及其应用图及其应用 3无无无无向向向向图图图图：若若图图图图中中中中的的的的边边边边是是是是顶顶顶顶点点点点的的的的无无无无序序序序对对对对,则则称称此此图图为为无向图。无向图。通通常常用用圆圆圆圆括括括括号号号号表表表表示示示示无无无无向向向向边边边边,(vi,vj)表表示示顶顶点点vi和和vj间间相连的边。在无向图中相连的边。在无向图中(vi,vj)和和(vj,vi)表示同一条边表示同一条边.2341第第10

3、章章 图及其应用图及其应用 4完全图、稠密图、稀疏图完全图、稠密图、稀疏图完全图、稠密图、稀疏图完全图、稠密图、稀疏图 具具有有n个个顶顶点点，n(n-1)/2条条边边的的图图，称称为为完完完完全全全全无无无无向向向向图图图图，具具有有n个个顶顶点点，n(n-1)条条弧弧的的有有向向图图,称称为为完完完完全全全全有有有有向向向向图图图图。完全无向图和完全有向图都称为完全无向图和完全有向图都称为完全图完全图完全图完全图。对对于于一一般般无无向向图图，顶顶点点数数为为n，边边数数为为e，则则 0e n(n-1)/2。对对于于一一般般有有向向图图，顶顶点点数数为为n，弧弧数数为为e，则则 0en(n

4、-1)。当当一一个个图图接接近近完完全全图图时时，则则称称它它为为稠稠稠稠密密密密图图图图，相相反反地地，当一个图中含有较少的边或弧时，则称它为当一个图中含有较少的边或弧时，则称它为稀疏图稀疏图稀疏图稀疏图。第第10章章 图及其应用图及其应用 5子图：子图：子图：子图：对于图对于图G=(V,VR),G=(V,VR),若有若有V V,VR VR,则称图则称图G是是G的一个子图。的一个子图。下图给出了下图给出了G与其子图与其子图G。2435167图G435167图G 第第10章章 图及其应用图及其应用 6邻接点邻接点邻接点邻接点 对对于于无无无无向向向向图图图图 G=(V,VR)，如如如如果果果果

5、边边边边(v(v，v)v)VRVR，则则则则称称称称顶顶顶顶点点点点v,v,vv互互互互为为为为邻邻邻邻接接接接点点点点，即即v,v相相邻邻接接。边边（v,v）依依附附于顶点于顶点v和和v，或者说边（，或者说边（v，v）与顶点）与顶点v和和v相关联。相关联。对对于于有有有有向向向向图图图图G=(V，VR)而而言言，若若若若弧弧弧弧vvVRVR，则则则则称称称称顶顶顶顶点点点点v v邻邻邻邻接接接接到到到到顶顶顶顶点点点点vv，顶顶顶顶点点点点vv邻邻邻邻接接接接自自自自顶顶顶顶点点点点v v，或或者者说说弧弧与顶点与顶点v和和v相关联。相关联。2341132如：顶点如：顶点1、2互为邻接点互为

6、邻接点如：顶点如：顶点1邻接到顶点邻接到顶点2 顶点顶点2邻接自顶点邻接自顶点1第第10章章 图及其应用图及其应用 7权与网权与网权与网权与网 在在实实际际应应用用中中，图图的的边边或或弧弧上上往往往往与与具具有有一一定定意意义义的的数数有有关关，即即每每每每一一一一条条条条边边边边都都都都有有有有与与与与它它它它相相相相关关关关的的的的数数数数，称称为为权权权权，我们将我们将这种带权的图这种带权的图这种带权的图这种带权的图叫做叫做赋权图赋权图赋权图赋权图或或网网网网，如图所示。，如图所示。第第10章章 图及其应用图及其应用 8路径和回路路径和回路路径和回路路径和回路路径：路径：路径：路径：所

7、谓顶点所谓顶点vp 到顶点到顶点vq之间的路径之间的路径,是指是指顶点序列顶点序列顶点序列顶点序列vp,vi1,vi2,vim,vq,其中（其中（vp,vi1）,（vi1,vi2）,（vim,vq）分别为图中的边。）分别为图中的边。路径长度：路径上边的数目路径长度：路径上边的数目路径长度：路径上边的数目路径长度：路径上边的数目称为路径长度。称为路径长度。简单路径：简单路径：简单路径：简单路径：序列中序列中顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径称为简单路径。称为简单路径。回路或环：回路或环：回路或环：回路或环：如果如果路径的起点和终点相同路径的起点和终点

8、相同路径的起点和终点相同路径的起点和终点相同(即即vp=vq),则则称此路径为回路或环。称此路径为回路或环。第第10章章 图及其应用图及其应用 9 如图所示的无向图中如图所示的无向图中,顶点顶点顶点顶点v1v1到顶点到顶点到顶点到顶点v5v5的路径有两条的路径有两条的路径有两条的路径有两条,分别为分别为v1,v2,v3,v4与与v1,v5,v4,路径长度分别为路径长度分别为路径长度分别为路径长度分别为3 3和和和和2 2。v1到到v5的两条路径都为的两条路径都为简简简简单路径单路径单路径单路径。简单回路：简单回路：简单回路：简单回路：除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第

9、一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外,其它顶点不其它顶点不其它顶点不其它顶点不重复出现的回路重复出现的回路重复出现的回路重复出现的回路为简单回路或者简单环。为简单回路或者简单环。第第10章章 图及其应用图及其应用 10 连通图和强连通图连通图和强连通图连通图和强连通图连通图和强连通图 在在无向图无向图无向图无向图中，若从顶点中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和顶点和顶点j是连通的。若任意两个顶点都是连通的，则称是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。此无向图为连通图，否则称为非连通图。连通图和非连通图示例见图连通图

10、和非连通图示例见图:第第10章章 图及其应用图及其应用 11 对对于于有有有有向向向向图图图图来来说说,若若图图中中任任任任意意意意一一一一对对对对顶顶顶顶点点点点v vi i和和和和v vj j(ij)(ij)均均均均有有有有从从从从v vi i到到到到 v vj j及及及及从从从从 v vj j到到到到 v vi i的的的的有有有有向向向向路路路路径径径径,则则称称该该有有有有向向向向图图图图是是是是强连通的强连通的强连通的强连通的。强连通图和非强连通图示例见图强连通图和非强连通图示例见图:第第10章章 图及其应用图及其应用 12连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量

11、连通分量和强连通分量 无无无无向向向向图图图图中中，极极大大的的连连通通子子图图为为该该图图的的连连通通分分量量。显显然然，任任何何连连通通图图的的连连通通分分量量只只有有一一个个，即即它它本本身身，而而非连通图有多个连通分量。非连通图有多个连通分量。24351672435167第第10章章 图及其应用图及其应用 13 有有向向图图中中的的极极极极大大大大强强强强连连连连通通通通子子子子图图图图称称为为该该有有向向图图的的强强强强连连连连通通通通分分分分量量量量。显显然然，任任何何强强连连通通图图的的强强连连通通分分量量只只有有一一个个，即即它本身，而非强连通图有多个强连通分量。它本身，而非强

12、连通图有多个强连通分量。下图不是强连通的下图不是强连通的,但它有两个强连通分量但它有两个强连通分量:132321第第10章章 图及其应用图及其应用 14顶点的度顶点的度顶点的度顶点的度2341如：顶点如：顶点1的度为的度为3132如：顶点如：顶点2的入度为的入度为2 出度为出度为1有向图有向图有向图有向图中中,要区别顶点的入度和出度的概念。要区别顶点的入度和出度的概念。顶点顶点v的的入度入度入度入度 是指是指以以以以v v为终点的弧的数目为终点的弧的数目为终点的弧的数目为终点的弧的数目记为记为ID(v)顶点顶点v的的出度出度出度出度 是指是指以以以以v v为始点的弧的数目为始点的弧的数目为始点

13、的弧的数目为始点的弧的数目记为记为OD(v)显然：显然：D(v)=ID(v)+OD(v)顶点的顶点的度度度度 是指是指依附于某顶点依附于某顶点依附于某顶点依附于某顶点v vi i的边数的边数的边数的边数,通常记通常记 为为D(v)第第10章章 图及其应用图及其应用 15 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第10章 图及其应用第第10章章 图及其应用图及其应用 16 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 10.2 图的存储第第

14、10章章 图及其应用图及其应用 17邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：用一个二维数组（矩阵）来表示图中顶点之间的相邻关系。设图设图G=(V,VR)有有n(n1)个顶点个顶点,则则G的邻接矩阵是按如的邻接矩阵是按如下定义的下定义的n阶方阵阶方阵:1 若若(vi,vj)或或VR(G)aij=0 反之反之第第10章章 图及其应用图及其应用 18例例例例:图图G1、G2的的邻邻接接矩矩阵阵分分别别表表示示为为A1和和A2,矩矩阵阵的的行、行、列号对应于图中结点的号。列号对应于图中结点的号。0 1 1 11 0 1 01 1 0 11 0 1 00 1 10 0 10 1 02341132G1G2

15、第第10章章 图及其应用图及其应用 19从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：（1）矩阵是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很很容容易易判判断断顶顶点点i 和和顶顶点点j之之间间是是否否有有边边相相连连(看看矩阵中矩阵中i行行j列值是否为列值是否为1)。第第10章章 图及其应用图及其应用 2

16、0从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论:（1）矩阵不一定是对称的矩阵不一定是对称的;（2）第第i 行中行中1的个数为顶点的个数为顶点i 的出度的出度;（3）第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4）矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目;（5）很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是否有弧相连.第第10章章 图及其应用图及其应用 21 网的邻接矩阵表示：网的邻接矩阵表示：网的邻接矩阵表示：网的邻接矩阵表示：若图若图G是一个有是一个有n个

17、顶点的网，则它的邻接矩阵是具有个顶点的网，则它的邻接矩阵是具有如下性质的如下性质的nn矩阵矩阵A：若若或或(vi,vj)VR(G)反之反之 第第10章章 图及其应用图及其应用 22 5 7 4 8 5 234158475例：例：例：例：一个有向网一个有向网N及其邻接矩阵的示例。及其邻接矩阵的示例。第第10章章 图及其应用图及其应用 23 n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O O(n(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接

18、矩阵法邻接矩阵法缺点：缺点：容易实现图的操作，如：求某顶点的度、判断顶点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。之间是否有边（弧）、找顶点的邻接点等等。第第10章章 图及其应用图及其应用 24邻接矩阵表示法的邻接矩阵表示法的C语言类型描述如下：语言类型描述如下：define MAX_V_N 10 /最多顶点个数最多顶点个数最多顶点个数最多顶点个数define INFINITY 32768 /表示极大值，表示极大值，表示极大值，表示极大值，即即即即 typedef enumDG,DN,UDG,UDNenumDG,DN,UDG,UDN GraphKind

19、;/图图图图的的的的种种种种类类类类：DGDG表表表表示示示示有有有有向向向向图图图图,DNDN表表表表示示示示有有有有向向向向网网网网,UDGUDG表表表表示示示示无向图无向图无向图无向图,UDN,UDN表示无向网表示无向网表示无向网表示无向网第第10章章 图及其应用图及其应用 25typedef struct ArcNodestruct ArcNode AdjType adj;AdjType adj;/AdjTypeAdjType是是是是顶顶顶顶点点点点关关关关系系系系类类类类型型型型，对对对对无无无无权权权权图图图图，用用用用1 1或或或或0 0表表表表示是否相邻；对带权图，则为权值类型

20、示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为权值类型 InfoType *info;InfoType *info;/该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针 ArcNode;第第10章章 图及其应用图及其应用 26 typedef structstruct VertexData vexsMAX_V_N;VertexData vexsMAX_V_N;/顶点向量顶点向量顶点向量顶点向量 ArcNode arcsMAX_V_NMAX_V_N;ArcNode arcsMAX_V_NMAX_V_N;/邻接矩阵邻接矩阵邻接矩

21、阵邻接矩阵 int vexnum,arcnum;int vexnum,arcnum;/图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数 GraphKind kind;GraphKind kind;/图的种类标志图的种类标志图的种类标志图的种类标志 AdjMatrix;/(Adjacency Matrix Graph)/(Adjacency Matrix Graph)第第10章章 图及其应用图及其应用 27int LocateVertex(AdjMatrix*G,VertexData v)/求顶点位置函数求顶点位置函数 int j=-1,k;for(k=0;kvexnum;k+)

22、if(G-vexsk=v)j=k;break;return(j);第第10章章 图及其应用图及其应用 28int CreateDN(AdjMatrix*G)/创建有向网创建有向网 int i,j,k,weight;VertexData v1,v2;scanf(%d,%d,&G-arcnum,&G-vexnum);/输入图的顶点数和弧数输入图的顶点数和弧数输入图的顶点数和弧数输入图的顶点数和弧数 for(i=0;ivexnum;i+)/初始化邻接矩阵初始化邻接矩阵初始化邻接矩阵初始化邻接矩阵 for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;for(i=0;ive

23、xnum;i+)scanf(%c,&G-vexsi);/输入图的顶点值输入图的顶点值输入图的顶点值输入图的顶点值第第10章章 图及其应用图及其应用 29 for(k=0;karcnum;k+)scanf(%c,%c,%d,&v1,&v2,&weight);/输入一条弧的两个顶点及权值输入一条弧的两个顶点及权值输入一条弧的两个顶点及权值输入一条弧的两个顶点及权值 i=LocateVex(G,v1);/求顶点位置函数求顶点位置函数求顶点位置函数求顶点位置函数 j=LocateVex(G,v2);G-arcsij.adj=weight;/建立弧建立弧建立弧建立弧 return(Ok);第第10章章

24、图及其应用图及其应用 30 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表10.2 图的存储第第10章章 图及其应用图及其应用 31 邻接表（邻接表（Adjacency List）表示法是图的一种链式存储）表示法是图的一种链式存储结构。它包括两个部分结构。它包括两个部分,一部分是一部分是链表链表链表链表,另一部分是另一部分是向量向量向量向量。在在链表部分中共有链表部分中共有链表部分中共有链表部分中共有n n个链表个链表个链表个链表(n为顶点数为顶点数),用来存放边用来存放边的信息。的信息。将将每个单链表的表头结点顺序存储在一个向量中每

25、个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中。2341第第10章章 图及其应用图及其应用 32 这这样样，一一个个n个个顶顶点点的的图图的的邻邻接接表表表表示示由由表表表表头头头头结结结结点点点点表表表表与与边表边表边表边表两部分构成：两部分构成：(1)(1)表表表表头头头头结结结结点点点点表表表表：由由所所有有表表头头结结点点以以顺顺序序结结构构（向向量量）的形式存储的形式存储.。表表头头结结点点的的结结构构如如图图所所示示，由由两两部部分分构构成成：数数数数据据据据域域域域（vexdatavexdata）用用于于存存

26、储储顶顶点点的的名名(值值)；链链链链域域域域（firstarcfirstarc）用用于于指指向向链链表表中中第第一一个个顶顶点点（即即与与顶顶点点vi邻邻接接的的第第一一个个邻接点）。邻接点）。vexdatavexdatafirstarcfirstarc第第10章章 图及其应用图及其应用 33(2)(2)边表：边表：边表：边表：由邻接点链式存储的单链表。由邻接点链式存储的单链表。单链表中每个结点由三个域组成单链表中每个结点由三个域组成:邻接点域邻接点域邻接点域邻接点域(adjvex)(adjvex)指指示与顶点示与顶点vi 邻接的点在图中的位置；邻接的点在图中的位置；链域链域链域链域(nex

27、tarc)(nextarc)指向指向顶点顶点vi 的下一个邻接点；的下一个邻接点；数据域数据域数据域数据域(info)(info)存储和边存储和边(或弧或弧)相相关的信息关的信息,如权值等。如权值等。adjvexadjvexnextarcnextarcinfoinfo第第10章章 图及其应用图及其应用 34例：例：2341第第10章章 图及其应用图及其应用 355423415第第10章章 图及其应用图及其应用 36从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：（1）第）第i 个链表中结点数目为顶点个链表中

28、结点数目为顶点i的度；的度；（2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e(e为边数为边数)。第第10章章 图及其应用图及其应用 37从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论:（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。从

29、有向图的邻接表可知，不能求出顶点的入度。若要求第若要求第i个顶点的个顶点的入度入度入度入度，必须，必须遍历整个邻接表遍历整个邻接表遍历整个邻接表遍历整个邻接表，在所，在所有边链表中查找有边链表中查找邻接点域的值为邻接点域的值为邻接点域的值为邻接点域的值为i i的结点并计数的结点并计数的结点并计数的结点并计数求和。求和。由此可见，由此可见，对于用邻接表方式存储的有向图，求顶点对于用邻接表方式存储的有向图，求顶点的入度并不方便，的入度并不方便，它需要通过扫描整个邻接表才能得它需要通过扫描整个邻接表才能得到结果。到结果。第第10章章 图及其应用图及其应用 38 解解解解决决决决的的的的方方方方法法法

30、法：逆逆逆逆邻邻邻邻接接接接表表表表法法，对对每每一一顶顶点点vi再再建建立立一一个个逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个所所有有以以顶顶点点vi为为弧弧头头的弧的表，如图所示：的弧的表，如图所示：2341第第10章章 图及其应用图及其应用 39邻接表的邻接表的邻接表的邻接表的缺点：缺点：缺点：缺点：邻接表的邻接表的邻接表的邻接表的优点：优点：优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。第第10

31、章章 图及其应用图及其应用 40define MAX_V_N 10 /最多顶点个数最多顶点个数最多顶点个数最多顶点个数typedef enumenum DG,DN,UDG,UDN DG,DN,UDG,UDN GraphKind;/图的种类图的种类图的种类图的种类typedef struct ArcNodestruct ArcNode int adjvex;int adjvex;/该弧指向顶点的位置该弧指向顶点的位置该弧指向顶点的位置该弧指向顶点的位置 struct ArcNode *nextarc;struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针指向下一条

32、弧的指针指向下一条弧的指针 InfoType *info;InfoType *info;/该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针 ArcNode;/边表中结点的类型边表中结点的类型邻接表存储结构的形式化说明如下：邻接表存储结构的形式化说明如下：第第10章章 图及其应用图及其应用 41typedef struct VertexNodestruct VertexNode VertexData verdata;VertexData verdata;/顶点数据顶点数据顶点数据顶点数据 ArcNode *firstarc;ArcNode *firstarc;/指向下一个

33、邻接点指向下一个邻接点指向下一个邻接点指向下一个邻接点 VertexNode;/表头结点表中结点的类型表头结点表中结点的类型typedef structstruct VertexNode vertexMAX_V_N;VertexNode vertexMAX_V_N;int vexnum,arcnum;int vexnum,arcnum;/图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数 GraphKind kind;GraphKind kind;/图的种类标志图的种类标志图的种类标志图的种类标志 AdjList;/基于邻接表的图基于邻接表的图(Adjacency List Gr

34、aph)第第10章章 图及其应用图及其应用 42讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.1.1.联系：联系：联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.2.2.区别：区别：区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶与顶点编号一致），但邻

35、接表不唯一（链接次序与顶点编号无关）。点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂而邻接表的空间复杂度为度为O(n+e)O(n+e)。第第10章章 图及其应用图及其应用 43 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 10.2 图的存储第第10章章 图及其应用图及其应用 44 十字链表是有向图的另一种链式存储结构。在十字十字链表是有向图的另一种链式存储结构。在十字链表中，链表中，对应于有向图中每一条弧有一个结点（对应于有向图中每一条弧有一个结点（对应于有向图中每一条弧有一

36、个结点（对应于有向图中每一条弧有一个结点（弧结弧结弧结弧结点点点点）:tailvextailvexheadvexheadvexhlinkhlinktlinktlinkinfoinfo弧尾顶点在弧尾顶点在图中的位置图中的位置弧头顶点在弧头顶点在图中的位置图中的位置指向与此弧弧头指向与此弧弧头相同的下一条弧相同的下一条弧指向与此弧弧尾指向与此弧弧尾相同的下一条弧相同的下一条弧指向该弧的指向该弧的相关信息相关信息第第10章章 图及其应用图及其应用 45对应于每个顶点也有一个结点（对应于每个顶点也有一个结点（顶点结点顶点结点顶点结点顶点结点）：）：指向以该顶点作为弧头指向以该顶点作为弧头的第一个弧顶点

37、的第一个弧顶点存储与顶点有关的信息存储与顶点有关的信息,如顶点的名字等如顶点的名字等指向以该顶点作为弧指向以该顶点作为弧尾的第一个弧顶点尾的第一个弧顶点datafirstinfirstout第第10章章 图及其应用图及其应用 46123412341213 34 234141 第第10章章 图及其应用图及其应用 47图的十字链表结构形式化定义如下：图的十字链表结构形式化定义如下：图的十字链表结构形式化定义如下：图的十字链表结构形式化定义如下：define MAX_V_N 10 /*/*最多顶点个数最多顶点个数最多顶点个数最多顶点个数*/*/typedef enumDG,DN,UDG,UDNenu

38、mDG,DN,UDG,UDN GraphKind;/*/*图的种类图的种类图的种类图的种类*/*/typedef struct ArcNodestruct ArcNode int tailvex,headvex;int tailvex,headvex;struct ArcNode *hlink,*tlink;struct ArcNode *hlink,*tlink;InfoType *info;InfoType *info;ArcNode;/*弧结点的类型弧结点的类型*/第第10章章 图及其应用图及其应用 48typedef struct VertexNodestruct VertexNode

39、 VertexData data;VertexData data;/*/*顶点信息顶点信息顶点信息顶点信息*/*/ArcNode *firstin,*firstout;ArcNode *firstin,*firstout;VertexNode;/*顶点结点的类型顶点结点的类型*/typedef structstruct VertexNode vertexMAX_V_N;VertexNode vertexMAX_V_N;int vexnum,arcnum;int vexnum,arcnum;/*/*图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数*/*/GraphKind kin

40、d;GraphKind kind;/*/*图的种类图的种类图的种类图的种类*/*/OrthList;/*图的十字链表表示法图的十字链表表示法(Orthogonal List)*/第第10章章 图及其应用图及其应用 49 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 10.2 图的存储第第10章章 图及其应用图及其应用 50 邻接多重表邻接多重表邻接多重表邻接多重表是无向图的另一种链式存储结构。在是无向图的另一种链式存储结构。在邻接多重表中，邻接多重表中，每一条边用一个结点表示，该结点有每一条边用一个结点表示，该结点有每一条边用一个结

41、点表示，该结点有每一条边用一个结点表示，该结点有六个域：六个域：六个域：六个域：markivexilinkjvexjlinkinfo标记该条边是标记该条边是否被搜索过否被搜索过指向下一依附指向下一依附于顶点于顶点i的边的边该边的一个该边的一个顶点在图中顶点在图中的位置序号的位置序号该边的另一个该边的另一个顶点在图中顶点在图中的位置序号的位置序号指向下一指向下一条依附于条依附于顶点顶点j的边的边指向该弧的指向该弧的相关信息相关信息第第10章章 图及其应用图及其应用 51 每一个顶点也用一个结点表示，该结点有两个域：每一个顶点也用一个结点表示，该结点有两个域：datafirstedge存储与顶点有

42、存储与顶点有关的信息，如关的信息，如顶点的名字顶点的名字指向第一条依附指向第一条依附于该顶点的边于该顶点的边第第10章章 图及其应用图及其应用 5235143234521212345123454523415第第10章章 图及其应用图及其应用 53邻接多重表的结构类型说明如下：邻接多重表的结构类型说明如下：typedef struct struct VertexData data;VertexData data;EdgeNode *firstedge;EdgeNode *firstedge;VertexNode;/*顶点结点的类型顶点结点的类型*/第第10章章 图及其应用图及其应用 54type

43、def struct EdgeNode struct EdgeNode int mark,ivex,jvex;int mark,ivex,jvex;struct EdgeNode *ilink,*jlink;struct EdgeNode *ilink,*jlink;InfoType *info;InfoType *info;EdgeNode;/*边结点的类型边结点的类型*/typedef structstruct VertexNode vertexMAX_V_N;VertexNode vertexMAX_V_N;int vexnum,arcnum;int vexnum,arcnum;/*/*

44、图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数*/*/GraphKind kind;/*GraphKind kind;/*图的种类图的种类图的种类图的种类*/*/AdjMultiList;/*基于图的邻接多重表表示法基于图的邻接多重表表示法(Adjacency Multi-list)*/第第10章章 图及其应用图及其应用 55分析分析分析分析:在图的链接存储在图的链接存储(邻接表、逆邻接表、十字链表邻接表、逆邻接表、十字链表和邻接多重表和邻接多重表)中，表头向量需要占用中，表头向量需要占用n个存储单元，个存储单元，所有边结点需要占用所有边结点需要占用2e或或e存储单元，所以最

45、多需要存储单元，所以最多需要（n+2e）个存储单元，稀疏图采用这种存储方式可）个存储单元，稀疏图采用这种存储方式可节省存储空间。节省存储空间。第第10章章 图及其应用图及其应用 56 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 有向无环图的应用 10.6 最短路径第10章 图及其应用第第10章章 图及其应用图及其应用 57图图图图的的的的遍遍遍遍历历历历：沿沿着着某某条条搜搜索索路路径径对对图图中中所所有有顶顶点点各各作一次访问。作一次访问。图图的的遍遍历历比比起起树树的的遍遍历历要要复复杂杂得得多多。图图中中顶顶点点关关系系是是多多对对

46、多多的的关关系系，图图可可能能是是非非连连通通图图，图图中中还还可可能能有有回回路路存存在在，因因此此在在访访问问了了某某个个顶顶点点后后，可可能能沿沿着着某某条路径搜索后又回到该顶点上。条路径搜索后又回到该顶点上。为为为为了了了了保保保保证证证证图图图图中中中中的的的的各各各各顶顶顶顶点点点点在在在在遍遍遍遍历历历历过过过过程程程程中中中中访访访访问问问问且且且且仅仅仅仅访访访访问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志。第第10章章 图及其应用图及其应用 58 为为此此 我我们们设设置置一

47、一个个访访访访问问问问标标标标志志志志数数数数组组组组visitednvisitedn，用用于于标标示示图图中中每每个个顶顶点点是是否否被被访访问问过过，它它它它的的的的初初初初始始始始值值值值为为为为0(“0(“假假假假”)”)，表表表表示示示示顶顶顶顶点点点点均均均均未未未未被被被被访访访访问问问问；一一一一旦旦旦旦访访访访问问问问过过过过顶顶顶顶点点点点vivi，则则置置访访问问标标志志数数组组中中的的visitedivisitedi为为为为1(“1(“真真真真”)”)，以以表表示示该该顶顶点点已已访问。访问。根据搜索路径的不同，图的遍历又分：根据搜索路径的不同，图的遍历又分：深度优先搜

48、索遍历深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历 广度优先搜索遍历广度优先搜索遍历广度优先搜索遍历广度优先搜索遍历 第第10章章 图及其应用图及其应用 5910.3.1 深度优先搜索遍历 10.3.2 广度优先搜索遍历 10.3 图的遍历第第10章章 图及其应用图及其应用 60 深深深深度度度度优优优优先先先先搜搜搜搜索索索索（Depth-First Search）是是指指按按照照深深度度方方向向搜搜索索，它它类类似似于于树树的的先先根根遍遍历历，是是树树的的先先根根遍遍历历的推广。的推广。特点：特点：特点：特点：尽可能先对纵深方向进行搜索。尽可能先对纵深方向进行搜索。算法描述：算法描述

49、：算法描述：算法描述：从某个顶点从某个顶点v0出发，进行出发，进行dfs的算法描述如下：的算法描述如下：(1)(1)访问访问访问访问v v0 0 。(2)(2)依次从依次从依次从依次从v0v0的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历第第10章章 图及其应用图及其应用 61BAGDCFHEI 下图给出了一个深度优先搜索的过程图示，其中下图给出了一个深度优先搜索的过程图示，其中实实实实箭头代表访问方向，虚箭头代表回溯方向箭头代表访问方向，虚箭头代表回溯方向箭头代表访问方向，虚箭头代表回溯方向箭头代表访问方向，虚

50、箭头代表回溯方向，箭头旁边的，箭头旁边的数字代表搜索顺序，数字代表搜索顺序，A A为起始顶点为起始顶点为起始顶点为起始顶点。第第10章章 图及其应用图及其应用 62 若若若若图图图图是是是是连连连连通通通通的的的的或或或或强强强强连连连连通通通通的的的的，则则从从图图中中某某一一个个顶顶点点出出发发可可以以访访问问到到图图中中所所有有顶顶点点，否否则则只只能能访访问问到到一一部部分顶点。分顶点。另外，从刚才写出的遍历结果可以看出，从某一另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是个顶点出发的遍历结果是不唯一的。但是,若我们给若我们给定图的存贮结构定图的存贮结构