图资料学习教程.pptx

《图资料学习教程.pptx》由会员分享，可在线阅读，更多相关《图资料学习教程.pptx（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的存储结构图的存储结构图的存储结构图的存储结构-邻接矩阵邻接矩阵邻接矩阵邻接矩阵（数组表示法）（数组表示法）（数组表示法）（数组表示法）基基本本思思想想：用用一一个个一一维维数数组组存存储储图图中中顶顶点点的的信信息息，用用一一个个二二维维数数组组（称称为为邻邻接接矩矩阵阵）存存储储图图中中各各顶顶点点之之间间的的邻邻接接关关系系。用用两两个个整整型型变变量量分分别别存存储储顶顶点点数数和边数和边数。6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现假假设设图图G G(V(V，E)E)有有n n个个顶顶点点，则则邻邻接接矩矩阵阵是是一一个个nnnn的方阵

2、，定义为：的方阵，定义为：arcsij1 若若(vi,vj)E（或（或E）0 其它其它第1页/共117页无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？无向图的邻接矩阵无向图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arcs=V1 V2 V3 V4V1V2V3V4主对角线为主对角线为 0 且一定是对称矩阵。且一定是对称矩阵。第2页/共117页如何求顶点如何求顶点i的度？的度？无向图的邻接矩阵无向图的邻接矩阵6.2 6.2 图

3、的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arcs=V1 V2 V3 V4V1V2V3V4邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。第3页/共117页如何判断顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？无向图的邻接矩阵无向图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1

4、0 1 1 0 1 0 0 1 1 0 0 arcs=V1 V2 V3 V4V1V2V3V4测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcsij是否为是否为1第4页/共117页如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？无向图的邻接矩阵无向图的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arcs=V1 V2 V3 V4V1V2V3V4将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若arcs

5、ij为为1，则，则顶点顶点 j 为顶点为顶点 i 的邻接点。的邻接点。第5页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arcs=V1 V2 V3 V4V1V2V3V4有向图的邻接矩阵一定不对称吗？有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。不一定，例如有向完全图。第6页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接矩

6、阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arcs=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的的出度（出度（i是弧尾）是弧尾）？邻接矩阵的第邻接矩阵的第 i 行元素之和。行元素之和。第7页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arcs=V1 V2 V3 V4V1V2V3V4

7、如何求顶点如何求顶点 i 的的入度入度？（i是弧头）是弧头）邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。第8页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arcs=V1 V2 V3 V4V1V2V3V4如何判断从顶点如何判断从顶点 i 到顶点到顶点 j 是否存在弧？是否存在弧？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcsij是否为是否为1。第9页/共117页网的邻

8、接矩阵网的邻接矩阵6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现网的邻接矩阵可定义为：网的邻接矩阵可定义为：arcsij wij 若若(vi,vj)E（或（或E）0 若若i=j 其他，其他，是人为指定的一个数是人为指定的一个数V1V2V3V42785 0 2 5 0 0 8 7 0 arc=第10页/共117页邻邻接接矩矩阵阵数数据据类类型型描描述述#define MaxSize 20 typedef struct GelemType vertexMaxSize;/存顶点信息存顶点信息 ArcType arcsMaxSizeMaxSize;/存顶点间的

9、关系存顶点间的关系 int vertexNum,arcNum;/存顶点数和边数存顶点数和边数 MGraph;6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现其中：其中：GelemTypeGelemType表示图中顶点的数据类型表示图中顶点的数据类型 ArcType ArcType表示图中边（弧）的数据类型表示图中边（弧）的数据类型第11页/共117页ABC该无向图需要存放以下该无向图需要存放以下信息：信息：1.1.顶点数据顶点数据A A、B B、C C2.2.顶点之间的邻接关系顶点之间的邻接关系3.3.无向图中的顶点数和无向图中的顶点数和边数边数第12页

10、/共117页对应的数据类型为：#define MaxSize 20 typedef struct char vertexMaxSize;/存顶点 int arcsMaxSizeMaxSize;/存顶点间的关系 int vertexNum,arcNum;/存顶点数和边数 MGraph;MGraph G;MGraph G;变量变量G G可以存放图，其中：可以存放图，其中：G.vertexiG.vertexi存放顶点值，存放顶点值，G.arcsijG.arcsij存放顶点的关系，存放顶点的关系，G.vertexNumG.vertexNum存放图的存放图的顶点数，顶点数，G.arcNumG.arcNu

11、m存放图的边数。存放图的边数。第13页/共117页ABC 0 1 1 1 0 11 1 03 3ABC无向图无向图MGraph G;变量变量G的存储结构示意图的存储结构示意图第14页/共117页ABC该有向图需要存放以下该有向图需要存放以下信息：信息：1.1.顶点数据顶点数据A A、B B、C C2.2.顶点之间的邻接关系顶点之间的邻接关系3.3.有向图中的顶点数和有向图中的顶点数和边数边数第15页/共117页ABC 0 1 1 0 0 00 1 03 3ABC有向图有向图MGraph G;变量变量G的存储结构示意图的存储结构示意图第16页/共117页该该无向网无向网需要存放以下需要存放以下信

12、息：信息：1.1.顶点数据：动物园、顶点数据：动物园、长城、故宫、野山坡长城、故宫、野山坡2.2.顶点之间的邻接关系顶点之间的邻接关系和边上的权和边上的权3.3.无向网中的顶点数和无向网中的顶点数和边数边数假设权代表距离假设权代表距离动物园故宫长城205030野山坡100第17页/共117页对应的数据类型为：#define MaxSize 20 typedef char MC10;typedef struct MC vertexMaxSize;/存顶点 int arcsMaxSizeMaxSize;/存顶点间的关系 int vertexNum,arcNum;/存顶点数和边数 MGraph;第1

13、8页/共117页动物园 故宫 长城 野山坡 0 20 30 -1 20 0 50 10030 50 0 -1-1 100 -1 04 4无向网无向网MGraph G;变量变量G的存储示意图的存储示意图动物园故宫长城205030野山坡第19页/共117页该有向网需要存放以下该有向网需要存放以下信息：信息：1.1.顶点数据顶点数据A A、B B、C C2.2.顶点之间的邻接关系顶点之间的邻接关系和弧上的权以及弧上的和弧上的权以及弧上的一些描述一些描述3.3.有向网中的顶点数和有向网中的顶点数和边数边数ABC205030CB之间有5个阀门假设假设A、B、C为三个小区，为三个小区，弧为地下天然气管道弧

14、为地下天然气管道第20页/共117页（1）对应的数据类型为：#define MaxSize 20 typedef struct int data;/存放边上的权 char str80;/用于指向描述边信息的字符串ArcType;typedef struct char vertexMaxSize;/存顶点的信息 ArcType arcsMaxSizeMaxSize;/存顶点间的关系 int vertexNum,arcNum;/存顶点数和边数 MGraph;第21页/共117页（2）对应的数据类型为：#define MaxSize 20 typedef struct int data;/存放边上的

15、权 char*p;/用于指向描述边信息的字符串ArcType;typedef struct char vertexMaxSize;/存顶点的信息 ArcType arcMaxSizeMaxSize;/存顶点间的关系 int vertexNum,arcNum;/存顶点数和边数 MGraph;第22页/共117页ABC 0 1000 30 20 0 1000 1000 50 0 3 3有向网有向网ABC205030CB之间有MGraph G;变量变量G存储结构示意图存储结构示意图表示字符型指针变量第23页/共117页基于邻接矩阵的无向图基本操作基于邻接矩阵的无向图基本操作创建函数创建函数 1.确定

16、图的顶点个数和边的个数；确定图的顶点个数和边的个数；2.输入顶点信息存储在一维数组输入顶点信息存储在一维数组vertex中；中；3.初始化邻接矩阵（每个元素置初始化邻接矩阵（每个元素置0）；）；4.依次输入每条边存储在邻接矩阵依次输入每条边存储在邻接矩阵arcs中；中；4.1 输入边依附的两个顶点的序号输入边依附的两个顶点的序号i,j；4.2 将邻接矩阵的第将邻接矩阵的第i行第行第j列的元素值置为列的元素值置为1；4.3 将邻接矩阵的第将邻接矩阵的第j行第行第i列的元素值置为列的元素值置为1；6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第24页/共1

17、17页void creatMGraph(MGraph&G)printf(“请输入顶点数和边数：”);scanf(“%d%d”,&G.vertexNum,&G.arcNum);for(i=0;iG.vertexNum;i+)printf(“请输入第%d个顶点的值:,i+1);scanf(&G.vertexi);for(i=0;iG.vertexNum;i+)/初始化邻接矩阵 for(j=0;jG.vertexNum;j+)G.arcsij=0;for(k=0;kG.arcNum;k+)/依次输入每一条边 printf(“请输入第%d条边依附的两个顶点的序号：,k+1);scanf(%d%d,&i

18、,&j);/边依附的两个顶点的序号 G.arcsij=1;G.arcsji=1;/置有边标志 创建无向图创建无向图创建无向图创建无向图有向图怎样创建？有向图怎样创建？第25页/共117页void creatMGraph(MGraph&G)printf(“请输入顶点数和弧数：”);scanf(“%d%d”,&G.vertexNum,&G.arcNum);for(i=0;iG.vertexNum;i+)printf(“请输入第%d个顶点的值:,i+1);scanf(&G.vertexi);printf(“请输入弧不存在的标志”);scanf(&flag)for(i=0;iG.vertexNum;i

19、+)/初始化邻接矩阵 for(j=0;jG.vertexNum;j+)if(i=j)G.arcsij=0;else G.arcsij=flag;/依次读入每条弧和权，建立邻接矩阵创建无向网创建无向网创建无向网创建无向网第26页/共117页/依次输入每一条弧for(k=0;kG.arcNum;k+)printf(“请输入第%d条弧的弧尾、弧头的序号和权值：,k+1);scanf(%d%d%d,&i,&j,&w);G.arcsij=w;G.arcsji=w;/置有弧的权值 创建无向网创建无向网创建无向网创建无向网有向网怎样创建？有向网怎样创建？第27页/共117页基于邻接矩阵的基于邻接矩阵的连通图

20、连通图基本操作基本操作深度优先遍历深度优先遍历void DFS(MGraph G,int v,int visited)/)/递归递归 printf(G.vertexv);visited v=1;for(j=0;jG.vertexNum;j+)if(G.arcsvj=1&visitedj=0)DFS(G,j,visited);6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现其中：其中：v是顶点编号，是顶点编号，visited指向一个存放指向一个存放顶点是否遍历过的标志数组，初始值为顶点是否遍历过的标志数组，初始值为0第28页/共117页分析在图的邻接矩阵上

21、的递归的深度优先遍历过程ADBC1 10 02 23 3第29页/共117页 A B C D 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 01A1BC1D1第30页/共117页基于邻接矩阵的基于邻接矩阵的非连通图非连通图基本操作基本操作深度优先遍历深度优先遍历void DFSTraverse(void DFSTraverse(MGraphMGraph G)G)/对图对图 G G 作深度优先遍历作深度优先遍历 for(v=0;vG.vertexNum;+v)for(v=0;vG.vertexNum;+v)visitedv=0;/visitedv=0;/访问标志数组

22、初始化访问标志数组初始化 for(v=0;vG.vertexNum;+v)for(v=0;vG.vertexNum;+v)if(!visitedv)DFS(G,v,visited);if(!visitedv)DFS(G,v,visited);/对尚未访问的顶点调用对尚未访问的顶点调用DFSDFS 6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现如何求无向图的连通分量如何求无向图的连通分量第31页/共117页基于邻接矩阵的基于邻接矩阵的连通图连通图基本操作基本操作广度优先遍历广度优先遍历void BFS(MGraph G,int v,int visited

23、)InitQueue(Q);printf(G.vertexv);visitedv=1;EnQueue(Q,v);while(!EmptyQueue(Q)DeQueue(Q,v);for(j=0;jG.vertexNum;j+)if(G.arcsvj=1&visitedj=0)printf(G.vertexj);visitedj=1;EnQueue(Q,j);6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第32页/共117页基于邻接矩阵的基于邻接矩阵的非连通图非连通图基本操作基本操作广度优先遍历广度优先遍历void BFSTraverse(void BF

24、STraverse(MGraphMGraph G)G)/对图对图 G G 作广度优先遍历。作广度优先遍历。for(v=0;vG.vertexNum;+v)for(v=0;vG.vertexNum;+v)visitedv=0;/visitedv=0;/访问标志数组初始化访问标志数组初始化 for(v=0;vG.vertexNum;+v)for(v=0;vG.vertexNum;+v)if(!visitedv)BFS(G,v,visited);if(!visitedv)BFS(G,v,visited);/对尚未访问的顶点调用对尚未访问的顶点调用BFSBFS 6.2 6.2 图的存储结构及实现图的存

25、储结构及实现图的存储结构及实现图的存储结构及实现如何求无向图的连通分量如何求无向图的连通分量第33页/共117页邻接表邻接表邻接表邻接表邻接表存储的基本思想邻接表存储的基本思想：对于图的每个顶点：对于图的每个顶点v vi i，将所将所有邻接于有邻接于v vi i的顶点链成一个单链表，称为顶点的顶点链成一个单链表，称为顶点v vi i的的边边表表（对于有向图则称为出边表），所有边表的头指（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了针和存储顶点信息的一维数组构成了顶点表顶点表。6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现图的

26、邻接矩阵存储结构的图的邻接矩阵存储结构的空间空间复杂度？复杂度？如果为稀疏图则会出现什么现象？如果为稀疏图则会出现什么现象？假设图假设图G有有n个顶点个顶点e条边，则存储该图需要条边，则存储该图需要O(n2)。第34页/共117页vexdata firstarc顶点无向图的邻接表无向图的邻接表 adjvex nextarc 边（弧）BACDFE012345102030405060704 1012345ABCDEF35 25 01 123 045 无向网的邻接表无向网的邻接表 adjvex info nextarc已知图的邻接表，如何求无向图中的顶点vi的度和边数?1 104 30 4 505

27、20 0 103 605 40 2 403 70 1 200 301 50 2 605 70 第35页/共117页有向图的邻接表（出度）有向图的邻接表（出度）1 4230 120 1 2 3 4 A B C D EABECD可见，在有向图的邻接表中不易找到以该顶点为弧头的弧（入度）。AB弧尾弧头第36页/共117页ABECD有向图的有向图的逆逆邻接表邻接表（入度）（入度）在有向图的逆邻接表中，不易找到以该顶点为弧尾的弧（出度）。4A B C D E 03310012342AB弧尾弧头第37页/共117页10323101 V1 V2 V3 V40123vertex firstedge6.2 6.

28、2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表无向图的邻接表边表中的结点表示什么？边表中的结点表示什么？每个结点对应图中的一条边，每个结点对应图中的一条边，邻接表的空间复杂度为邻接表的空间复杂度为O(n+e)。第38页/共117页10323101 V1 V2 V3 V40123vertex firstedge6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表无向图的邻接表如何求顶点如何求顶点 i 的度？的度？顶点顶点i的边表中结点的个数。的边表中结点的个数。第39页/

29、共117页如何判断顶点如何判断顶点 i 和顶点和顶点 j之间是否存在边之间是否存在边?测试顶点测试顶点 i 的边表中是否存的边表中是否存在邻接点为在邻接点为 j 的结点。的结点。6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2无向图的邻接表无向图的邻接表第40页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex fi

30、rstedge如何求顶点如何求顶点 i 的出度？的出度？顶点顶点 i 的出边表中结点的个数。的出边表中结点的个数。第41页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的入度？的入度？各顶点的出边表中以顶点各顶点的出边表中以顶点 i 为为终点的结点个数。终点的结点个数。第42页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接

31、表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？遍历顶点遍历顶点 i 的边表，该边表中的的边表，该边表中的所有结点都是顶点所有结点都是顶点 i 的邻接点。的邻接点。第43页/共117页6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现有向网的邻接表有向网的邻接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 0第44页/共117页邻接表有两种结点结构：顶点表结点和边表结点邻接表有两种结点结构：顶点表结

32、点和边表结点。vertexfirstedge adjvex next 顶点表顶点表 边表边表 vertex：数据域，存放顶点信息。数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。指针域，指向边表中的下一个结点。6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第45页/共117页邻邻接接表表存存储储类类型型的的描描述述#define MaxSize 20 /图的最大顶点数图的最

33、大顶点数typedef struct ArcNode int adjvex;/存顶点的编号存顶点的编号 struct ArcNode*next;ArcNode;/边表结点的数据类型边表结点的数据类型typedef struct VertexNode Gelemtype vertex;/存顶点值存顶点值 ArcNode*firstedge;/存边表的头指针存边表的头指针 VertexNode;/顶点表结点的数据类型顶点表结点的数据类型typedef struct ALGraph VertexNode adjlistMaxSize;int vertexNum,arcNum;ALGraph;/邻接表

34、数据类型邻接表数据类型6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现1230 V1 V2 V3 V40123vertex firstedge第46页/共117页创建无向图的邻接表存储结构（1）给出实例和编号ADBC1 10 02 23 3确定顶点编号确定顶点编号确定输入边的顺序确定输入边的顺序第47页/共117页创建无向图的邻接表存储结构（2）画出实例的邻接表存储结构示意图ADBC1 10 02 23 30A1B2C3D 453 2 1 2 0 3 1 0 2 0 第48页/共117页创建无向图的邻接表存储结构（3）根据邻接表存储结构，设计存放数据的顺

35、序ADBC1 10 02 23 33 2 1 0A2 0 1B3 1 0 2C2 0 3D 45第49页/共117页邻接表的无向图基本操作邻接表的无向图基本操作 创建函数创建函数 1.输入图的顶点个数和边的个数；输入图的顶点个数和边的个数；2.输入顶点信息，初始化该顶点的边表；输入顶点信息，初始化该顶点的边表；3.依次输入边的信息并存储在边表中；依次输入边的信息并存储在边表中；3.1 输入边所依附的两个顶点的序号输入边所依附的两个顶点的序号i和和j；3.2 生成邻接点序号为生成邻接点序号为j的边表结点的边表结点s s；3.3 将结点将结点s s插入到第插入到第i个边表的头部；个边表的头部；3.

36、4 生成邻接点序号为生成邻接点序号为i的边表结点的边表结点s s；3.5 将结点将结点s s插入到第插入到第j个边表的头部；个边表的头部；6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第50页/共117页void creatALgraph(ALGraph&G)/无向图无向图 printf(“请输入顶点数和边数请输入顶点数和边数m,n:”);scanf(“%d,%d”,&G.vertexNum,&G.arcNum);/输入顶点信息，初始化边表输入顶点信息，初始化边表 for(i=0;iG.vertexNum;i+)printf(“(“请输入第请输入第%d

37、%d个顶点信息个顶点信息:”,i+1);:”,i+1);scanf(&G.adjlisti.vertex);G.adjlisti.firstedge=NULL;6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现邻接表的无向图基本操作邻接表的无向图基本操作创建函数创建函数 第51页/共117页/依次输入边的信息存储在边表中依次输入边的信息存储在边表中for(k=0;kadjvex=j;/新建边结点新建边结点，头插，头插 s-next=G.adjlisti.firstedge;/(vi,vj)G.adjlisti.firstedge=s;s=new ArcNo

38、de;s-adjvex=i;/新建边结点新建边结点，头插，头插 s-next=G.adjlistj.firstedge;/(vj,vi)G.adjlistj.firstedge=s;s12 V1 V2 V3 V40123无向网、有向图、有向网无向网、有向图、有向网怎样创建？怎样创建？第52页/共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作深度优先遍历深度优先遍历6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现（1 1）画出邻接表存储结构示意图）画出邻接表存储结构示意图3 2 1 0A2 0 1B3 1 0 2C2 0 3D 45第53页/

39、共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作深度优先遍历深度优先遍历6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现（2 2）选取起始点，进行深度优先遍历分析）选取起始点，进行深度优先遍历分析3 2 1 0A2 0 1B3 1 0 2C2 0 3D 0 0 0 00123访问标志数组假定起始点编号为假定起始点编号为0 0A遍历结果遍历结果p1DpCp1pB1pppppppppp1第54页/共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作深度优先遍历深度优先遍历递归递归算法算法void DFS(ALGraph G,int v

40、,int visited)printf(G.adjlistv.vertex);visitedv=1;p=G.adjlistv.firstedge;/获取边表的头指针获取边表的头指针 while(p!=NULL)j=p-adjvex;/获取顶点的编号获取顶点的编号 if(visitedj=0)DFS(G,G,j,visited);/从从j出发出发 p=p-next;/找下一个邻接点找下一个邻接点 6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第55页/共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作深度优先遍历深度优先遍历非递归非递归算法算

41、法6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现3 2 1 0A2 0 1B3 1 0 2C2 0 3D 0 0 0 00123访问标志数组访问标志数组假定起始点编号为假定起始点编号为0 0A遍历结果遍历结果p1DpCp1pB1pppppppppp1栈栈03 2 1第56页/共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作深度优先遍历深度优先遍历非递归非递归算法算法6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现void DFS_N0(ALGraph G,int v)int visitedMaxSi

42、ze=0;initStack(S);printf(G.adjlistv.vertex);visitedv=1;push(S,v);while(!EmptyStack(S)j=getTop(S);p=G.adjlistj.firstedge;/得到头指针得到头指针 while(p!=NULL)(p!=NULL)/从边表中找未访问过的邻接点从边表中找未访问过的邻接点 k=p-adjvex;/获取与获取与j相邻的邻接点编号相邻的邻接点编号 if(visitedk=0)printf(G.adjlistk.vertex);visitedk=1;push(S,k);break；else p=p-next;

43、/找下一个邻接点找下一个邻接点 if(p=NULL)pop(S);/将完成深度遍历的顶点出栈将完成深度遍历的顶点出栈 第57页/共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作广度优先遍历广度优先遍历6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现3 2 1 0A2 0 1B3 1 0 2C2 0 3D队列队列访问标志数组访问标志数组起始点选编号为起始点选编号为2 2的顶点的顶点遍历结果遍历结果 0 0 0 101230000C12P P3P P1P P0P PDP PP PP PBP PP PP PAP PP PP PP P111第58页

44、/共117页基于邻接表的连通图基本操作基于邻接表的连通图基本操作广度优先遍历广度优先遍历void BFS(ALGraph G,int v,int visited)InitQueue(Q);printf(G.adjlistv.vertex);visitedv=1;EnQueue(Q,v);/顶点编号进队列顶点编号进队列 while(!EmptyQueue(Q)DeQueue(Q,v);p=G.adjlistv.firstedge;while(p!=NULL)j=p-adjvex;/获取有邻接关系的顶点编号获取有邻接关系的顶点编号 if(visitedj=0)printf(G.adjlistj.v

45、ertex);visitedj=1;EnQueue(Q,j);/有邻接关系的顶点编号进队列有邻接关系的顶点编号进队列 p=p-next;/找下一个邻接点找下一个邻接点 6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第59页/共117页邻接表邻接表6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现逆邻接表逆邻接表V1V2V3V412 3 0v1v2v3v401231 3 0 2 v1v2v3v4012303 分析：在什么情况下，用什么邻接表分析：在什么情况下，用什么邻接表第60页/共117页图的存储结构的比较图的存储

46、结构的比较图的存储结构的比较图的存储结构的比较邻接矩阵和邻接表邻接矩阵和邻接表邻接矩阵和邻接表邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n*e）空间性能 时间性能 适用范围 唯一性邻接矩阵邻接表稠密图稠密图稀疏图稀疏图唯一唯一不唯一不唯一6.2 6.2 图的存储结构及实现图的存储结构及实现图的存储结构及实现图的存储结构及实现第61页/共117页 图的遍历应用举例图的遍历应用举例1.求无向图的一条求无向图的一条从顶点从顶点 i 到顶点到顶点 s 的简单路径的简单路径2.求无向图的两个顶点之间的一条求无向图的两个顶点之间的一条路径长度最短路径长度最短的路径的路径3.基于遍历算法的基于遍历

47、算法的查询查询（深度遍历或深度遍历或广度遍历）广度遍历）（深度优先遍历）（深度优先遍历）（广度优先遍历）（广度优先遍历）第62页/共117页1.求一条求一条从顶点从顶点 i 到顶点到顶点 s 的简单路径的简单路径abchdekfg 求从顶点 b b 到顶点 k k 的一条简单路径。从顶点 b 出发进行深度优先搜索遍历例如:假设找到的第一个邻接点是a,且得到的结点访问序列为:b a d h c e k f g 假设找到的第一个邻接点是c,则得到的结点访问序列为:b c h d a e k f gdhc不是简单路径上的点第63页/共117页1.从顶点 i 到顶点 s,若存在路径，则从顶点 i 出发

48、进行深度优先搜索，必能搜索到顶点 s。结论:2.由顶点 i 出发进行的深度优先遍历已经完成的顶点（所有的邻接点都已经被访问过）一定不是顶点i到顶点s路径上的顶点。在遍历的过程中，凡是该点的所有邻接点都被访问过，但是还没到达目的地，该点必须被删除。第64页/共117页如：b c h d a e k f g中的c h d a e 这些点在遍历过程中不满足所有的邻接点都被访问过，应保留。b到k的简单路径为：b c h d a e k 如：b a d h c e k f g中的d h c 这些点在遍历过程中满足所有的邻接点都被访问过，应删除。b到k的简单路径为：b a e k 第65页/共117页vo

49、id DFSearch(MGraph G,int v,int s,STACK&PATH,int visited,int&found)/从第从第v个顶点出发递归深度优先遍历图个顶点出发递归深度优先遍历图G，/求得一条从求得一条从v到到s的简单路径，并记录在的简单路径，并记录在PATH中中 visitedv=1;/访问第访问第 v 个顶点个顶点 push(PATH,G.vertexv);/第第v个顶点加入路径个顶点加入路径 for(j=0;j41-3第77页/共117页1)将链队列的结点改为将链队列的结点改为“双链双链”结点结点。即结点中包含next 和prior两个指针;2)修改入队列的操作。插

50、入新的队尾结点时，令其prior域的指针指向刚刚出队列的结点，即当前的队头指针所指结点;3)修改出队列的操作。出队列时，将队头指针移动到当前队头指针的后继，而不将队头结点从链表中删除第78页/共117页typedef struct DuLinkListint data;struct DuLinkList*prior,*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;3 1 2 4 7 5 Q.frontQ.rear第79页/共117页/队列初始化队列初始化void InitQueue(Link