《数据结构——图讲述》由会员分享，可在线阅读，更多相关《数据结构——图讲述（106页珍藏版）》请在金锄头文库上搜索。
1、第七章 图 多对多的关系 学习要点： v图的基本概念与相关有向图、无向图、网和连通图概念。 v图的邻接矩阵与邻接表存储结构及其特性。 v图的深度优先和广度优先遍历方法及其在邻接表存储结构中的 实现算法。 v图与树的联系与区别，图的生成树与最小生成树。 v图的最短路径。 v图的应用：最短路径、拓扑排序与关键路径。 2 7.1 基本概念与相关描述 7.1.1 图的基本概念 v“图”（Graph）也称为网状结构，它由一个非空的顶点（ vertex）集合V和一个描述顶点之间邻接关系的边（edge） 集合E组成，而E中每条边连接的两个顶点都属于集合V。一 个图G可以记为：G =（V，E）。 v多对多的关
2、系，非线性结构 vV(G)：顶点的非空有限集合 vE(G)：图中边的有限集合 3 7.1.1 图的基本概念2 v有向图：弧（有向边）， v :xy,x邻接到y，y邻接自x v 与x、y相关联 v 4 v无向图：边（无向边）， v (x,y):xy,x与y相邻接 v (x,y) 与x、y相关联 v (x,y) = (y,x) 7.1.1 图的基本概念3 子图：V(B)属于V(A)，且E(B)属于E(A)， 则B是A的子图。 （B是A中的一部分） 5 7.1.2 图的相关概念 1.顶点邻接与顶点的度 顶点的度 相邻接顶点的个数，顶点vi的度记为D(vi)。 有向图顶点的度 v出度：以顶点vi为弧尾
3、的弧的个数，记为OD(vi)； v入度：以顶点vi为弧头的弧的个数，记为ID(vi)。 D(vi)=ID(vi)+OD(vi) 边数与顶点度关系 在图的顶点数n、边数e以及各顶点的度D(vi) （1in）三者之间存在如下关系： 6 2e= D(vi) 7.1.2 图的相关概念2 1.路径与路径长度 7 无向图的路径 在顶点vi与顶点vj之间存在一个边的序列：（vi, vi1），（ vi1, vi2），（vim, vj）。 有向图的路径 顶点vi与顶点vj之间存在一个弧的序列：， 。 路径长度 由顶点vi到顶点vj路径上拥有的边的个数。 简单路径与回路 若在一条路径上出现的顶点都不同，则称其为“
4、 简单路径”或“简单回路（环cycle）”。 7.1.2 图的相关概念3 3.无向完全图与有向完全图 v有向完全图：每个顶点都与其它任意顶点有弧。 v 共 条边。 n*(n-1) n*(n-1)/2 8 v无向完全图：每个顶点都与其它任意顶点有边。 v 共 条边。 7.1.2 图的相关概念4 4.连通图与连通分量 连通分量 在无向图G中，尽可能多地从集合V及E里收集顶点和 边，使它们成为该图的一个极大的连通子图，这个子图就被称 为是无向图G的一个“连通分量”。 9 连通图 在无向图G中，任意一对顶点之间都是连通的。 7.1.2 图的相关概念4 4.连通图与连通分量2 10 强连通图和弱连通图
5、在有向图G中，若对其中任意两个顶点vi和vj 互有路径可达，则称G强连通图；如果任意两个顶点都至少存在 单向路径，则称G是弱连通图。 n个顶点的强连通图应当至少有n条弧。 强连通分量和弱连通分量 有向图G中的极大强连通子图称为G的强 连通分量，而其中的极大弱连通子图称为G的弱连通分量。 7.1.2 图的相关概念5 5.边的权值与网络 11 边的权值 图的边或弧依附上的某种数值称为“权值”或“权（ weight）”。例如地图上连接两个城市的铁路线在其上附 有该铁路线的里程数等。 网络 边或弧上带有权的图称为“网络”或“网图”。 7.2 图的存储 7.2.1基于邻接矩阵存储 v用二维数组表示顶点的
6、邻接关系 1、图的邻接矩阵（n顶点用n阶方阵） 12 A = 1、图的邻接矩阵2 邻接矩阵特点： 无向图邻接矩阵对称，有向图不对称 无向图第i行(列)非零元素个数即为结点i的度 有向图第i行(列)非零元素个数即为结点i的出(入)度 容易确认任两点之间是否有边，但扫描边数代价大 （对每个结点进行检测） 13 2、网络的邻接矩阵 14 3、邻接矩阵存储算法 算法7-1 有向图G邻接矩阵算法。 设置一个一维数组Gv，用于存放G的顶点数据信息；设置一个二 维数组Ge，用于存放G中有关弧的信息；设置变量n和e，记录图的 顶点个数和弧的个数信息。 15 00 Create_Gm(MGraph *Gm) 0
7、1 02 scanf(%d,%d, /* 输入顶点和弧的个数信息 */ 03 for (i=1; in; i+) 04 scanf(%d, Gm-Gvi); 05 for (i=1; in; i+) /* 邻接矩阵初始化 */ 06 for (j=1; jn; j+) 07 if (i = j) 08 Gm-Geij = 0; 09 else 10 Gm-Geij = ; 11 for (k=1; ke; k+) /* 输入e条弧 */ 12 13 scanf (%d%d, 14 Gm-Geij = 1; 15 16 7.2.2 基于邻接表存储 00 struct enode /* 定义边结点
8、结构 */ 01 02 int adjvex; 03 struct enode *next; 04 ; 16 05 struct vnode /* 定义顶点结点结构 */ 06 07 vertextype vertex; /* 顶点类型为vertextype */ 08 struct enode *fadj; 09 ; 10 typedef struct /* 定义一个图邻接表类型 */ 11 12 struct vnode GvMAX; /* 图的邻接表 */ 13 int n, e; /* 图的顶点数、边数信息 */ 14 RGraph; 7.2.2 基于邻接表存储2 17 图7-12 图
9、7-5（5）所示无向图邻接表存储结构 7.2.2 基于邻接表存储3 网络的邻接表： 18 7.2.2 基于邻接表存储4 算法7-2 有向图邻接表存储算法。 设置由单链表表头结点组成的一维数组Gv，用于存放图的顶点序号（ vertex）以及指向顶点单链表的指针（fadj）；设置变量n和e，记录 图的顶点个数和弧的个数信息。 19 00 Create_Gr(RGraph *Gr) 01 02 struct enode *ptr; 03 scanf(%d,%d, /* 输入顶点和弧的个数信息 */ 04 for (i=1; in; i+) /* 对一维数组Gv进行初始化 */ 05 06 Gr-Gv
10、i.vertex = i; 07 Gr-Gvi.fadj = NULL; 08 09 for (k=1; ke; k+) /* 构造各顶点的单链表 */ 10 11 scanf (%d,%d, 12 ptr = (struct enode *)malloc(sizeof(enode); /* 申请新结点 */ 13 ptr-adjvex = j; 14 ptr-next = Gr-Gvi.fadj; /* 新结点链入邻接表 */ 15 Gr-Gvi.fadj = ptr; 16 17 问题：如何求有向图顶点的入度？ v解：可建立有向图的逆邻接表 20 正邻接表：方便求顶点的出度 逆邻接表：方便
11、求顶点的入度 7.3 图的遍历 从图的某一个顶点出发访问图中的所有顶点，且每个顶点 只被访问一次的过程。 21 步骤如下： v 在图G中指定一个顶点v0作为遍历开始顶点，先访问v0并将其 进行适当标记表明已被访问。 v 依次从v0的还未被访问的各个邻接顶点w出发递归地进行深度 优先搜索。 v 如果图中还存在未访问过的顶点，则选其中之一由其出发重复 上述步骤“”“”，直到图中所有顶点都被访问。 7.3.1 深度优先遍历 过程（利用栈结构）： v 指定起点q v 访问q v q进栈 v 栈空否？ v a：不空，转 v b：空，转 找栈顶元素未访问邻接点q a：找到，转 b：找不到，出栈，转 结束
12、遍历结果：n结点，（n1）条边，无回路 按遍历过程经过的边为一棵深度优先生成树。 22 例子： 求下图从顶点v0出发的深度遍历序列。 23 解： v0 v1 v3 v4 v5 v2 算法7-3 基于邻接表的无向图深度优先搜索算法 00 Depth_Gr(RGraph *Gr, int n) 01 02 for (i=1; iadjvex; 17 if (flagk = 0)/* 对未访问的顶点继续深度优先搜索 */ 18 DFS(Gr, k, flag); 19 20 25 上机： 使用邻接表存储图，编写其深度优先遍历的非递归算法。 26 过程： v 访问地点；起点进栈； v while （栈
13、不空） v 找栈顶未访问邻接点p； v if 找到 v 访问；进栈； v else v 出栈； 7.3.2 广度优先遍历 步骤如下： v 在图中指定一个顶点v0为遍历起始点，访问顶点v0并将其进行 标记以表明被访问； v 依次访问 v0 的所有相邻顶点 w1, w2, , wx ，此时需要为 v 的 邻接顶点规定一种顺序，然后依次访问与 w1, w2, , wx 邻接的所 有未访问顶点直到所有已访问顶点的相邻顶点都已访问。 v 如果图中还有未访问顶点，则选择其中之一作为新的遍历起始 顶点，由其出发进行广度优先搜索直到所有顶点都已访问。 27 算法7-4 基于邻接表的无向图广度优先搜索算法 00
14、 Breadth_Gr(RGraph *Gr, int n) 01 02 for (i=0; in; i+) /* 记录顶点是否被访问的一维数组flag初始化 */ 03 flagi = 0; 04 for (i=0; in; i+) /* 对整个图进行广度优先搜索遍历 */ 05 if (flagi = 0) 06 BFS(Gr, i, flag); /* 从顶点vi开始对图进行广度优先遍历 */ 07 28 算法7-4 基于邻接表的无向图广度优先搜索算法2 08 BFS(RGraph *Gr, int i, int flag ) 09 10 Qs_front=0; /* 队首、队尾指针初始化 */ 11 Qs_rear=0; 12 Qs_r
