数据结构第7章(2)

1、数 据 结 构 第第7 7章章 图图北华航天工业学院计算机系 制作目目 标标理解图的基本概念及术语；理解图的基本概念及术语；掌握图的两种存储结构掌握图的两种存储结构( (邻接矩阵和邻接表邻接矩阵和邻接表) )；熟练掌握图的两种遍历的算法思想、步骤；熟练掌握图的两种遍历的算法思想、步骤；掌握按掌握按PrimPrim和和KruskalKruskal算法构造最小生成树的步骤；算法构造最小生成树的步骤；领会并掌握求拓扑排序、关键路径、最短路径的领会并掌握求拓扑排序、关键路径、最短路径的过程。过程。 北华航天工业学院计算机系 制作本章内容本章内容7.1 图的定义和术语图的定义和术语7.2 图的存储结构图

2、的存储结构7.3 图的遍历图的遍历7.4 图的连通性问题图的连通性问题7.5 有向无环图及其应用有向无环图及其应用7.6 最短路径最短路径北华航天工业学院计算机系 制作 图的遍历是图的一种基本操作，它跟树的遍历不图的遍历是图的一种基本操作，它跟树的遍历不同，是一种复杂的操作。同，是一种复杂的操作。主要表现在以下方面：主要表现在以下方面： 图中，没有一个图中，没有一个“自然自然”的的首结点首结点。 非连通图非连通图中，从一个顶点出发，只能访问它所中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点。在的连通分量上的所有顶点。 若若存在回路存在回路，那么一个顶点被访问之后，有可，那么一个顶点被

3、访问之后，有可能沿回路又回到该顶点。能沿回路又回到该顶点。 在图中，一个顶点可以和其它顶点相连，当这在图中，一个顶点可以和其它顶点相连，当这样的顶点访问过后，存在样的顶点访问过后，存在如何选取下一个要访问的如何选取下一个要访问的顶点顶点的问题。的问题。7.3 图的遍历图的遍历北华航天工业学院计算机系 制作 解决问题的方法解决问题的方法 遍历之前选取一个顶点作为起点遍历之前选取一个顶点作为起点 为了区分顶点的状态，定义一个辅助数组。为了区分顶点的状态，定义一个辅助数组。 visitedvisited顶点总数顶点总数 未被访问时元素值为未被访问时元素值为0 0； 已被访问时元素值为已被访问时元素值

4、为1 1。 选取下一个顶点的策略：选取下一个顶点的策略： 深度优先搜索遍历深度优先搜索遍历 广度优先搜索遍历广度优先搜索遍历7.3 图的遍历图的遍历北华航天工业学院计算机系 制作7.3 图的遍历图的遍历7.3.1 7.3.1 深度优先搜索遍历深度优先搜索遍历7.3.2 7.3.2 广度优先搜索遍历广度优先搜索遍历北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索 深度优先搜索（深度优先搜索（Depth_Fisrst Search）遍历类）遍历类似于似于树的先根遍历树的先根遍历。 基本思想：基本思想：假设初始状态是图中所有顶点未曾被访问；假设初始状态是图中所有顶点未曾被访问；从图

5、中某个顶点从图中某个顶点v v出发，访问此顶点；出发，访问此顶点；然后依次从然后依次从v v的未被访问的邻接点出发深度优的未被访问的邻接点出发深度优先遍历图，直至图中所有和先遍历图，直至图中所有和v v有路径相通的顶有路径相通的顶点都被访问到；点都被访问到；若此时图中尚有顶点未被访问，则另选图中一若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。直至图中所有顶点都被访问到为止。北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索 给出下图深度优先搜索遍历的顶点序列。给出下图深

6、度优先搜索遍历的顶点序列。北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索 实现算法实现算法 （1）一种递归过程；）一种递归过程； （2）标志数组）标志数组visited ； （3）图以邻接矩阵方式存储；）图以邻接矩阵方式存储； （4）连通图和非连通图的遍历区别）连通图和非连通图的遍历区别北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索u 邻接矩阵的数据类型定义邻接矩阵的数据类型定义#define MaxVertexNum typedef enumDG,DN,UDG,UDN GraphKind; typedef struct VRType adj; Info

7、Type *info;ArcCell,AdjMatrix MaxVertexNum MaxVertexNum;typedef struct VertexType vexsMaxVertexNum; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind;MGraph ； 北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索int visitedMaxVexNum; /辅助数组定义辅助数组定义 /遍历前将所有元素全部置为遍历前将所有元素全部置为0深度优先遍历过程在邻接矩阵存储中如何实现深度优先遍历过程在邻接矩阵存储中如何实现？设定图的顶点

8、类型为字符类型。设定图的顶点类型为字符类型。 typedef char VertexType;北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索void DFS(MGraph G,int i)/从项点从项点i开始，对图进行深度优先搜索遍历的算法开始，对图进行深度优先搜索遍历的算法 coutG.vexsi ; visitedi=1; /标志已被访问标志已被访问 int j; for(j=0;jG.vexnum;j+)if(visitedj=0)&(G.arcsij=1)DFS(G,j);北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索连通图和非连通图的遍

9、历区别？连通图和非连通图的遍历区别？连通图：从连通图：从任意一个顶点出发任意一个顶点出发进行深度优先遍历，进行深度优先遍历，都可以访问到图中所有的顶点；都可以访问到图中所有的顶点；非连通图：从任意一个顶点出发进行深度优先遍非连通图：从任意一个顶点出发进行深度优先遍历，历，只能访问到包含该顶点的连通分量中的所有顶只能访问到包含该顶点的连通分量中的所有顶点点。所以，还需要在图中寻找一个还未被访问的顶。所以，还需要在图中寻找一个还未被访问的顶点，从该顶点出发进行遍历，直到所有顶点全被访点，从该顶点出发进行遍历，直到所有顶点全被访问为止。问为止。北华航天工业学院计算机系 制作7.3.1 深度优先搜索深

10、度优先搜索void DFSTraverse(MGraph G)/图的深度优先搜索遍历算法图的深度优先搜索遍历算法 int i; for(i=0;iG.vexnum;i+) visitedi=0; /置标志数组的初值为置标志数组的初值为0 for(i=0;iG.vexnum;i+) if(visitedi=0) DFS(G,i);北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索void main()MGraph G;Create(G); /创建邻接矩阵图创建邻接矩阵图 DFSTraverse(G);注意事项：注意事项： visitedvisited数组在数组在DFSTraver

11、seDFSTraverse()()和和DFS()DFS()函数中函数中都要用到，所以一种方法是将其都要用到，所以一种方法是将其定义为全局变量定义为全局变量，或者或者做为参数来传递做为参数来传递。北华航天工业学院计算机系 制作7.3.1 深度优先搜索深度优先搜索 分析算法分析算法 （1）遍历的实质就是对每个顶点查找其邻接顶）遍历的实质就是对每个顶点查找其邻接顶点的过程。点的过程。 （2）以邻接矩阵存储时，查找每个顶点的邻接）以邻接矩阵存储时，查找每个顶点的邻接点所需时间为点所需时间为o(n2)。 （3）以邻接表存储时，查找每个顶点的邻接点）以邻接表存储时，查找每个顶点的邻接点所需时间为所需时间为

12、o(n+e)。北华航天工业学院计算机系 制作7.3 图的遍历图的遍历7.3.1 7.3.1 深度优先搜索遍历深度优先搜索遍历7.3.2 7.3.2 广度优先搜索遍历广度优先搜索遍历北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索 广度优先搜索（广度优先搜索（Breadth_First SearchBreadth_First Search） 遍历遍历类似于树的按层次遍历的过程。类似于树的按层次遍历的过程。 基本思想：基本思想：从图中某顶点从图中某顶点v v出发，在访问了出发，在访问了v v之后依次访问之后依次访问v v的各个未曾访问过的邻接点；的各个未曾访问过的邻接点；然后分别

13、从这些邻接点出发依次访问它们的邻然后分别从这些邻接点出发依次访问它们的邻接点，并使接点，并使“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问，直至图被访问，直至图中所有已被访问的顶点的邻接点都被访问到。中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选一个未若此时图中尚有顶点未被访问，则另选一个未被访问的顶点作起始点，重复上述过程，直至被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。图中所有顶点都被访问到为止。北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索 给出下图广度

14、优先搜索遍历的顶点序列。给出下图广度优先搜索遍历的顶点序列。北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索 实现算法实现算法 （1）从遍历过程发现：）从遍历过程发现： “先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访问后被访问的顶点的邻接点的顶点的邻接点”被访问。被访问。 队列队列 （2）标志数组）标志数组visited ； （3）图以邻接表方式存储；）图以邻接表方式存储； （4）连通图和非连通图的遍历区别）连通图和非连通图的遍历区别北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索u 邻接表的数据类型定义邻接表的数据类型定义#define

15、MaxVertexNum struct ArcNode /定义边结点类型定义边结点类型 int adjvex； /邻接点域邻接点域 struct ArcNode *nextarc； InfoType *info;；struct VertexNode VertexType data; /存放顶点信息存放顶点信息 ArcNode *firstarc; /存放链表头指针存放链表头指针AdjListMaxVertexNum；typedef struct AdjList vertices； int vexnum, arcnum; GraphKind kind; ALGraph ；北华航天工业学院计算机系

16、 制作7.3.2 广度优先搜索广度优先搜索int visitedMaxVexNum; /辅助数组定义辅助数组定义 /遍历前将所有元素全部置为遍历前将所有元素全部置为0广度优先遍历过程在邻接表存储中如何实现广度优先遍历过程在邻接表存储中如何实现？设定图的顶点类型为字符类型。设定图的顶点类型为字符类型。 typedef char VertexType;北华航天工业学院计算机系 制作8.3.2 广度优先搜索广度优先搜索void BFS(ALGraph G,int i)ArcNode *p; int k;LQueue *Q; Q=Init_LQueue();coutadjvex=0) coutadjv

17、ex.data; visitedp-adjvex=1; In_LQueue(Q,p-adjvex); p=p-nextarc;北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索 实现算法实现算法void BFSTraverse(ALGraph G)/图的广度优先搜索遍历算法图的广度优先搜索遍历算法int i;for(i=0;iG.vexnum;i+) visitedi=0;for(i=0;iG.vexnum;i+)if(visitedi=0) BFS(G,i);北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索 实现算法实现算法void main()ALGrap

18、h G; Create(G);BFSTraverse(G);coutendl;北华航天工业学院计算机系 制作7.3.2 广度优先搜索广度优先搜索 分析算法分析算法 （1）广度优先搜索遍历图的时间复杂度和深度广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。访问的顺序不同。 （2）以邻接矩阵存储时，查找每个顶点的邻接）以邻接矩阵存储时，查找每个顶点的邻接点所需时间为点所需时间为o(n2)。 （3）以邻接表存储时，查找每个顶点的邻接点）以邻接表存储时，查找每个顶点的邻接点所需时间为所需时间为o(n+e)。北华航天工业学院计算机系 制作7.3 7.3 图的遍历