《数据结构》教案第六章 图.docx

《《数据结构》教案第六章 图.docx》由会员分享，可在线阅读，更多相关《《数据结构》教案第六章 图.docx（28页珍藏版）》请在三一办公上搜索。

1、数据结构教案第六章 图 程序设计算法篇 图 图的遍历算法及其应用 目 录 第6章 图.2 6.1 图的定义和基本术语.2 6.2 图的存储和创建.3 6.2.1 图的存储表示.3 6.2.2 图的创建.6 6.3 图的遍历 .6 6.3.1 深度优先搜索.6 6.3.2 广度优先搜索.7 6.4 遍历算法的应用.8 6.4.1 应用问题概述.8 6.4.2 求一条包含图中所有顶点的简单路径.9 6.4.3 求距v0最短路径长度最长的一个顶点 . 10 6.5 图的连通性问题. 11 6.5.1 无向图的连通分量和生成树. 11 6.5.2 最小生成树 . 13 6.6 有向无环图及其应用. 1

2、3 文档编号 完成时间 修改时间 成 人 张 昱 完第 1 页 程序设计算法篇 图 图的遍历算法及其应用 第6章 图 6.1 图的定义和基本术语 1、图的特征 任意两个数据元素之间都可能相关。结点之间的关系是多对多的。 G = (V,E) 2、基本术语 结点： 顶点 结点间的关系：无向图：边(v,w)，v与w互为邻接点，边(v,w)依附于顶点v,w，边(v,w)和顶点v,w相关联 v的度：和v相关联的边的数目。 有向图：弧，v弧尾，w弧头，顶点v邻接到顶点w，顶点w邻接自顶点v，弧和顶点v,w相关联。 v的入度：以v为头的弧的数目；v的出度：以v为尾的弧的数目； v的度：v的入度与出度之和。

3、路径、回路(环)、简单路径、简单回路(简单环) 连通性：若从顶点v到顶点v有路径，则称v和v是连通的 图的规模：顶点数n、边(弧)数e、顶点的度(有向图：入度/出度) 子图：G= (V,E), G = (V,E)，若VV且E E，则称G是G的子图。 图的分类： 1）关系的方向性、关系上是否有附加的数权(图/网) 有向图、无向图、有向网、无向网 2）边(弧)数：完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图) 稀疏图(enlogn) 3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林 有向图：强/弱连通

4、图、强连通分量、生成树(极小连通子图)、生成森林 3、抽象数据类型定义 ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R = VR VR = |v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w) 定义了弧的意义或信息 基本操作： CreateGraph(&G, V, VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DestroyGraph(&G) 初始条件：图G存在 操作结果：销毁图G LocateVex(G,u) 初始条件：图G已存在，u和G中顶点有相同特征 文档编号 完成时间 修改时间 成 人

5、 张 昱 完第 2 页 程序设计算法篇 图 图的遍历算法及其应用 操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其它信息 GetVex(G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的值 PutVex(&G, v, value) 初始条件：图G存在，v是G中某个顶点 操作结果：对v赋值value FirstAdjVex(G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空” NextAdjVex(G, v, w) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 操作结果：返回v的(相对

6、于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空” InsertVex(&G, v) 初始条件：图G存在，v和G中顶点有相同特征 操作结果：在图中增添新顶点v DeleteVex(&G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的弧 InsertArc(&G, v, w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：在图G中增添弧，若G是无向的，则还应增添对称弧 DeleteArc(&G, v, w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：删除G中的弧，若G是无向的，则还应删除对称弧 DFSTraverse(G, v, vi

7、sit) 初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数 操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit一次且至多一次。一旦visit失败，则操作失败 BFSTraverse(G, v, visit) 初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数 操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit一次且至多一次。一旦visit失败，则操作失败 ADT Graph 6.2 图的存储和创建 6.2.1 图的存储表示 1、图的存储表示分析 顶点之间的关系是多对多的(m:n)，由于m和n都是不定的，无法给出一个这种多对多

8、的关系向线性关系的映射公式 图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反映；必须另外引入存储空间反映顶点之间的邻接关系。 文档编号 完成时间 修改时间 成 人 张 昱 完第 3 页 程序设计算法篇 图 图的遍历算法及其应用 图的存储结构：1）顶点信息；2）边(弧)信息；3）整体信息：顶点数、边(弧)数、图的种类(有向图、无向图、有向网、无向网) 顶点集的存储：图的应用中，顶点集动态变化的几率十分小 顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间 #define MAX_VERTEX_NUM 20 /* 最大顶点数 */ 注意：顺序表与顺序映像之间的区

9、别 关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的，且在实际应用中，可能会改变图中的顶点之间的关系。 邻接矩阵表示法：矩阵中的第i行第j列的元素反映图中第i个顶点到第j个顶点是否存在弧，若存在其附加的信息是什么。 邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于有向图/网来说，该邻接表反映的是顶点的出边表。 typedef enumDG, DN, AG, AN GraphKind; /*有向图，有向网，无向图，无向网*/ 2、邻接矩阵表示法 无向图/网：对称矩阵 有向图/网：非对称矩阵 图：邻接关系用1/0表示 网：邻接关系需要进一步反映权值，用INFINITY表示无

10、穷大，反映顶点之间无邻接关系 #define INT_MAX 32767 /* 最大整数 */ #define INFINITY INT_MAX 1) 邻接矩阵 typedef struct ArcCell int adj; /* 顶点间关系，无权图：0-不相邻，1-相邻 有权图，权值，INFINITY-不相邻 */ InfoType *info; /* 该弧相关信息的指针 */ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; 2) 图的整体结构 typedef struct char AdjMatrix int GraphKind MGraph

11、; 3、邻接表表示法 vexsMAX_VERTEX_NUM; /* 有效的顶点下标从0开始 */ arcs; /* 关系集 */ vexnum, arcnum; /* 顶点数、边/弧数 */ kind; /* 图的种类 */ 无向图/网：边表，表结点的个数为边数的两倍 有向图/网：出边表，表结点的个数为弧数 1) 邻接表的表结点 typedef struct ArcNode int adjvex; /* 弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; ArcNode; 文档编号 完成时间 修改时间 成

12、 人 张 昱 完第 4 页 程序设计算法篇 图 图的遍历算法及其应用 2) 邻接表的头结点 typedef struct VNode char data; /* 顶点信息 */ ArcNode *firstarc; /* 邻接表指针 */ VNode, AdjListMAX_VERTEX_NUM; 3) 图的整体结构 typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; 4、邻接矩阵与邻接表的对比 假设图为G，顶点数为n，边/弧数为e。 A邻接矩阵 2O(n+n) 存储空间 图的创建算法 B邻

13、接表 O(n+e) T1(n)=O(e+n2)或T2(n)=O(e*n+n2) T1(n)=O(n+e)或T2(n)=O(e*n) T1(n)是指在输入边/弧时，输入的顶点信息为顶点的编号；而T2(n)则指在输入边/弧时，输入的为顶点本身的信息，此时需要查找顶点在图中的位置 n-1无向图中求第i顶点的度 G.arcsij.adjj=0n-1(第i行之和)或 G.verticesi.firstarc所指向的邻接表包含的结点个数 j=0G.arcsji.adj(第i列之和) 无向网中求第i行/列中adj值不为INFINITY的第i顶点的度 元素个数 n-1有向图中求第i顶点的入/出度 入度：G.a

14、rcsji.adj(第i列) j=0n-1有向网中求第i顶点的入/出度 入度：扫描各顶点的邻接表，统计表结点的adjvex为i的表结点个数出度：G.arcsij.adj(第i行) T(n)=O(n+e) j=0入度：第i列中adj值不为INFINITY出度：G.verticesi.firstarc所指向的元素个数 的邻接表包含的结点个数 出度：第i行中adj值不为INFINITY的元素个数 无向图：1n-1n-1G.arcsij.adj2i=0j=0) 无向图/网：图中表结点数目的一半 有向图/网：图中表结点的数目 统计边/弧数 无向网：G.arcs中adj值不为INFINITY的元素个数的一

15、半 n-1n-1有向图：G.arcsij.adji=0j=0有向网：G.arcs中adj值不为INFINITY的元素个数 结论：邻接矩阵适于稠密图，邻接表适于稀疏图；邻接表求有向图的顶点的入度不方便，文档编号 完成时间 修改时间 成 人 张 昱 完第 5 页 程序设计算法篇 图 图的遍历算法及其应用 要遍历全部的邻接表。 6.2.2 图的创建 基本过程： 1） 输入图的类型，根据类型选择相应的创建算法 2） 输入图的顶点数，边/弧数 3） 输入并存储顶点信息 4） 输入边/弧所关联的顶点对，将边或弧的信息存储到邻接矩阵/邻接表中 图的存储结构不同、图的类型不同，都会影响创建算法的实现细节；但是

16、，图的总体创建流程是一致的。 示例：用邻接矩阵表示法构造有向网G Status CreateMDG(MGraph &G) /* 步骤2：输入图的顶点数、边/弧数 */ scanf(&G.vexnum, &G.arcnum, &IncInfo); /* IncInfo为0则各弧不含其它信息 */ /* 步骤3：输入并存储顶点信息 */ for ( i = 0; i G.vexnum ; i+) scanf ( &G.vexsi ); /* 步骤4：输入并存储边/弧信息 */ for ( i = 0; i G.vexnum ; i+) /* 邻接矩阵初始化 */ for ( j = 0; j G.

17、vexnum ; j+) G.arcsij = INFINITY, NULL; for ( k = 0; k G.arcnum ; k+) scanf(&v1, &v2, &w); i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcsij.adj = w; if ( IncInfo) Input( *G.arcsij.info); /* *G.arcsij.info要求G.arcsij.info指向的空间在调用Input前分配 */ 6.3 图的遍历 6.3.1 深度优先搜索 1、分析 类似于树的先序遍历 引入访问标志数组visit0:n-1，区

18、分顶点是否已被访问 非连通图，需引入多个深度优先搜索的起始顶点 递归算法或基于栈的非递归算法 2、基于逻辑结构的算法 Boolean visitedMAX_VERTEX_NUM; void DFSTraverse(Graph G) for ( v = 0; v G.vexnum; + v) visitedv = FALSE; for ( v = 0; v G.vexnum; + v) if ( !visitedv ) DFS(G, v); void DFS(Graph G, int v) 文档编号 完成时间 修改时间 成 人 张 昱 完第 6 页 程序设计算法篇 图 图的遍历算法及其应用 vi

19、sitedv = TRUE; Visit(G, v); for ( w = FirstAdjVex( G, v); w; w = NextAdjVex(G, v, w) ) if ( !visitedw ) DFS(G, w); 3、基于某种存储结构的算法 根据选择的存储结构，决定 FirstAdjVex和NextAdjVex的实现，重新整合算法。 如采用邻接矩阵表示法表示的图，则DFS算法如下： void DFS (MGraph G, int v) visitedv = TRUE; Visit(G, v); for ( w = 0; w nextarc) if (!visitedp-adjv

20、ex ) DFS(G, p-adjvex); 6.3.2 广度优先搜索 1、分析 类似于树的层次遍历 引入visited访问标志数组 非连通图，需引入多个广度优先搜索的起始顶点 引入队列保存“顶点已访问，但其邻接点未全访问”的顶点编号 2、基于逻辑结构的算法 void BFSTraverse(Graph G) for ( v = 0; v G.vexnum; + v) visitedv = FALSE; InitQueue(Q); for ( v = 0; v G.vexnum; + v) if ( !visitedv ) /* 访问某连通分量的起始顶点，起点入队 */ visitedv =

21、TRUE; Visit(G, v); EnQueue(Q, v); while(!QueueEmpty(Q) /* 出队，访问出队元素的邻接点 */ DeQueue(Q,u); for ( w = FirstAdjVex( G, u) ; w ; w = NextAdjVex(G, u, w) if ( !visitedw ) /* 访问顶点u的尚未访问的邻接点并入队 */ visitedw = TRUE; Visit(G, w); EnQueue(Q, w); 文档编号 完成时间 修改时间 成 人 张 昱 完第 7 页 程序设计算法篇 图 图的遍历算法及其应用 3、基于某种存储结构的算法 如

22、采用邻接矩阵表示法表示的网，则算法如下： void BFSTraverse(MGraph G) for ( v = 0; v G.vexnum; + v) visitedv = FALSE; InitQueue(Q); for ( v = 0; v G.vexnum; + v) if ( !visitedv ) /* 访问某连通分量的起始顶点，起点入队 */ visitedv = TRUE; Visit(G, v); EnQueue(Q, v); while(!QueueEmpty(Q) /* 出队，访问出队元素的邻接点 */ DeQueue(Q,u); for ( w = 0 ; w G.v

23、exnum; w + ) if ( G.arcsuw.adj != INFINITY & !visitedw ) /* 访问顶点u的尚未访问的邻接点并入队 */ visitedw = TRUE; Visit(G, w); EnQueue(Q, w); 如采用邻接表表示法表示的网，则算法如下： void BFSTraverse(ALGraph G) for ( v = 0; v G.vexnum; + v) visitedv = FALSE; InitQueue(Q); for ( v = 0; v nextarc ) if ( !visitedp-adjvex ) /* 访问顶点u的尚未访问的

24、邻接点并入队 */ visitedp-adjvex = TRUE; Visit(G, p-adjvex); EnQueue(Q, p-adjvex); 6.4 遍历算法的应用 6.4.1 应用问题概述 文档编号 完成时间 修改时间 成 人 张 昱 完第 8 页 程序设计算法篇 图 图的遍历算法及其应用 图的深度优先遍历： 1、 求一条包含图中所有顶点的简单路径(简单回路) 2、 判断图中是否存在环 3、 求图中通过给定顶点vk的简单回路 4、 判断是否存在从顶点vi到顶点vj的的路径 图的广度优先遍历： 1、 判断是否存在从顶点vi到顶点vj的的路径 2、 求距v0最短路径长度最长的一个顶点。

25、 3、 求v0和v1之间的最短路径. 4、 在顶点子集U中找出距离顶点v0最近的顶点 5、 求顶点v0到其余每个顶点的最短路径 6、 求距离顶点v0的最短路径长度为k的所有顶点 7、 判别v0和v1之间是否存在一条长度为k的路径 6.4.2 求一条包含图中所有顶点的简单路径 1、思路 对于任意的有向图或无向图G，并不一定都能找到符合题意的简单路径。这样的简单路径要求包含G.vexnum个顶点，且互不相同。它的查找可以基于深度优先遍历。 在一个存在包含全部顶点的简单路径的图中，以下因素会影响该简单路径是否能顺利地查到： 1 1 1） 起点的选择：如图(a)，其符合题意的一条简单4 4 2 2 路

26、径如图(b)。若起点为1，则不能找到符合题3 3 意的简单路径； 5 7 5 7 2） 顶点的邻接点次序：进一步考察图(a)，即使以6 6 2为起点，但是2的邻接点选择的是1，而不是(a) (b) 5，此时也不能找到符合题意的解。 在基于DFS的查找算法中，由于起点和邻接点的选取是与顶点和邻接点的存储次序以及算法的搜索次序有关，不可能依据特定的图给出特定的解决算法。因此，在整个搜索中应允许有查找失败，此时可采取回溯到上一层的方法，继续查找其他路径。 这样，引入数组Path用来保存当前已搜索的简单路径上的顶点，引入计数器n用来记录当前该路径上的顶点数。 对DFS算法的修改如下： 1） 计数器n的

27、初始化，放在visited的初始化前后； 2） 访问顶点时，增加将该顶点序号入数组Path中，计数器n+；判断是否已获得所求路径，是则输出结束，否则继续遍历邻接点； 3） 某顶点的全部邻接点都访问后，仍未得到简单路径，则回溯，将该顶点置为未访问，计数器n-。 2、算法 /* 邻接矩阵表示法, 粗体字部分为在深度优先遍历上的增加或修改的步骤 */ void Hamilton(MGraph G) for(i=0; iG.vexnum; i+) visitedi=FALSE; n=0; 文档编号 完成时间 修改时间 成 人 张 昱 完第 9 页 程序设计算法篇 图 图的遍历算法及其应用 for(i=

28、0; iG.vexnum; i+) if ( !visitedi) DFS (G, i); void DFS(MGraph G, int i) visitedi=TRUE; Pathn=i; n+; if(n=G.vexnum) Print(Path); /* 符合条件，输出该简单路径 */ for(j=0; jG.vexnum; j+) if( G.arcsij.adj & !visitedj) DFS( G, j); visitedi=FALSE; n-; 3、思考 1） 若图中存在多条符合条件的路径，本算法是输出一条，还是输出全部？ 2） 如何修改算法，变成判断是否有包含全部顶点的简单路

29、径？ 3） 如何修改算法，输出包含全部顶点的简单路径的条数？ 4） 如何修改算法，输出所有的简单回路？ 5） 考虑其他图的存储方法对算法的影响； 6） 考虑在非递归的深度优先遍历算法上，如何修改使之适应本问题的求解。 6.4.3 求距v0最短路径长度最长的一个顶点 1、思路 由于题意强调为最短路径，因此应当考虑BFS的算法应用。本问题的求解转变成：从v0出发进行BFS，最后一层的顶点距离v0的最短路径长度最长。 由于BFS类似于树的按层次遍历，需要引入队列用来保存本身已访问但其邻接点尚未全部访问的顶点。BFS遍历中最后一层的顶点一定是最后出队的若干顶点，队列中最后一个出队的顶点必定是符合题意的

30、顶点。 这样，只需调用BFS的算法，将最后出队的元素返回即可。 2、算法 int MaxDistance(MGraph G, int v0) /* 初始化各顶点的访问标志，设置为未访问 */ for(i=0; iG.vexnum; i+) visitedi=FALSE; InitQueue(Q); /* 不需要考虑其他的连通分量，因为所求的顶点必定与v0在同一个连通分量中 */ EnQueue(Q, v0); visitedv0 = TRUE; while( !QueueEmpty(Q) DeQueue(Q, v); for(w = 0; w G.vexnum; w+) if(G.arcsvw

31、.adj & !visitedw ) 文档编号 完成时间 修改时间 成 人 张 昱 完第 10 页 程序设计算法篇 图 图的遍历算法及其应用 visitedw=TRUE; EnQueue(Q, w); return(v); 3、思考 1） 若要求输出满足条件的全部顶点，则如何修改上述算法； 2） 考虑其它图的存储表示下的算法实现。 4、其它类似的应用 求v0和v1之间的最短路径； 在顶点子集U中找出距离顶点v0最近的顶点； 求顶点v0到其余每个顶点的最短路径； 求距离顶点v0的最短路径长度为K的所有顶点； 判别v0和v1之间是否存在长度为K的路径。 6.5 图的连通性问题 6.5.1 无向图的

32、连通分量和生成树 1、基本概念 连通分量的顶点集：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列； 生成树： 某连通分量的极小连通子图 深度优先搜索生成树、广度优先搜索生成树 由该连通分量的顶点集和搜索所经过的边组成 生成森林：非连通图的各个连通分量的极小连通子图构成的集合 2、算法思路 也是图的遍历算法的应用 将访问顶点变成创建生成树或增加一个结点到生成树中的操作 生成树/森林的存储表示采用孩子-兄弟表示法 3、深度优先搜索生成树/森林算法思路 /* 基于抽象数据类型(逻辑结构)的算法 */ void DFSForest(Graph G, CSTree &T) T = NULL;

33、for ( v = 0; v G.vexnum; + v) visitedv = FALSE; for ( v = 0; v nextsbling = p; /* 其它生成树的根(前一棵的“兄弟”) */ q = p; /* q指示当前生成树的根 */ DFSTree(G, v, p); /* 建立以p指向的结点为根结点的生成树 */ void DFSTree(Graph G, int v, CSTree & T) 文档编号 完成时间 修改时间 成 人 张 昱 完第 11 页 程序设计算法篇 图 图的遍历算法及其应用 visitedv = TRUE; Visit(G, v); first =

34、TRUE; /* 标识下一个访问的邻接点是否为第一个未访问的邻接点 */ for ( w = FirstAdjVex( G, v); w; w = NextAdjVex(G, v, w) ) if ( !visitedw ) p = ( CSTree ) malloc(sizeof(CSNode); /* 分配孩子结点 */ p = GetVex(G, w), NULL, NULL; if ( first ) /* w是v的第一个未访问的邻接点 */ T-firstchild = p; first = FALSE; /*是根的第一个孩子 */ else q-nextsbling = p; /*

35、 是上一邻接点的右兄弟结点 */ q = p; /* 修改上一孩子结点的指针 */ DFSTree(G, w, q); 4、广度优先搜索生成树/森林算法思路 引入队列，除了保存“顶点已访问，但其邻接点未全访问”的顶点编号以外，还须保存该顶点在生成树中的对应结点的指针。 void BFSForest(Graph G, CSTree &T) T = NULL; for ( v = 0; v G.vexnum; + v) visitedv = FALSE; InitQueue(Q); for ( v = 0; v nextsbling = p; /* 其它生成树的根(前一棵的“兄弟”) */ q =

36、 p; /* q指示当前生成树的根 */ EnQueue(Q, v, p); while(!QueueEmpty(Q) /* 出队，访问出队元素的邻接点 */ DeQueue(Q,u, q); first = TRUE; for ( w = FirstAdjVex( G, u) ; w ; w = NextAdjVex(G, u, w) if ( !visitedw ) /* 访问顶点u的尚未访问的邻接点并入队 */ visitedw = TRUE; p = ( CSTree ) malloc(sizeof(CSNode); /* 分配孩子结点 */ p = GetVex(G, w), NUL

37、L, NULL; if ( first ) /* w是v的第一个未访问的邻接点 */ q-firstchild = p; first = FALSE; /*是根的第一个孩子 */ else q-nextsbling = p; /* 是上一邻接点的右兄弟结点 */ q = p; /* 修改上一孩子结点的指针 */ 文档编号 完成时间 修改时间 成 人 张 昱 完第 12 页 程序设计算法篇 图 图的遍历算法及其应用 EnQueue(Q, w, p); 6.5.2 最小生成树 1、概念 应用的图的类型：连通网 最小生成树：树上各边权值之和最小的生成树 MST性质 2、普里姆算法 3、克鲁斯卡尔算法