图的定义和术语课件.ppt

《图的定义和术语课件.ppt》由会员分享，可在线阅读，更多相关《图的定义和术语课件.ppt（210页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用 7.6 7.6 最短路径最短路径 第七章第七章 图图v图图(Graph)由一个由一个顶点集顶点集V V和一个和一个边集边集E E构成的数构成的数据结构。据结构。Graph=(V,E)其中，其中，V V=x x|x x 某个数据对象某个数据对象 是非空有限的顶点集合；是非空有限的顶点集合；E E=(=(x x,y y)|)|x x,y y V V 或或 E E=y|x x,y y V

2、V&PathPath(x x,y y)是有限的顶点之间关系的集合，是有限的顶点之间关系的集合，(x,y)x,y)也叫做也叫做边边(edge)edge)集集合合,它是无方向的它是无方向的;PathPath(x x,y y)表示从表示从 x x 到到 y y 的一条单向的一条单向通路通路,它是有方向的它是有方向的,所以所以 x,y也叫做也叫做弧弧(arc)arc)的集合的集合,x x称称为弧尾或始点为弧尾或始点,y y称为弧头或终点称为弧头或终点.7.1 7.1 图的定义和术语图的定义和术语v有向图有向图有向图有向图G G是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成的组成的其中

3、：其中：V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是有向边（也称是有向边（也称弧弧）的有限集合，弧是顶点的）的有限集合，弧是顶点的有序对，记为有序对，记为 v,w，v,wv,w是顶点，是顶点，v v为弧尾，为弧尾，w w为弧头为弧头v无向图无向图无向图无向图G G是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成的组成的 其中：其中：V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是边的有限集合，边是顶点的无序对，是边的有限集合，边是顶点的无序对，记为（记为（v,wv,w）或（或（w,v)w,v)，并且（并且（v,w)=(w,v)

4、v,w)=(w,v)7.1 7.1 图的定义和术语图的定义和术语例例7.1245136G1图图G1中：中：V(G1)=1,2,3,4,5,6 E(G1)=,例例7.2157324G26图图G2中：中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)7.1 7.1 图的定义和术语图的定义和术语v无向完全图无向完全图(Completed graph)n个顶点的无向图有个顶点的无向图有n(n-1)/2条边（条边（最大边数是最大边数是n(n-1)/2）v有向完全图有向完全图n个顶点的有向图，有个顶点的有向图，有n(n

5、-1)条边（条边（最最大边数是大边数是n(n-1)）v稀疏图稀疏图(sparse graph)sparse graph)：边或弧很少的图边或弧很少的图,通常边数通常边数 nlognlog2 2n nv稠密图稠密图(Dense graph)Dense graph)无向图中，边数接近无向图中，边数接近n n n n(n n n n-1)/2-1)/2-1)/2-1)/2；有向图中，边数接近有向图中，边数接近n n n n(n n n n-1)-1)-1)-1)7.1 7.1 图的定义和术语图的定义和术语有向完全图有向完全图7.1 7.1 图的定义和术语图的定义和术语无向图无向图(树树)有向图有向图

6、完全图完全图无向无向 完全图完全图v权权与图的边或弧相关的数与图的边或弧相关的数v网网带权的带权的有向有向图叫有向网，带权的无向图图叫有向网，带权的无向图叫无向网叫无向网7.1 7.1 图的定义和术语图的定义和术语v子图子图如果图如果图G(V,E)和图和图G(V,E),满足：满足：V V，E E 则称则称G为为G的子图的子图7.1 7.1 图的定义和术语图的定义和术语v邻接点邻接点邻接点邻接点(或相邻点或相邻点或相邻点或相邻点),),),),关联关联 如果如果如果如果 e=(e=(e=(e=(u u u u,v v v v)是是是是 E E E E(G)(G)(G)(G)中的一条边，则称中的一

7、条边，则称中的一条边，则称中的一条边，则称 u u u u 与与与与 v v v v 互为邻接顶点或相邻顶点互为邻接顶点或相邻顶点互为邻接顶点或相邻顶点互为邻接顶点或相邻顶点;称边称边称边称边e e e e与顶点与顶点与顶点与顶点u u u u,v v v v 关联关联关联关联;如果如果如果如果 e=e=e=e=vvv 是是是是 E E E E(G)(G)(G)(G)中的一条弧，则称中的一条弧，则称中的一条弧，则称中的一条弧，则称 u u u u 邻接到邻接到邻接到邻接到v,vv,vv,vv,v邻接于邻接于邻接于邻接于u,u,u,u,也称也称也称也称e e e e与与与与u,vu,vu,vu,

8、v关联关联关联关联;称弧称弧称弧称弧e e e e与顶点与顶点与顶点与顶点u u u u,v v v v 关联关联关联关联;7.1 7.1 图的定义和术语图的定义和术语v顶点的度（于树的度不同）顶点的度（于树的度不同）无向图中，顶点的度为与每个顶点相连的边数无向图中，顶点的度为与每个顶点相连的边数,记记作作TD(v)有向图中，顶点的度分成入度与出度有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目入度：以该顶点为头的弧的数目,记为记为ID(v)出度：以该顶点为尾的弧的数目出度：以该顶点为尾的弧的数目,记为记为OD(v)一个顶点的度数等于该顶点的入度与出度之和一个顶点的度数等于该顶点的

9、入度与出度之和,即即TD(v)=OD(v)+ID(v)7.1 7.1 图的定义和术语图的定义和术语v路径路径路径是顶点的序列路径是顶点的序列V=Vi0,Vi1,V=Vi0,Vi1,VinVin，满足满足(V Vij-1ij-1,V,Vijij)E E 或或 E,(1jE,(1j n)n)v路径长度路径长度沿路径边的数目或沿路径各边权值之沿路径边的数目或沿路径各边权值之和和v简单路径简单路径序列中顶点不重复出现的路径序列中顶点不重复出现的路径v回路回路(环环)第一个顶点和最后一个顶点相同的路第一个顶点和最后一个顶点相同的路径径v简单回路简单回路(简单环简单环)除了第一个顶点和最后一个除了第一个顶

10、点和最后一个顶点外，其余顶点不重复出现的回路顶点外，其余顶点不重复出现的回路7.1 7.1 图的定义和术语图的定义和术语7.1 7.1 图的定义和术语图的定义和术语V0V1V3V2V0V1V3V2V0V1V2V0V1V3V0v连通图与连通分量连通图与连通分量连通图与连通分量连通图与连通分量在在在在无向图无向图无向图无向图中中中中,若从顶点若从顶点若从顶点若从顶点v v v v1 1 1 1到顶点到顶点到顶点到顶点v v v v2 2 2 2有路径有路径有路径有路径,则称顶则称顶则称顶则称顶点点点点v v v v1 1 1 1与与与与v v v v2 2 2 2是是是是连通的连通的连通的连通的。

11、如果图中任意一对顶点都是连。如果图中任意一对顶点都是连。如果图中任意一对顶点都是连。如果图中任意一对顶点都是连通的通的通的通的,则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连通子。非连通图的极大连通子。非连通图的极大连通子。非连通图的极大连通子图叫做图叫做图叫做图叫做连通分量连通分量连通分量连通分量。ABCDEHMFGIJLK无向图无向图G的三个连通分量的三个连通分量ABCDEFGIJLHMK无向图无向图G7.1 7.1 图的定义和术语图的定义和术语v强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量在在在在有向图有向图有向图有

12、向图中中中中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点v v v vi i i i和和和和v v v vj j j j,都存在一条都存在一条都存在一条都存在一条从从从从v v v vi i i i到到到到v v v vj j j j和从和从和从和从v v v vj j j j到到到到v v v vi i i i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此图是强连通图强连通图强连通图强连通图。非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做叫做叫做强连通分量强连通分量强连通分量强连通分量。强

13、连通图强连通图 有向图有向图G 有向图有向图G的两的两个个 强强连通分量连通分量7.1 7.1 图的定义和术语图的定义和术语v生成树生成树：是一个极小连通子图，它含有图中全部是一个极小连通子图，它含有图中全部是一个极小连通子图，它含有图中全部是一个极小连通子图，它含有图中全部n n n n个顶个顶个顶个顶点，但只有点，但只有点，但只有点，但只有n n n n-1-1-1-1条边。条边。条边。条边。如果在生成树上添加如果在生成树上添加如果在生成树上添加如果在生成树上添加1 1 1 1条边，必定构成一个环条边，必定构成一个环条边，必定构成一个环条边，必定构成一个环若图中有若图中有若图中有若图中有n

14、 n n n个顶点，却少于个顶点，却少于个顶点，却少于个顶点，却少于n n n n-1-1-1-1条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 7.1 7.1 图的定义和术语图的定义和术语v生成森林生成森林：由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。树的边是最少的。树的边是最少的。树的边是最少的。有向图有向图G的生成森林的生成森林有向图有向图G7

15、.1 7.1 图的定义和术语图的定义和术语本章只讨论本章只讨论简单图简单图,有两类图形不在本章讨论之列：有两类图形不在本章讨论之列：7.1 7.1 图的定义和术语图的定义和术语图的抽象数据类型定义图的抽象数据类型定义ADT Graph 数据对象数据对象V：v v是具有相同特性的数据元素的集合，称为是具有相同特性的数据元素的集合，称为顶点集。顶点集。数据关系数据关系 R R：R=VRR=VR；VR=VR=|v,wV|v,wV 且且 P(v,w)P(v,w),表示从表示从v v到到w w的弧，的弧，谓词谓词P(v,w)P(v,w)定义了弧定义了弧 v,w的意义或信息的意义或信息 基本操作基本操作P

16、 P：CreatGraph(&G,V,VR)/按定义按定义(V,VR)构造图构造图DestroyGraph(&G):/销毁图基本操作基本操作LocateVex(G,u);/若若G中存在顶点中存在顶点u，则返回该顶点在则返回该顶点在 图中图中“位置位置”；否则返回其它信息。；否则返回其它信息。GetVex(G,v);/返回返回 v 的值。的值。PutVex(&G,v,value);/对对 v 赋值赋值value。FirstAdjVex(G,v);/返回返回 v 的的“第一个邻接点第一个邻接点”。若该顶点。若该顶点/在在 G 中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAdjVex(

17、G,v,w);/返回返回 v 的（相对于的（相对于 w 的）的）“下一个邻接下一个邻接 点点”。若。若 w 是是 v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。基本操作基本操作InsertArc(&G,v,w);/在在G中增添弧中增添弧，若若G是无向的，是无向的，/则还增添对称弧则还增添对称弧。DeleteArc(&G,v,w);/在在G中删除弧中删除弧，若若G是无向的，是无向的，/则还删除对称弧则还删除对称弧。DeleteVex(&G,v);/删除删除G中顶点中顶点v及其相关的弧。及其相关的弧。InsertVex(&G,v);/在图在图G中增添新顶点中增添新顶点v。基本操作基

18、本操作DFSTraverse(G,v,Visit()/从顶点从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每个顶点调并对每个顶点调用函数用函数VisitVisit一次且仅一次一次且仅一次。BFSTraverse(G,v,Visit()/从顶点从顶点v v起广度优先遍历图起广度优先遍历图G G，并对每个顶点并对每个顶点调用函数调用函数VisitVisit一次且仅一次。一次且仅一次。图的四种常用的存储形式：图的四种常用的存储形式：邻接矩阵和加权邻接矩阵邻接矩阵和加权邻接矩阵（labeled adjacency matrix）邻接表邻接表十字链表十字链表邻接多重表邻接多重表7.2 图的存储

19、结构图的存储结构一、一、(加权加权)邻接矩阵（邻接矩阵（labeled adjacency matrix）设图设图设图设图 G=G=E是一个有是一个有是一个有是一个有 n n 个顶点的图，则图的邻接个顶点的图，则图的邻接个顶点的图，则图的邻接个顶点的图，则图的邻接矩阵是一个二维数组矩阵是一个二维数组矩阵是一个二维数组矩阵是一个二维数组 GG.arcs.arcs n n n n，定义：定义：定义：定义：无向图无向图G1有向图有向图G2 一、一、(加权加权)邻接矩阵（邻接矩阵（continue）(1)(1)对称矩阵对称矩阵对称矩阵对称矩阵(可采用压缩存储可采用压缩存储可采用压缩存储可采用压缩存储)

20、;);(2)(2)每一行每一行每一行每一行(或列或列或列或列)1)1的个数是该顶点的度的个数是该顶点的度的个数是该顶点的度的个数是该顶点的度;(3)(3)主对角线全为主对角线全为主对角线全为主对角线全为0(0(简单图简单图简单图简单图););从邻接矩阵中可以反映图的许多特征从邻接矩阵中可以反映图的许多特征从邻接矩阵中可以反映图的许多特征从邻接矩阵中可以反映图的许多特征:无向图无向图 一、一、(加权加权)邻接矩阵（邻接矩阵（continue）有向图有向图(1)(1)每一行每一行每一行每一行1 1的个数是该顶点的出度的个数是该顶点的出度的个数是该顶点的出度的个数是该顶点的出度;(2)(2)每一列每

21、一列每一列每一列1 1的个数是该顶点的入度的个数是该顶点的入度的个数是该顶点的入度的个数是该顶点的入度;(3)(3)主对角线全为主对角线全为主对角线全为主对角线全为0(0(简单图简单图简单图简单图););有向图的邻接矩阵不一定对称。有向图的邻接矩阵不一定对称。有向图的邻接矩阵不一定对称。有向图的邻接矩阵不一定对称。定义为：定义为：G.arcs i j=Wij 或（或（vi,vj）VR 无边（弧）无边（弧）以有向网为例：以有向网为例：邻接矩阵：N.Edge=(v1 v2 v3 v4 v5 v6 )顶点表：5v1v2v3v4v5v6489755613N 5 7 4 8 9 5 6 5 3 1 网络

22、的邻接矩阵网络的邻接矩阵 一、一、(加权加权)邻接矩阵（邻接矩阵（continue）容易实现图的操作，如：求某顶点的容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。接点等等。n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空空间效率为间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：一、一、(加权加权)邻接矩阵（邻接矩阵（continue）#define INFINITY INT_MAX#defi

23、ne MAX_VERTEX_NUM 20typedef enumDG,DN,UDG,UDN GraghKind;typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。是顶点关系类型。/对无权图，用对无权图，用1或或0表示相邻否表示相邻否；/对带权图，则为权值类型。对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;用邻接矩阵表示的图的存储表示用邻接矩阵表示的图的存储表示用邻接矩阵表示的图的存储表示用

24、邻接矩阵表示的图的存储表示(P161)P161)P161)P161)typedef struct /图的定义图的定义 VertexType vexsMAX_VERTEX_NUM;/顶顶点点信息信息 AdjMatrix arcs;/弧的信息弧的信息 int vexnum,arcnum;/顶点数，弧数顶点数，弧数 GraphKind kind;/图的种类标志图的种类标志 MGraph;用邻接矩阵表示的图的存储表示用邻接矩阵表示的图的存储表示用邻接矩阵表示的图的存储表示用邻接矩阵表示的图的存储表示(continue)continue)continue)continue)Status CreateUD

25、N(Mgraph&G)/用邻接矩阵表示用邻接矩阵表示return OK;例：用邻接矩阵生成无向网的算法例：用邻接矩阵生成无向网的算法（参见教材（参见教材P162）scanf(&G.vexnum,&G.arcnum,&IncInfo);/输入总顶输入总顶点数，总弧数和信息点数，总弧数和信息for(i=0;iG.vexnum,;+i)scanf(&G.vexsi);/输入顶点输入顶点值，存入一维向量中值，存入一维向量中for(i=0;iG.vexnum;+i)/对邻接矩阵对邻接矩阵n*nn*n个单元初个单元初始化，始化，adj=,info=NULL for(j=0;jG.vexnum;+j)G.a

26、rcsij=INFINITY,NULL;for(k=0;kG.arcnum;+k)/给弧赋初值给弧赋初值(循环次数循环次数弧数弧数)scanf(&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);/找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n n次次)G.arcsij.adj=w;/输入对应权值输入对应权值 If(IncInfo)Input(*G.arcsij.info);G.arcsji=G.arcs i j；/无向网是对称矩阵无向网是对称矩阵 对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率=O(nO(n2 2

27、+n+e*n)+n+e*n)int firstAdjVex(Mgraph G,int v)/返回顶点返回顶点v的第一个邻接点，的第一个邻接点，G为无向图为无向图 for(k=0;k0 )break;if(k=G.vexnum)k=-1;/无邻接点无邻接点return k;/end firstAdjVex()图的部分操作在邻接矩阵上的实现图的部分操作在邻接矩阵上的实现二二、邻接表邻接表 (Adjacency List)q无向图的邻接表无向图的邻接表为每个顶点建立一个单链表为每个顶点建立一个单链表为每个顶点建立一个单链表为每个顶点建立一个单链表,第第第第i i i i个单链表中的结点表个单链表中的

28、结点表个单链表中的结点表个单链表中的结点表示与顶点示与顶点示与顶点示与顶点v v v vi i i i相邻的顶点相邻的顶点相邻的顶点相邻的顶点0123413341420注：邻接表不唯一，因各个边结点的链入顺序是任意的。注：邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v1v2v3v5v4v4data:结点的数据域，保存结点的数据值。结点的数据域，保存结点的数据值。firstarc:结点的指针域，给出自该结点出发的的第一条边结点的指针域，给出自该结点出发的的第一条边 的边结点的地址。的边结点的地址。头结点头结点:datafirstarcadjvexnextarc表

29、结点表结点:adjvex:该边或弧所指向的顶点的位置该边或弧所指向的顶点的位置.nextarc:指向下一条边或弧的指针指向下一条边或弧的指针.二二、邻接表邻接表 (Adjacency List)adjvexnextarcdatafirstarc在无向图的邻接表中在无向图的邻接表中在无向图的邻接表中在无向图的邻接表中,如何求每个顶点的度？如何求每个顶点的度？如何求每个顶点的度？如何求每个顶点的度？若顶点数为若顶点数为若顶点数为若顶点数为n,n,n,n,边数为边数为边数为边数为e e e e时时时时,则在无向图中共需多少则在无向图中共需多少则在无向图中共需多少则在无向图中共需多少 个结点？个结点？

30、个结点？个结点？二二、邻接表邻接表 (Adjacency List)0123413341420v1v2v3v4v5231420v1v2v3v5v4v4n n n n个头结点个头结点个头结点个头结点,2,2,2,2e e e e个表结点个表结点个表结点个表结点第第第第 i i i i 个链表中的结点个数是顶点个链表中的结点个数是顶点个链表中的结点个数是顶点个链表中的结点个数是顶点 i i i i 的度的度的度的度q有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表在有向图的邻接表中，第在有向图的邻接表中，第 i i 个单链表链接的边个单链表链接的边都是都是顶点顶点 i i 发出的边发出的边。也叫做

31、。也叫做出边表出边表。在有向图的逆邻接表中，第在有向图的逆邻接表中，第 i i 个单链表链接的个单链表链接的边都是边都是进入顶点进入顶点 i i 的边的边。也叫做。也叫做入边表入边表。v1v2v3v4V4V3V2V12301V4V3V2V13020邻接表邻接表(出边出边)逆邻接表逆邻接表(入边入边)01230123用用邻接表表示有向图时邻接表表示有向图时，若不考虑逆邻接表，只需，若不考虑逆邻接表，只需 n n 个顶点结点，个顶点结点，e e 个边结点。个边结点。q网络网络(带权图带权图)的邻接表的邻接表带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 costcost邻接表表示

32、的图的存储结构邻接表表示的图的存储结构（P163）/边结点定义边结点定义typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;adjvex info nextarc/头结点定义头结点定义typedef struct VNode VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指指向向第第一一条条依依附附该该顶顶点的弧点的

33、弧 VNode,AdjListMAX_VERTEX_NUM;data firstArc邻接表表示的图的存储结构邻接表表示的图的存储结构（P163）/图的定义图的定义typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志图的种类标志 ALGraph;邻接表表示的图的存储结构邻接表表示的图的存储结构（P163）图的操作在邻接连表的上的实现图的操作在邻接连表的上的实现int firstAdjVex(ALGraph ghead,int v)return gheadv-firstArc.adjvex;/end firstAdj

34、Vex()int nextAdjVex(ALGraph ghead,int v,int w)p=gheadv-firstArc;while(p&p-adjvex!=w)p=p-next;if(!p)return 0;else return p-next-adjvex;/end nextAdjVex()找某顶点的所有邻接点的时间复杂度是找某顶点的所有邻接点的时间复杂度是O(e)如何建立邻接表（以有向图为例）如何建立邻接表（以有向图为例）算法思想：算法思想：首先将邻接表表头数组初始化，首先将邻接表表头数组初始化，vertexvertex域初始域初始化为化为i i，firstarcfirstarc初

35、始化为初始化为NULLNULL；然后对读入的每一条弧然后对读入的每一条弧 i,j，产生一个表结产生一个表结点，点，adjveradjver域置为域置为j j，并将结点链接到邻接表的并将结点链接到邻接表的第第i i个链表中。个链表中。算法如下：算法如下：Void GreatAdjList(ALGraph&G)ArcNode *p;sacnf(“%d%d”,&n,&e);G.vexnum=n;G.arcnum=e;for(i=0;in;i+)G.verticesi.vertex=i;G.verticesi.firstarc=NULL;for(k=0;kadjvex=j;p-nextarc=G.ve

36、rticesi.firstarc;G.verticesi.firstarc=p;/GreatAdjList讨论：邻接表与邻接矩阵的比较讨论：邻接表与邻接矩阵的比较1.1.联系：联系：都可以用来存储有向图和无向图；邻接表中都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。数等于一行中非零元素的个数。2.2.区别：区别：邻接矩阵是顺序结构，邻接表是链式结构邻接矩阵是顺序结构，邻接表是链式结构对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致）

37、，但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂而邻接表的空间复杂度为度为O(n+e)O(n+e)。邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而而邻接表多用于稀疏图的存储（邻接表多用于稀疏图的存储（enen2 2)三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)在在无向图无向图的邻接表中的邻接表中,一条边出现两个单链表中一条边出现两个单链表中.浪费浪费空间，也给

38、某种操作带来了困难。空间，也给某种操作带来了困难。在邻接多重表中，每一条边只有一个结点在邻接多重表中，每一条边只有一个结点(称边结点称边结点)为有关边的处理提供了方便。为有关边的处理提供了方便。mark ivex jvex ilink jlink其中其中:mark 是记录是否处理过的标记；是记录是否处理过的标记；ivex和和jvex是依附于该边的两顶点位置。是依附于该边的两顶点位置。ilink域指向下一条依附于顶点域指向下一条依附于顶点ivexivex的边；的边；jlink指向下一条依附于顶点指向下一条依附于顶点jvexjvex的边。的边。需要时还可设置一个存放与该边相关的权值需要时还可设置一

39、个存放与该边相关的权值的域的域 cost。边结点的结构边结点的结构Ebox:三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)顶点结点的结构顶点结点的结构:其中其中:data 存放与该顶点相关的信息存放与该顶点相关的信息;Firstarc 是指示第一条依附于该顶点的边的指针。是指示第一条依附于该顶点的边的指针。存储顶点信息的结点表以顺序表方式组织存储顶点信息的结点表以顺序表方式组织.在邻在邻接多重表中接多重表中,所有依附于同一个顶点的边都链接所有依附于同一个顶点的边都链接在同一个单链表中。从顶点在同一个单链表中。从顶点 i i 出发出发,可以循链找到可以循链找到所有依附于

40、该顶点的边，也可以找到它的所有邻所有依附于该顶点的边，也可以找到它的所有邻接顶点。接顶点。data FirstarcVexBox:三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)例例aecbd0123acdb4e 0 1 0 3 2 3 2 1 2 4 4 1三、三、邻接多重表邻接多重表(无向图无向图的一种存储结构的一种存储结构)四、十字链表四、十字链表(有向图有向图的一种存储结构的一种存储结构)v可以把十字链表看成是将有向图的邻接表和逆可以把十字链表看成是将有向图的邻接表和逆邻接表这两个表结合起来而得到的一种链表。邻接表这两个表结合起来而得到的一种链表。v在十字链表中

41、在十字链表中,有向图中每一条弧对应一个结点有向图中每一条弧对应一个结点(称称弧结点弧结点)v每一个顶点也对应一个结点每一个顶点也对应一个结点(称顶点结点称顶点结点)。其中其中:tailvex表示该弧的弧尾顶点在图中的位置；表示该弧的弧尾顶点在图中的位置；headvex表示该弧的弧头顶点在图中的位置；表示该弧的弧头顶点在图中的位置；hlink指向指向弧头弧头相同的下一条弧的指针；相同的下一条弧的指针；tlink指向指向弧尾弧尾相同的下一条边的指针。相同的下一条边的指针。需要时还可有权值域需要时还可有权值域cost 边结点的结构边结点的结构tailvex headvex hlink tlinkAr

42、cBox:四、十字链表四、十字链表(有向图有向图的一种存储结构的一种存储结构)顶点结点的结构顶点结点的结构 data Firstin FirstoutVexNode:其中其中:数据域数据域data存放与该顶点相关的信息，存放与该顶点相关的信息，指针域指针域Firstin指向以该顶点为指向以该顶点为弧头弧头的第一条弧；的第一条弧；指针域指针域Firstout指向以该顶点为指向以该顶点为弧尾弧尾的第一条弧。的第一条弧。四、十字链表四、十字链表(有向图有向图的一种存储结构的一种存储结构)例例bdacab cd0123 0 2 0 1 2 3 2 0 3 2 3 1 3 0四、十字链表四、十字链表(有

43、向图有向图的一种存储结构的一种存储结构)#define MAX_VERTEX_NUM 20Typedef struct ArcBox /弧结点结构弧结点结构 int tailvex,headvex;struct ArcBox*hlink,tlink;InfoType *info;ArcBox；Typedef struct VexNode /顶点结构顶点结构 VertexType data;ArcBox *firstin,*firstout;VexNode;Typedef struct VexNode xlist MAX_VERTEX_NUM;/表头向量表头向量 int vexnum,arcnu

44、m;OLGraph;/图结构图结构7.3 7.3 图的遍历图的遍历q从已给的连通图中某一顶点出发，沿着一些边访问图从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历(Graph Traversal)。u深度优先遍历深度优先遍历u广度优先遍历广度优先遍历q图的两种遍历方法图的两种遍历方法图中可能存在回路，在访问完某个顶点之后图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点可能会沿着某些边又回到了曾经访问过的顶点为了避免重复访问，可设置一个标志顶点是为了避免重复访问

45、，可设置一个标志顶点是否被访问过的辅助数组否被访问过的辅助数组 visited ，它的初始状它的初始状态为态为 0 0，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点 i i 被访问，就立即让被访问，就立即让 visited i 为为 1 1，防止它，防止它被多次访问。被多次访问。7.3 7.3 图的遍历图的遍历DFS算法思想：算法思想：深度优先搜索深度优先搜索DFS(Depth First Search)从图中某个顶点从图中某个顶点V V0 0 出发，访问此顶点，然后出发，访问此顶点，然后依次从依次从V V0 0的各个未被访问的邻接点出发深度优先搜索遍历图的各个未被访问的

46、邻接点出发深度优先搜索遍历图，直至直至V V0 0 的所有邻接点都被访问到。的所有邻接点都被访问到。若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问,则另选图中一个未则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。中所有顶点都被访问到为止。深度优先搜索深度优先搜索DFS(Depth First Search)深度优先搜索的示例深度优先搜索的示例深度优先遍历生成树深度优先遍历生成树图的深度优先遍历算法图的深度优先遍历算法void dfsTraverse()for(v=1;v=n;v+)visitedv=fals

47、e;for(v=1;v=n;v+)if(!visitedv)dfs(v);void dfs(int v)visitedv=1;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w)if(!visitedw)dfs(w);/使用使用ADT在递归函数中增加一计数器在递归函数中增加一计数器sum，初值为初值为n，每访问每访问一次就减一次就减1,减到减到0则则return，可避免递归时间过长。可避免递归时间过长。在邻接矩阵在邻接矩阵A A上实现上实现 void dfs(int v)visitedv=true;for(w=1;w0)if(!visitedw)dfs(w);/图的

48、深度优先遍历算法图的深度优先遍历算法在邻接链表上实现在邻接链表上实现 void dfs(int v)visitedv=true;p=gheadv-firstArc;while(p)w=p-adjvex;if(!visitedw)dfs(w);p=p-next;同学们自己考虑非递归实现算法同学们自己考虑非递归实现算法图的深度优先遍历算法图的深度优先遍历算法Dfs1(Graph g,int v)/利用栈实现非递归算法利用栈实现非递归算法 /第一个顶点入栈并访问第一个顶点入栈并访问 Visit(v);visitv=1;push(s,v);/当栈不空时做当栈不空时做 Whlie(!EmptyStack

49、(s)p=gheadv-firstArc;/找到栈顶的一个未被访问的邻接点，入栈并访问找到栈顶的一个未被访问的邻接点，入栈并访问while(p)w=p-adjvex;if(!visitedw)push(s,w);visit(w);p=gheadw-firstArc;else p=p-next;/while/如果所有邻接点都被访问，出栈如果所有邻接点都被访问，出栈 pop(s,v);/whileV1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V112341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 1 5 1 2 8 2678678 7 3 6

50、3 5 4V3 V7 V6 V2 V5 V8 V4V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：深度遍历：V1V3 V7 V6 V2 V4 V8 V5DFS 算法效率分析算法效率分析:设图中有设图中有 n n 个顶点，个顶点，e e 条边，遍历时对图中每个顶条边，遍历时对图中每个顶点至多调用一次点至多调用一次DSFDSF函数，遍历图的过程就是对每个函数，遍历图的过程就是对每个顶点查找其邻接点的过程，消耗的时间取决于所采顶点查找其邻接点的过程，消耗的时间取决于所采用的存储结构用的