敦案 第七章图 程序设计—数据结构 图的遍历算法及其应用 目录 第7章图. 1 7.1图的定义和基本术语 7.2图的存储和创建. 2 7.2.1图的存储表示 7.2.2图的创建 _5 7.3图的遍历… 5 7.3.1深度优先搜索 5 7.3.2广度优先搜索 7.4遍历算法的应用.… 6 8 7.4.1应用问题概述 8 7.4.2求一条包含图中所有顶点的简单路径. 8 7.4.3求距v0的各顶点中最短路径长度最长的一个顶点 9 7.5图的连通性问题.… ,。。。2-。-。。。。，。。。。。。。。。,。。。,。。。,。，。，。,。。,。。。，.。。。,。 7.5.1无向图的连通分量和生成树10 7.5.2最小生成树.… 2 7.6有向无环图及其应用 12 文档编号引 完成时间 完成人张昱 修改时间20026-6 第0页
程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 0 页 目 录 第7章 图...............................................................................................................................1 7.1 图的定义和基本术语.................................................................................................1 7.2 图的存储和创建........................................................................................................2 7.2.1 图的存储表示..................................................................................................2 7.2.2 图的创建.........................................................................................................5 7.3 图的遍历..................................................................................................................5 7.3.1 深度优先搜索..................................................................................................5 7.3.2 广度优先搜索..................................................................................................6 7.4 遍历算法的应用........................................................................................................8 7.4.1 应用问题概述..................................................................................................8 7.4.2 求一条包含图中所有顶点的简单路径...............................................................8 7.4.3 求距v0的各顶点中最短路径长度最长的一个顶点.............................................9 7.5 图的连通性问题......................................................................................................10 7.5.1 无向图的连通分量和生成树...........................................................................10 7.5.2 最小生成树...................................................................................................12 7.6 有向无环图及其应用...............................................................................................12
教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 第7章图 7.1图的定义和基本术语 1、图的特征 任意两个数据元素之间都可能相关。结点之间的关系是多对多的。 G=(V,{E}) 2、基本术语 结点：顶点 结点间的关系：无向图：边(yw),v与w互为邻接点，边(y,w)依附于顶点y,w,边(v,w) 和顶点y,w相关联 v的度：和v相关联的边的数目。 有向图：弧<y,w>,v弧尾，w弧头，顶点v邻接到顶点w,顶点w邻接 自顶点v,弧<y,w>和顶点y,相关联。 v的入度：以v为弧头的弧的数目：v的出度：以v为弧尾的弧的数目： v的度：v的入度与出度之和。 路径、回路（环、简单路径、简单回路（简单环） 连通性：若从顶点v到顶点v有路径，则称v和v是连通的 图的规模：顶点数n、边（弧）数、项点的度（有向图：入度/出度） 子图：G=(P,{E}),G=(V,{E),若VcV且EcE,则称G是G的子图。 图的分类： 1)关系的方向性（无向/有向）、关系上是否有附加的数一一权（图/网） 有向图、无向图、有向网、无向网 2)边（弧）数：完全图（边数=n(r1)/2的无向图）、有向完全图（弧数=n(m1)的有向图） 稀疏图(e<nlogn)、稠密图(e>nlogn) 3)连通性：无向图：连通图（任意两顶点都是连通的）、连通分量（极大连通子图）、生成树极 小连通子图)、生成森林 有向图：强/弱连通图、强连通分量、生成树（极小连通子图）、生成森林 3、抽象数据类型定义 ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R: R=VR) VR={<V,w>WweV且P(W,w),<y,w>表示从v到w的弧，谓词P(V,w) 定义了弧<y,w>的意义或信息} 基本操作： CreateGraph(&G.V.VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DestroyGraph(&G) 初始条件：图G存在 操作结果：销毁图G LocateVex(G,u) 初始条件：图G己存在，u和G中顶点有相同特征 文档编号 完成时间 完成人张昱 修改时间20026-6 第1页
程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 1 页 第7章 图 7.1 图的定义和基本术语 1、图的特征 任意两个数据元素之间都可能相关。结点之间的关系是多对多的。 G = (V,{E}) 2、基本术语 结点： 顶点 结点间的关系：无向图：边( v, w )，v 与 w 互为邻接点，边( v, w )依附于顶点 v, w，边( v, w ) 和顶点 v, w 相关联 v 的度：和 v 相关联的边的数目。 有向图：弧< v, w >，v 弧尾，w 弧头，顶点 v 邻接到顶点 w，顶点 w 邻接 自顶点 v，弧< v, w >和顶点 v,w 相关联。 v 的入度：以 v 为弧头的弧的数目；v 的出度：以 v 为弧尾的弧的数目； v 的度：v 的入度与出度之和。 路径、回路(环)、简单路径、简单回路(简单环) 连通性：若从顶点 v 到顶点 v’有路径，则称 v 和 v’是连通的 图的规模：顶点数 n、边(弧)数 e、顶点的度(有向图：入度/出度) 子图：G’= (V’,{E’}), G = (V,{E})，若 V’V 且 E’ E，则称 G’是 G 的子图。 图的分类： 1）关系的方向性（无向/有向）、关系上是否有附加的数——权(图/网) 有向图、无向图、有向网、无向网 2）边(弧)数：完全图(边数= n ( n-1 ) / 2 的无向图)、有向完全图(弧数= n ( n-1)的有向图) 稀疏图(e<nlogn)、稠密图(e>nlogn) 3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极 小连通子图)、生成森林 有向图：强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林 3、抽象数据类型定义 ADT Graph{ 数据对象 V：V 是具有相同特性的数据元素的集合，称为顶点集。 数据关系 R： R = {VR} VR = {< v, w >|v, wV且P(v, w)，<v,w>表示从v到w的弧，谓词P(v,w) 定义了弧<v,w>的意义或信息} 基本操作： CreateGraph(&G, V, VR) 初始条件：V 是图的顶点集，VR 是图中弧的集合 操作结果：按 V 和 VR 的定义构造图 G DestroyGraph(&G) 初始条件：图 G 存在 操作结果：销毁图 G LocateVex( G, u ) 初始条件：图 G 已存在，u 和 G 中顶点有相同特征
敦黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 操作结果：若G中存在顶点u,则返回该项点在图中位置，否则返回其 它信息 GetVex(G.v) 初始条件：图G存在，v是G中某个顶点 操作结果：返回ⅴ的值 PutVex(&G,v,value) 初始条件：图G存在，v是G中某个顶点 操作结果：对v赋值value FirstAdjVex(G,v) 初始条件：图G存在，V是G中某个顶点 操作结果：返回ⅴ的第一个邻接顶点。若顶点在G中没有邻接顶点，则 返回“空” NextAdjVex(G,v,w) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一 个邻接点，则返回“空” InsertVex(&G.v) 初始条件：图G存在，ⅴ和G中顶点有相同特征 操作结果：在图中增添新顶点ⅴ Delete Vex(&G,v) 初始条件：图G存在，ⅴ是G中某个顶点 操作结果：删除G中顶点V及其相关的弧 InsertArc(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：在图G中增添弧<，w>,若G是无向的，则还应增添对称弧 <w,V> DeleteArc(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：删除G中的弧<V,w心，若G是无向的，则还应删除对称弧 DFSTraverse(G,v,visit()) 初始条件：图G存在，v是G中某个顶点，vsit是对顶点的应用函数 操作结果：从顶点v起深度优先遍历图G,并对每个顶点调用函数visit() 一次且至多一次。一旦visit()失败，则操作失败 BFSTraverse(G,v,visit()) 初始条件：图G存在，v是G中某个顶点，vsit是对顶点的应用函数 操作结果：从顶点v起广度优先遍历图G,并对每个顶点调用函数visit() 一次且至多一次。一旦visit()失败，则操作失败 ADT Graph 7.2图的存储和创建 7.2.1图的存储表示 1、图的存储表示分析 ,顶点之间的关系是多对多的(m:n),由于m和n都是不定的，无法给出一个这种多对多 的关系向线性关系的映射公式 ∴图中的关系不能通过顺序映像（即通过顶点之间的存储位置反映顶点之间的逻辑关系）反 文档编号 完成时间 完成人张昱 修改时间20026-6 第2页
程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 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 的(相对于 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 中增添弧<v,w>，若 G 是无向的，则还应增添对称弧 <w,v> DeleteArc(&G, v, w) 初始条件：图 G 存在，v 和 w 是 G 中两个顶点 操作结果：删除 G 中的弧<v,w>，若 G 是无向的，则还应删除对称弧 DFSTraverse(G, v, visit( )) 初始条件：图 G 存在，v 是 G 中某个顶点，visit 是对顶点的应用函数 操作结果：从顶点 v 起深度优先遍历图 G，并对每个顶点调用函数 visit( ) 一次且至多一次。一旦 visit( )失败，则操作失败 BFSTraverse(G, v, visit( )) 初始条件：图 G 存在，v 是 G 中某个顶点，visit 是对顶点的应用函数 操作结果：从顶点 v 起广度优先遍历图 G，并对每个顶点调用函数 visit( ) 一次且至多一次。一旦 visit( )失败，则操作失败 }ADT Graph 7.2 图的存储和创建 7.2.1 图的存储表示 1、图的存储表示分析 ∵顶点之间的关系是多对多的(m : n)，由于 m 和 n 都是不定的，无法给出一个这种多对多 的关系向线性关系的映射公式 ∴图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反
第七章图 程序设计—数据结构 图的遍历算法及其应用 映：必须另外引入存储空间反映顶点之间的邻接关系。 图的存储结构：1)顶点信息：2)边（弧）信息：3)整体信息：顶点数、边（弧）数、图的种 类（有向图、无向图、有向网、无向网） 顶点集的存储：图的应用中，顶点集动态变化的几率十分小 ∴.顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间 (顺序表和链表：若数据元素集是静态的，采用顺序表要好（随机存取）： 若数据元素集是动态的，则采用链表要好（动态分配与释放）) #define MAX VERTEX NUM 20 体最大顶点数*/ 注意：顺序表与顺序映像之间的区别 关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的：且在实际应用中，可能 会改变图中顶点之间的关系。 邻接矩阵表示法：矩阵中的第ⅰ行第j列的元素反映图中第i个顶点到第 j个顶点是否存在弧：若存在，其附加的信息是什么。 邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于 有向图/网来说，该邻接表反映的是顶点的出边表。 typedef enum(DG,DN,AG,AN)GraphKind; 体{有向图，有向网，无向图，无向网}*/ 2、邻接矩阵表示法（数组表示法） 无向图网：对称矩阵 有向图/网：非必是对称矩阵 图：邻接关系用1/0表示 网：邻接关系需要进一步反映权值，用NFINITY表示无穷大，反映顶点之间无邻接关系 #define INT MAX 32767 体最大整数 * #define INFINITY INT MAX 1)邻接矩阵 typedef struct ArcCell int adj; ∥顶点间关系，无权图：0-不相邻，1-相邻 ∥有权图，权值，NFINITY.不相邻 InfoType *info; ∥该弧相关信息的指针 }ArcCell,AdjMatrix[MAX VERTEX NUM][MAX_VERTEX_NUM]; 2) 图的整体结构 typedef struct{ VertexType vexs[MAX VERTEX NUM]; 体有效的顶点下标从0开始*/ AdiMatrix arcs: *关系集 int vexnum,arcnum; /体顶点数、边弧数 GraphKind kind; /体图的种类 */ MGraph; 3、邻接表表示法 无向图/网：边表，表结点的个数为边数的两倍 有向图网：出边表，表结点的个数为弧数 1)邻接表的表结点 typedef struct ArcNode int adivex;/体弧所指向的顶点的位置/ struct ArcNode *nextarc:体指向下一条弧的指针*/ InfoType *info; }ArcNode; 文档编号 完成时间 完成人张昱 修改时间20026-6 第3页
程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 3 页 映；必须另外引入存储空间反映顶点之间的邻接关系。 图的存储结构：1）顶点信息；2）边(弧)信息；3）整体信息：顶点数、边(弧)数、图的种 类(有向图、无向图、有向网、无向网) 顶点集的存储：∵图的应用中，顶点集动态变化的几率十分小 ∴顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间 （顺序表和链表：若数据元素集是静态的，采用顺序表要好(随机存取)； 若数据元素集是动态的，则采用链表要好(动态分配与释放)） #define MAX_VERTEX_NUM 20 /* 最大顶点数 */ 注意：顺序表与顺序映像之间的区别 关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的；且在实际应用中，可能 会改变图中顶点之间的关系。 邻接矩阵表示法：矩阵中的第 i 行第 j 列的元素反映图中第 i 个顶点到第 j 个顶点是否存在弧；若存在，其附加的信息是什么。 邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于 有向图/网来说，该邻接表反映的是顶点的出边表。 typedef enum{DG, DN, AG, AN} GraphKind; /*{有向图，有向网，无向图，无向网}*/ 2、邻接矩阵表示法（数组表示法） 无向图/网：对称矩阵 有向图/网：非必是对称矩阵 图：邻接关系用 1/0 表示 网：邻接关系需要进一步反映权值，用 INFINITY 表示无穷大，反映顶点之间无邻接关系 #define INT_MAX 32767 /* 最大整数 */ #define INFINITY INT_MAX 1) 邻接矩阵 typedef struct ArcCell{ int adj; // 顶点间关系，无权图：0-不相邻，1-相邻 // 有权图，权值，INFINITY-不相邻 InfoType *info; // 该弧相关信息的指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 2) 图的整体结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; /* 有效的顶点下标从 0 开始 */ AdjMatrix arcs; /* 关系集 */ int vexnum, arcnum; /* 顶点数、边/弧数 */ GraphKind kind; /* 图的种类 */ }MGraph; 3、邻接表表示法 无向图/网：边表，表结点的个数为边数的两倍 有向图/网：出边表，表结点的个数为弧数 1) 邻接表的表结点 typedef struct ArcNode{ int adjvex; /* 弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; }ArcNode;
教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 2) 邻接表的头结点 typedef struct VNode! Vertex Type data; 体顶点信息制 ArcNode *firstarc; 体邻接表指针*/ }VNode,AdjList[MAX VERTEX NUM]; 3)图的整体结构 typedef struct{ AdjList vertices; int vexnum,arcnum; GraphKind kind; }ALGraph; 4、邻接矩阵与邻接表的对比 假设图为G,顶点数为n,边/弧数为e。 A邻接矩阵 B邻接表 存储空间 0(n+n2) O(n+e) T1(n)=0(e+n2)或T2(n=0(e*n+n2) T1(n)=0(n+e)或T2(n)=0(e*n) 图的创建算 T1(n)是指在输入边/弧时，输入的顶点信息为顶点的编号：而T2(n)则指 法 在输入边弧时，输入的为顶点本身的信息，此时需要查找顶点在图中的 位置 GarcM小a(第i行之利成 无向图中求 j-0 第ⅰ顶点的度 cana时第i列之利 G.vertices[i.firstarc所指向的邻接 表包含的结点个数 j=0 无向网中求 第i行/列中ad值不为NFINITY的 第ⅰ顶点的度 元素个数 有向图中求 入度： acU0a(第i列 第i顶点的入 0 入度：扫描各顶点的邻接表，统计 出度 出度： GaresiUJad(第i行 表结点的adjvex为i的表结点个数 /0 T(n)=O(n+e) 有向网中求 入度：第i列中ad值不为NFINITY 出度：G.vertices[i).firstarc所指向 第i顶点的入/ 的元素个数 的邻接表包含的结点个数 出度 出度：第i行中adi值不为NFINITY 的元素个数 无向图： GonaEad 无向网：G.arcs中adj值不为 无向图/网：图中表结点数目的一 统计边/弧数 NFINITY的元素个数的一半 义 有向图： cacf1a时 有向图/网：图中表结点的数目 i=0j=0 有向网：G.arcs中adj值不为 INFINITY的元素个数 文档编号 完成时间 完成人张昱 修改时间20026-6 第4页
程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 4 页 2) 邻接表的头结点 typedef struct VNode{ VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 邻接表指针 */ }VNode, AdjList[MAX_VERTEX_NUM]; 3) 图的整体结构 typedef struct { AdjList vertices; int vexnum, arcnum; GraphKind kind; }ALGraph; 4、邻接矩阵与邻接表的对比 假设图为 G，顶点数为 n，边/弧数为 e。 A 邻接矩阵 B 邻接表 存储空间 O(n+n2 ) 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)则指 在输入边/弧时，输入的为顶点本身的信息，此时需要查找顶点在图中的 位置 无向图中求 第 i 顶点的度 G arcs i j adj n j . [ ][ ]. 1 0 − = (第 i 行之和)或 G arcs j i adj n j . [ ][ ]. 1 0 − = (第 i 列之和) G.vertices[i].firstarc 所指向的邻接 表包含的结点个数 无向网中求 第 i 顶点的度 第 i 行/列中 adj 值不为 INFINITY 的 元素个数 有向图中求 第i顶点的入/ 出度 入度： − = 1 0 . [ ][ ]. n j G arcs j i adj (第 i 列) 出度： − = 1 0 . [ ][ ]. n j G arcs i j adj (第 i 行) 入度：扫描各顶点的邻接表，统计 表结点的adjvex为i的表结点个数 T(n)=O(n+e) 出度：G.vertices[i].firstarc 所指向 的邻接表包含的结点个数 有 向网中求 第i顶点的入/ 出度 入度：第 i 列中 adj 值不为 INFINITY 的元素个数 出度：第 i 行中 adj 值不为 INFINITY 的元素个数 统计边/弧数 无向图： − = − = 1 0 1 0 . [ ][ ]. 2 1 n i n j G arcs i j adj ) 无向网： G.arcs 中 adj 值不为 INFINITY 的元素个数的一半 有向图： − = − = 1 0 1 0 . [ ][ ]. n i n j G arcs i j adj 有向网： G.arcs 中 adj 值不为 INFINITY 的元素个数 无向图/网：图中表结点数目的一 半 有向图/网：图中表结点的数目