第第8章章 图图 本章要点本章要点 图的基本概念及存储结构图的基本概念及存储结构 图的遍历图的遍历 图的连通及最小生成树图的连通及最小生成树 最短路径最短路径 有向无环图及其应用有向无环图及其应用 本章难点本章难点 图的存储结构及遍历图的存储结构及遍历 最小生成树、拓扑排序、关键路径、最短路径的算法实现最小生成树、拓扑排序、关键路径、最短路径的算法实现2021/6/71图是一种比线性表和树更复杂的数据结构。在线图是一种比线性表和树更复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间存在着明显的层次关系，并且每层的元数据元素之间存在着明显的层次关系，并且每层的元素可能和下一层的多个元素（即其孩子结点）相邻，素可能和下一层的多个元素（即其孩子结点）相邻，但只能和上一层的一个元素（即其双亲结点）相关。但只能和上一层的一个元素（即其双亲结点）相关。而在图形结构中，结点之间的关系可以是任意的，图而在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都可能相邻。中任意两个元素之间都可能相邻。 8.1 图的基本概念图的基本概念2021/6/72图图(graph)是由有限个顶点是由有限个顶点(vertex)集合及顶点间的关系集合及顶点间的关系(边边)集合组合而成的一种非线性数据结构。描述为：集合组合而成的一种非线性数据结构。描述为：G=(V,E)V=vi|vidataobjectE=(vi,vj)|vi,vj V且且P(vi,vj) )， (vi,vj)表示从表示从vi到到vj的弧，谓词的弧，谓词P(vi,vj)定义了弧定义了弧(vi,vj)的意义或信息的意义或信息其中，其中，G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是图的边是图的边的集合。的集合。 8.1.1 基本概念基本概念2021/6/73例：在例：在G1中，中， (vi,vj)表示顶点表示顶点vi和顶点和顶点vj之间有一条无向直接连线边。之间有一条无向直接连线边。G1 =(V,E)V=v1, v2, v3, v4, v5E=(v1,v2),(v1,v3) ,(v1,v4) ,(v2,v3) ,(v2,v5) ,(v3,v4)v1v2v4v3v5无向图无向图G1 8.1.1 基本概念基本概念2021/6/74例：在例：在G2中，中， 表示顶点表示顶点vi和顶和顶点点vj之间有一条有向直接连线弧，之间有一条有向直接连线弧， vi称为弧尾，称为弧尾， vj称为弧头。称为弧头。G2 =(V,E)V=v1, v2, v3, v4E=, , , ,v1v2v3v4有向图有向图G2 8.1.1 基本概念基本概念2021/6/75 8.1.2 基本术语基本术语 无向图、有向图、完全图、稀疏图和稠密图无向图、有向图、完全图、稀疏图和稠密图在一个图在一个图G中，如果任意两个顶点对（中，如果任意两个顶点对（vi,vj)E是无序的，是无序的， (vi,vj) (vj,vi)，即顶点之间的连线没有方向，则称该图为，即顶点之间的连线没有方向，则称该图为无向无向图图。在一个图在一个图G中，如果任意两个顶点对中，如果任意两个顶点对E是有序的，是有序的， ，即顶点之间的连线有方向，则称该图为，即顶点之间的连线有方向，则称该图为有向图有向图。若含有若含有n个顶点的无向图中，共有个顶点的无向图中，共有n(n-1)/2条边，即任意两条边，即任意两顶点都有一条直接边相连接，则称该图为顶点都有一条直接边相连接，则称该图为无向完全图无向完全图。若含有若含有n个顶点的有向图中，共有个顶点的有向图中，共有n(n-1)条弧，即任意两个条弧，即任意两个顶点之间都有方向互为相反的两条弧相连，则称之为顶点之间都有方向互为相反的两条弧相连，则称之为有向完全有向完全图图。含有很少条边或弧的图称为含有很少条边或弧的图称为稀疏图稀疏图。含有很多条边或弧，接近完全图的图称为含有很多条边或弧，接近完全图的图称为稠密图稠密图2021/6/76 8.1.2 基本术语基本术语 子图子图设设G1和和G是两个图，若是两个图，若V(G1 ) V(G)，E(G1 ) E(G)，则称，则称G1为为G的的子图子图，若，若V(G1 ) V(G)，E(G1 ) E(G)，则把，则把G1叫做叫做G的的真子图真子图。v1v1v4v3v1v2v4v3v5v1v2(a)(b)(c)(d)v1v2v4v3v5无向图无向图G1无向图无向图G1的的4个子图个子图2021/6/77 8.1.2 基本术语基本术语v1v2v4v1v3v4有向图有向图G2的的2个子图个子图v1v2v3v4有向图有向图G22021/6/78 邻接点邻接点对于无向图对于无向图G=(V,E)，如果边，如果边(vi,vj)E，则称顶点，则称顶点vi,vj互为互为邻接点，即邻接点，即vi,vj相邻接，称边相邻接，称边(vi,vj)和顶点和顶点vi,vj相关联。相关联。对于有向图对于有向图G=(V,A)，如果弧，如果弧A，则称顶，则称顶点点vi邻接到顶点邻接到顶点vj ，顶点，顶点vj邻接自顶点邻接自顶点vi，称弧，称弧和顶点相关联。和顶点相关联。 8.1.2 基本术语基本术语2021/6/79 8.1.2 基本术语基本术语 度、入度和出度度、入度和出度对无向图而言，顶点的度是指和对无向图而言，顶点的度是指和v相关联的边的数目，记作相关联的边的数目，记作TD(v)。对有向图而言，顶点的度为其出度和入度之和，其中出度定对有向图而言，顶点的度为其出度和入度之和，其中出度定义为以该顶点为弧尾的弧的个数，记作义为以该顶点为弧尾的弧的个数，记作OD(v)，入度定义为以该，入度定义为以该顶点为弧头的弧的个数，记作顶点为弧头的弧的个数，记作ID(v) ，即在有向图中存在，即在有向图中存在TD(v)ID(v)+OD(v) 。对于具有对于具有n个顶点、个顶点、e条边的图，顶点条边的图，顶点vi的度的度TD(vi)与顶点的与顶点的个数以及边的数目满足关系：个数以及边的数目满足关系：2021/6/710 权与网权与网在实际应用中，图的边或弧通常与具有一定意义的数有关，在实际应用中，图的边或弧通常与具有一定意义的数有关，与边或弧相关的数称为该边与边或弧相关的数称为该边(弧弧)的权，这些权可以表示从一个顶的权，这些权可以表示从一个顶点到另一个顶点的距离、时间耗费或经济耗费等信息。点到另一个顶点的距离、时间耗费或经济耗费等信息。带权的图叫做赋权图或网。带权的图叫做赋权图或网。 8.1.2 基本术语基本术语6v2v1v4v3v516491057无向网无向网2021/6/711 路径和回路路径和回路若有向图若有向图 G 中中 k+1 个顶点之间都有弧存在（即个顶点之间都有弧存在（即,，是图是图 G 中的弧），则这个顶点的序中的弧），则这个顶点的序列列v0,v1,vk 为从顶点为从顶点v0到顶点到顶点vk的一条的一条有向路径有向路径。对无向图，路径没有方向，相邻顶点之间存在边的对无向图，路径没有方向，相邻顶点之间存在边的 k+1 个个顶点序列构成一条长度为顶点序列构成一条长度为 k 的的无向路径无向路径。路径长度路径长度是指路径中弧或边的数目。是指路径中弧或边的数目。在一个路径中，若其第一个顶点和最后一个顶点是相同的，在一个路径中，若其第一个顶点和最后一个顶点是相同的，则称这种路径为则称这种路径为回路或环回路或环。若表示路径的顶点序列中的顶点各不相同，则称这样的路若表示路径的顶点序列中的顶点各不相同，则称这样的路径为径为简单路径简单路径。除了第一个和最后一个顶点外，其余各顶点均不重复出现除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为的回路为简单回路简单回路。 8.1.2 基本术语基本术语2021/6/712AECDB有向图中顶点序列有向图中顶点序列 A,E,C,D 是一条路径长度为是一条路径长度为3的简单路径，顶点序列的简单路径，顶点序列 A,B,C,D,A 是一条长度为是一条长度为4的的简单回路。简单回路。无向图中顶点序列无向图中顶点序列 A,B,F,C,D 是一条长度为是一条长度为4的的无向路径。无向路径。无向图无向图G4有向图有向图G3BDCEAF 8.1.2 基本术语基本术语2021/6/713 连通图与连通分量连通图与连通分量在无向图在无向图G中，如果从一个顶点中，如果从一个顶点vi到另一个顶点到另一个顶点vj(ij)有有路径，则称顶点路径，则称顶点vi到顶点到顶点vj是连通的，若图中任意两个顶点之是连通的，若图中任意两个顶点之间都是相通的，则称该图是连通图，否则称为非连通图。无间都是相通的，则称该图是连通图，否则称为非连通图。无向图中的极大连通子图称为它的连通分量。如图所示。向图中的极大连通子图称为它的连通分量。如图所示。连通图连通图G5非连通图非连通图G6v1v2v4v3v5v1v2v3v4v5v7v6 8.1.2 基本术语基本术语2021/6/714强连通图和强连通分量强连通图和强连通分量在有向图在有向图G中，如果任意两个顶点间都是相互有路径可达，中，如果任意两个顶点间都是相互有路径可达，则称该有向图为强连通图。如果图中任意两个顶点至少有一个则称该有向图为强连通图。如果图中任意两个顶点至少有一个顶点由另一顶点可达，则称此有向图是单向连通的。有向图的顶点由另一顶点可达，则称此有向图是单向连通的。有向图的最大强连通子图称作该图的强连通分量。如图为有向图含有两最大强连通子图称作该图的强连通分量。如图为有向图含有两个强连通分量。个强连通分量。v1v2v3v4有向图有向图G2v1v2v3v4有向图有向图G2的的2个强连通分量个强连通分量 8.1.2 基本术语基本术语2021/6/715 8.1.3 基本操作基本操作设设V是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合(顶点集顶点集)，E是图中是图中边边(或弧或弧)的集合，的集合，v和和w是图中的两个顶点，则有关图的基本操是图中的两个顶点，则有关图的基本操作为作为 结构初始化结构初始化CreateGraph(&G, V, E);初始条件：初始条件：V 是图的顶点集，是图的顶点集，E是图中边的集合。是图中边的集合。操作结果：按操作结果：按 V 和和 E 的定义构造图的定义构造图 G。 GetVex(G, v);初始条件：图初始条件：图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：返回操作结果：返回 v 的值。的值。顶点在图中的顶点在图中的“位置位置”指的是在图的存储结构中顶点之间自指的是在图的存储结构中顶点之间自然形成的相对位置。然形成的相对位置。2021/6/716 PutVex(&G, v, info);初始条件：图初始条件：图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：对操作结果：对 v 赋值为赋值为info。 FirstAdjvex(G, v);初始条件：图初始条件：图 G 存在，存在，v 是是 G 中某个顶点。中某个顶点。操作结果：返回操作结果：返回 v 的第一个邻接点。若该顶点在的第一个邻接点。若该顶点在 G 中没中没有邻接点，则返回有邻接点，则返回“空空”。 NextAdjvex(G, v, w);初始条件：图初始条件：图 G 存在，存在，v 是是 G 中某个顶点，中某个顶点，w 是是 v 的邻的邻接顶点。接顶点。操作结果：返回操作结果：返回 v 的（相对于的（相对于 w 的）下一个邻接点。若的）下一个邻接点。若 w 是是 v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。 8.1.3 基本操作基本操作2021/6/717 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 是有向的，则是有向的，则还删除对称弧还删除对称弧。 8.1.3 基本操作基本操作2021/6/718图没有顺序存储结构由于图中顶点间关系无法用统一的图没有顺序存储结构由于图中顶点间关系无法用统一的规则描述，也无法以存储位置之间一种确定的相对关系来描述，规则描述，也无法以存储位置之间一种确定的相对关系来描述，只能用附加的信息描述顶点间的关系。只能用附加的信息描述顶点间的关系。 8.2.1邻接矩阵表示法邻接矩阵表示法图的图的“邻接矩阵邻接矩阵”是以矩阵这种数学形式描述图中顶点之间是以矩阵这种数学形式描述图中顶点之间的关系。邻接矩阵属于图的顺序存储结构。所谓邻接矩阵表示的关系。邻接矩阵属于图的顺序存储结构。所谓邻接矩阵表示法，就是采用一个一维数组存储图的顶点信息，用矩阵表示图法，就是采用一个一维数组存储图的顶点信息，用矩阵表示图中各顶点之间的邻接关系。中各顶点之间的邻接关系。假设图假设图A=V,E是一个有是一个有n个顶点的图，图的邻接矩阵是一个顶点的图，图的邻接矩阵是一个二维数组个二维数组Ann ：用来存放顶点的信息和边：用来存放顶点的信息和边(弧弧)的信息。邻的信息。邻接矩阵中元素定义为：接矩阵中元素定义为： 8.2图的存储结构图的存储结构2021/6/7191若若(vi,vj)或或是是E(G)的边或弧的边或弧0若若(vi,vj)或或不是不是E(G)的边或弧的边或弧若若G是网图，则邻接矩阵可定义为：是网图，则邻接矩阵可定义为： Aij=Wij若若(vi,vj)或或是是E(G)的边或弧的边或弧若若(vi,vj)或或不是不是E(G)的边或弧的边或弧 其中其中Wij表示边表示边(vi,vj)或或上的权值，上的权值，可设定为计算可设定为计算机所能表示的最大值，表示两个顶点之间没有边或弧。机所能表示的最大值，表示两个顶点之间没有边或弧。Aij= 8.2.1邻接矩阵表示法邻接矩阵表示法2021/6/7200 1 1 1 00 1 1 01 0 1 0 10 0 0 0 1 1 0 1 0 0 0 0 11 0 1 0 0 1 1 0 0 0 1 0 0 0无向图无向图G1及邻接矩阵及邻接矩阵有向图有向图G2及邻接矩阵及邻接矩阵v1v2v4v3v5v1v2v3v4 8.2.1邻接矩阵表示法邻接矩阵表示法2021/6/721从图从图G1的邻接矩阵中可以看出，无向图的邻接的邻接矩阵中可以看出，无向图的邻接矩阵是对称矩阵，邻接矩阵的第矩阵是对称矩阵，邻接矩阵的第i行行(或第或第j列列)非零元非零元的个数就是第的个数就是第i个顶点的度。个顶点的度。对于有向图，邻接矩阵的第对于有向图，邻接矩阵的第i行行(或第或第j列列)非零元非零元的个数是第的个数是第i个顶点的出度个顶点的出度OD(vi)（或入度（或入度ID(vi)）。）。 8.2.1邻接矩阵表示法邻接矩阵表示法2021/6/7226v2v1v4v3v516491057无向网及邻接矩阵无向网及邻接矩阵 8.2.1邻接矩阵表示法邻接矩阵表示法1649165657491067102021/6/723图的邻接矩阵表示法类型定义图的邻接矩阵表示法类型定义#define INFINITY INT_MAX/*表示无穷大值表示无穷大值*/#define MaxSize 20typedef enum DG,DN,UDG,UDN GraphKind; /*图的类型图的类型*/typedef struct /* 图的定义图的定义*/ VextexType vexsMaxSize; /* 顶点信息顶点信息*/ ArcType arcsMaxSize MaxSize;/*各边各边(弧弧)*/ int vexnum,arcnum; /* 图的当前顶点数和弧图的当前顶点数和弧(边边)数数*/ GraphKind kind;/*图的类型图的类型*/ AdjMatrix;其中其中DG,DN,UDG和和UDN分别表示有向图，有向网，无向分别表示有向图，有向网，无向图和无向网。图和无向网。 8.2.1邻接矩阵表示法邻接矩阵表示法2021/6/724 8.2.1邻接矩阵表示法邻接矩阵表示法v6v1v5v4v2v325415569785748956521有向网及其邻接矩阵有向网及其邻接矩阵2021/6/725 8.2.1邻接矩阵表示法邻接矩阵表示法邻接矩阵表示法的特点邻接矩阵表示法的特点 存储空间对于无向图，因邻接矩阵是对称矩阵，故可以采存储空间对于无向图，因邻接矩阵是对称矩阵，故可以采用特殊矩阵的压缩存储法。一个具有用特殊矩阵的压缩存储法。一个具有n个顶点的无向图个顶点的无向图G，其，其邻接矩阵需要邻接矩阵需要n(n+1)/2个存储单元；对于有向图，则邻接矩阵个存储单元；对于有向图，则邻接矩阵需要需要n2个存储单元。个存储单元。 运算采用邻接矩阵表示法，便于判定图中任意两个顶点之运算采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，只需要根据间是否有边相连，只需要根据Aij的值进行判断即可。的值进行判断即可。另外还便于求各个顶点的度。另外还便于求各个顶点的度。 对于不带权值的无向图，其邻接矩阵第对于不带权值的无向图，其邻接矩阵第i行行(列列)元素之和就是元素之和就是图中第图中第i个顶点的度个顶点的度TD(Vi)=2021/6/726 对于不带权值的有向图，其邻接矩阵第对于不带权值的有向图，其邻接矩阵第i行元素之和就是图中行元素之和就是图中第第i个顶点的出度个顶点的出度OD(Vi)= 对于不带权值的有向图，其邻接矩阵第对于不带权值的有向图，其邻接矩阵第i列元素之和就是图中列元素之和就是图中第第i个顶点的入度个顶点的入度ID(Vi)= 对于带权图，只需求出对于的非对于带权图，只需求出对于的非的元素的个数即可。的元素的个数即可。 8.2.1邻接矩阵表示法邻接矩阵表示法2021/6/727 8.2.1邻接矩阵表示法邻接矩阵表示法算法算法8.1采用邻接矩阵表示法构造图采用邻接矩阵表示法构造图#define G (*G1)status CreateGraph1(AdjMatrix *G1) scanf(“%d”,&G.kind); switch(G.kind) case DG:return CreateDG1(G1);/*构造有向图构造有向图*/ case DN:return CreateDN1(G1);/*构造有向网构造有向网*/ case UDG:return CreateUDG1(G1); /*构造无向图构造无向图*/ case UDN:return CreaseUDN1(G1); /*构造无向网构造无向网*/ default:rerurn ERROR; 2021/6/728 8.2.1邻接矩阵表示法邻接矩阵表示法算法算法8.2构造邻接矩阵表示的无向网构造邻接矩阵表示的无向网#define G (*G1)status CreateUDN1(AdjMatrix *G1) scanf(“%d”,&G.vexnum);/*输入顶点数输入顶点数*/ n=G.vexnum; scanf(“%d”,&G.arcnum);/*输入边数输入边数*/ e=G.arcnum; for (i=1;i=n;i+) scanf(“%d”,&G.vexsi-1);/*输入各顶点的值输入各顶点的值*/ for (i=1;i=n;i+)/*初始化邻接矩阵中的元素为无穷大初始化邻接矩阵中的元素为无穷大*/ for (j=1;j=n;j+) G.arcsi-1j-1=INFINITY; for (k=1;k=e;k+)/*输入各边的邻接点和权值并修改邻接矩阵输入各边的邻接点和权值并修改邻接矩阵*/ scanf(“%d%d%d”,&i,&j,&w); G.arcsij=w; G.arcsji=w; return(1); 2021/6/729 8.2.2邻接表表示法邻接表表示法邻接表是图的顺序存储和链式存储相结合的存储方法，类邻接表是图的顺序存储和链式存储相结合的存储方法，类似于树的孩子链表表示法。在邻接表中，对图中每个顶点建立似于树的孩子链表表示法。在邻接表中，对图中每个顶点建立一个单链表，第一个单链表，第i个单链表中的结点表示依附于顶点个单链表中的结点表示依附于顶点vi的边（有的边（有向图是以向图是以vi为尾的弧），每个结点由三个域组成：为尾的弧），每个结点由三个域组成：邻接点域（邻接点域（adjvex）：指示与顶点）：指示与顶点vi邻接的点在图中的位置。邻接的点在图中的位置。链域（链域（nextarc）：指示下一条边或弧的结点。）：指示下一条边或弧的结点。数据域（数据域（info）：存储和边）：存储和边(或弧或弧)相关的信息相关的信息(如权值如权值)。该结点称为表结点。该结点称为表结点。每个链表上附设一个表头结点，包含每个链表上附设一个表头结点，包含数据域（数据域（data）存放顶点的值。）存放顶点的值。链域（链域（firstarc）指向链表中的第一个结点。）指向链表中的第一个结点。表头结点以顺序结构存储，以便随机访问任一顶点的链表。表头结点以顺序结构存储，以便随机访问任一顶点的链表。2021/6/730datafirstarc边表结点边表结点头结点头结点43210v5v4v3v2v1123024013021 8.2.2邻接表表示法邻接表表示法adjvexinfonextarcv1v2v4v3v5无向图无向图G1及其邻接表及其邻接表2021/6/731在无向图的邻接表中，顶点在无向图的邻接表中，顶点vi的度等于第的度等于第i个链表中的结点个链表中的结点数。在有向图的邻接表中，顶点数。在有向图的邻接表中，顶点vi的出度等于第的出度等于第i个链表中的结个链表中的结点数，求入度必须遍历整个邻接表，为便于求点数，求入度必须遍历整个邻接表，为便于求vi的入度，需建的入度，需建立有向图的逆邻接表（以顶点立有向图的逆邻接表（以顶点vi为头的弧所建立的邻接表）。为头的弧所建立的邻接表）。3210v4v3v2v112301有向图有向图G2及其邻接表及其邻接表 8.2.2邻接表表示法邻接表表示法v1v2v3v42021/6/732v1v2v3v4 8.2.2邻接表表示法邻接表表示法3210v4v3v2v133002有向图有向图G2及其逆邻接表及其逆邻接表2021/6/733邻接表存储结构类型定义邻接表存储结构类型定义边边(弧弧)结点类型定义结点类型定义#define MaxSize 100typedef struct int adjvex; struct Arcnode *nextarc; otherInfo info; ArcNode;头结点类型定义头结点类型定义typedef struct VertexType data; ArcNode *firstarc; VertexNode;图的邻接表存储结构定义图的邻接表存储结构定义typedef struct VertexNode vertexMaxSize; int vexnum,arcnum; int kind; AdjList;kind：0(有向图有向图)、1(有向网有向网)、2(无向图无向图)、3(无向网无向网)。 8.2.2邻接表表示法邻接表表示法2021/6/73443210EDCBAAECDB1223012 8.2.2邻接表表示法邻接表表示法有向图有向图G3及其邻接表及其邻接表2021/6/735AECDB43210EDCBA3031420有向图有向图G3及其逆邻接表及其逆邻接表 8.2.2邻接表表示法邻接表表示法2021/6/736 8.2.2邻接表表示法邻接表表示法6v2v1v4v3v51649105743210v5v4v3v2v1116349 01625461547049410 1627310 无向网无向网G4及其邻接表及其邻接表2021/6/737算法算法8.3采用邻接表表示法构造图采用邻接表表示法构造图#define G (*G1)status CreateGraph2(AdjList *G1) scanf(“%d”,&G.kind); switch(G.kind) case 0:return CreateDG2(G1);/*构造有向图构造有向图*/ case 1:return CreateDN2(G1);/*构造有向网构造有向网*/ case 2:return CreateUDG2(G1); /*构造无向图构造无向图*/ case 3:return CreaseUDN2(G1); /*构造无向网构造无向网*/ default:rerurn ERROR; 8.2.2邻接表表示法邻接表表示法2021/6/738 8.2.2邻接表表示法邻接表表示法算法算法8.4构造邻接表表示的无向网构造邻接表表示的无向网#define G (*G1)status CreateUDN2(AdjList *G1) scanf(“%d”,&G.vexnum);/*输入顶点数输入顶点数*/ n=G.vexnum; scanf(“%d”,&G.arcnum);/*输入边数输入边数*/ e=G.arcnum; for (i=1;i=n;i+)/*表头结点赋值表头结点赋值*/ scanf(“%d”,&G.vertexi-1.data); G.vextexi-1.firstarc=NULL; 2021/6/739 for (k=1;kadjvex=j; p-info=w; p-nextarc=G.vertexi.firstarc; G.vertexi.firstarc=p; /*头插法在第头插法在第j个单链表中插入边结点个单链表中插入边结点*/ q=malloc(sizeof(ArcNode); q-adjvex=i; q-info=w; q-nextarc=G.vertexj.firstarc; G.vertexj.firstarc=q; return(1); 8.2.2邻接表表示法邻接表表示法2021/6/740 8.2.2邻接表表示法邻接表表示法邻接表存储结构有如下特点邻接表存储结构有如下特点 存储空间对于有存储空间对于有n个顶点，个顶点，e条边的无向图，需要条边的无向图，需要n个表头个表头结点和结点和2e个表结点（有向图有个表结点（有向图有e个表结点）。个表结点）。 无向图的度无向图的邻接表中，顶点无向图的度无向图的邻接表中，顶点vi的度恰好就是第的度恰好就是第i个单链表上结点的个数。个单链表上结点的个数。 有向图的度在有向图的邻接表中，第有向图的度在有向图的邻接表中，第i个单链表上结点的个单链表上结点的个数是顶点个数是顶点vi的出度；在有向图的逆邻接表中，第的出度；在有向图的逆邻接表中，第i个单链表上个单链表上结点的个数是顶点结点的个数是顶点vi的入度。的入度。2021/6/741对于一个含对于一个含 n 个顶点和个顶点和 e 条边的无向图，条边的无向图，e 的最大值为的最大值为 n(n-1)/2。称含有。称含有 n 个顶点和个顶点和 n(n-1)/2 条边的图为完全图。条边的图为完全图。若无向图中有若无向图中有n个结点、个结点、e条边，则其邻接表需条边，则其邻接表需2e个表结点，个表结点，在边稀疏（在边稀疏（en(n-1)/2）情况下，用邻接表表示图比用邻接矩）情况下，用邻接表表示图比用邻接矩阵节省存储空间。阵节省存储空间。如果图中边的数目如果图中边的数目 enlog2n，则称为稀疏图，反之称为稠，则称为稀疏图，反之称为稠密图。密图。容易理解，由于邻接矩阵的存储空间是容易理解，由于邻接矩阵的存储空间是 n2 级的，而邻接级的，而邻接表的空间复杂度是表的空间复杂度是 O (n+e)。因此通常，稠密图的存储结构用。因此通常，稠密图的存储结构用“邻接矩阵邻接矩阵”，稀疏图的存储结构用，稀疏图的存储结构用“邻接表邻接表”表示。表示。 8.2.2邻接表表示法邻接表表示法2021/6/742与二叉树和树的遍历相同，图的与二叉树和树的遍历相同，图的“遍历遍历”是对图是对图中的每个顶点都进行一次访问且仅进行一次访问。中的每个顶点都进行一次访问且仅进行一次访问。但由于图结构较树和二叉树更为复杂，图中任意两但由于图结构较树和二叉树更为复杂，图中任意两个顶点之间都可能存在一条弧或边，反之也可能存个顶点之间都可能存在一条弧或边，反之也可能存在某个顶点和其它顶点之间都不存在弧或边。因此在某个顶点和其它顶点之间都不存在弧或边。因此对图的遍历而言，除了要确定一条搜索路径之外，对图的遍历而言，除了要确定一条搜索路径之外，还要解决两个问题：还要解决两个问题：(1)如何确保每个顶点都被访问到。如何确保每个顶点都被访问到。(2)如何确保每个顶点只被访问一次。如何确保每个顶点只被访问一次。 8.3图的遍历图的遍历2021/6/743深度优先搜索（深度优先搜索（depth-first search）是一个递归过程。）是一个递归过程。 从图中任意一个顶点从图中任意一个顶点v出发，首先访问此顶点。出发，首先访问此顶点。 任选一个任选一个v的未曾访问过的邻接点的未曾访问过的邻接点w进行访问，并由此出发进行访问，并由此出发继续进行深度优先搜索，直到图中所有和继续进行深度优先搜索，直到图中所有和v相通的顶点都被访相通的顶点都被访问到。问到。 若此时图中还有未被访问的顶点，则另选一个新的起始点，若此时图中还有未被访问的顶点，则另选一个新的起始点，重复上面的做法，直至图中所有的顶点都被访问。重复上面的做法，直至图中所有的顶点都被访问。由于二叉树和树中存在一个无前驱的由于二叉树和树中存在一个无前驱的“根结点根结点”，其它所有，其它所有结点都存在一条从根到该结点的路径，因此二叉树和树的遍历结点都存在一条从根到该结点的路径，因此二叉树和树的遍历都只能也必须从根出发进行，而对连通图而言，图中任意两个都只能也必须从根出发进行，而对连通图而言，图中任意两个顶点之间都有路径相通，因此可以从图中任意一个顶点出发进顶点之间都有路径相通，因此可以从图中任意一个顶点出发进行遍历。行遍历。 8.3.1 图的深度优先搜索遍历图的深度优先搜索遍历2021/6/744图的深度优先搜索遍历的图的深度优先搜索遍历的过程类似于树的先根遍历。可过程类似于树的先根遍历。可将将 v1 看作是树的根结点，看作是树的根结点， v2 和和 v3 可看成是它的二个可看成是它的二个“子树根结子树根结点点”，如果，如果 G1 和和 G2 分别为二个分别为二个连通子图且相互之间不连通，连通子图且相互之间不连通，则在访问则在访问 v1之后可依次从之后可依次从v2和和v3出发对图进行深度优先搜索遍出发对图进行深度优先搜索遍历。历。深度优先顶点序列：深度优先顶点序列：v1 v2 v4 v8 v5 v3 v6 v7v1v2v4v5v6v7v8v3G1G2结论：图的结论：图的深度优先搜索的顶点序列是不惟一的。深度优先搜索的顶点序列是不惟一的。无向图无向图G5 8.3.1 图的深度优先搜索遍历图的深度优先搜索遍历2021/6/745abgcdefhk深度优先顶点序列：深度优先顶点序列：a c h d k f e b g虽然在此以无向图为例，虽然在此以无向图为例，但方法同样适用于有向图的深但方法同样适用于有向图的深度优先搜索遍历。度优先搜索遍历。注意注意图的深度优先搜索的顶点图的深度优先搜索的顶点序列是不惟一的。序列是不惟一的。012345678无向图无向图G6 8.3.1 图的深度优先搜索遍历图的深度优先搜索遍历2021/6/746 8.3.1 图的深度优先搜索遍历图的深度优先搜索遍历算法算法8.5深度优先遍历以邻接矩阵存储的图的连通分量。深度优先遍历以邻接矩阵存储的图的连通分量。void dfs1(AdjMatrix G,int v) visit(v);/*访问出发点访问出发点*/ visitedv=1;/*置访问标志为置访问标志为1*/ for (w=0;wG.vexnum;w+) if (!visitedw & G.arcsvw=1)/*未访问过的邻接点未访问过的邻接点*/dfs1(G,w); 用邻接矩阵和邻接表作为存储结构的图的深度优先搜索算法用邻接矩阵和邻接表作为存储结构的图的深度优先搜索算法2021/6/747 8.3.1 图的深度优先搜索遍历图的深度优先搜索遍历算法算法8.6深度优先遍历以邻接矩阵为存储结构的图。深度优先遍历以邻接矩阵为存储结构的图。void TraverseGraph1(AdjMatrix G) for (v=0;vG.vexnum;v+) visitedv=0;/*访问标志数组初始化访问标志数组初始化*/ for (v=0;vadjvex;/*邻接点的序号邻接点的序号*/ if (!visitedw)/*未被访问过的邻接点未被访问过的邻接点*/ dfs2(G,w);/*深度遍历连通子图深度遍历连通子图*/ p=p-nextarc; 2021/6/749 8.3.1 图的深度优先搜索遍历图的深度优先搜索遍历算法算法8.8深度优先遍历以邻接表为存储结构的图。深度优先遍历以邻接表为存储结构的图。void TraverGraph2(AdjList G) for (v=0;vG.vexnum;v+) visitedv=0;/*访问标志数组初始化访问标志数组初始化*/ for (v=0;vG.vexnum;v+) if (!visitedv) dfs2(G,v); /*从未被访问过的点出发遍历一个连通子图从未被访问过的点出发遍历一个连通子图*/ 2021/6/750 8.3.2 图的广度优先搜索遍历图的广度优先搜索遍历广度优先搜索广度优先搜索(breadth-first search)的基本思想的基本思想从图中某个顶点从图中某个顶点 v 出发，在访问了出发，在访问了 v 之后依次访问之后依次访问 v 的各的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得它们的邻接点，并使得“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访后被访问的顶点的邻接点问的顶点的邻接点”进行访问，直至图中所有已被访问的顶点的进行访问，直至图中所有已被访问的顶点的邻接点都被访问到。如若此时图中尚有顶点未被访问，则需另邻接点都被访问到。如若此时图中尚有顶点未被访问，则需另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以换句话说，广度优先搜索遍历图的过程是以 v 为起始点，为起始点，由近至远，依次访问和由近至远，依次访问和 v 有路径相通且最短路径长度为有路径相通且最短路径长度为 1,2, 的顶点。的顶点。2021/6/751v1v2v4v5v6v7v8v3无向图无向图G5由于广度优先搜索遍历要求由于广度优先搜索遍历要求先被访问的顶点的邻接点也先于先被访问的顶点的邻接点也先于后被访问的顶点的邻接点进行访后被访问的顶点的邻接点进行访问，因此在遍历过程中需要一个问，因此在遍历过程中需要一个队列保存被访问顶点的次序，以队列保存被访问顶点的次序，以便按照已被访问过的顶点的访问便按照已被访问过的顶点的访问次序先后访问它们的未曾被访问次序先后访问它们的未曾被访问过的邻接点。过的邻接点。广度优先顶点序列：广度优先顶点序列：v1 v2 v3 v4 v5 v6 v7 v8 8.3.2 图的广度优先搜索遍历图的广度优先搜索遍历2021/6/752w1w2vw7w8w3w5w6w4无向图无向图G7广度优先顶点序列：广度优先顶点序列：v w1 w2 w8 w7 w3 w5 w6 w4 在图上看这个广度优先搜索遍历在图上看这个广度优先搜索遍历的过程就好比的过程就好比“一石激起千重浪一石激起千重浪”，访，访问顶点问顶点 v 就好比将一块大石头扔进池就好比将一块大石头扔进池塘的中央，必然激起浪花，这个浪花塘的中央，必然激起浪花，这个浪花从中央向外四周扩散开来，渐渐波及从中央向外四周扩散开来，渐渐波及池塘中从近到远的其它池塘中从近到远的其它“石块石块”。 8.3.2 图的广度优先搜索遍历图的广度优先搜索遍历2021/6/753w1w2vw7w8w3w5w6w4w1w2vw7w8w3w5w6w4无向图无向图G7可以改变可以改变布局重新画图布局重新画图 G7，将顶点，将顶点 v 放在上方中央，放在上方中央，其余顶点按从其余顶点按从 v 到该顶点的到该顶点的最短路径长度最短路径长度分别放在第分别放在第2、3和和4层上，则层上，则图的广度优先图的广度优先搜索遍历的过搜索遍历的过程类似于树的程类似于树的按层次遍历的按层次遍历的过程。过程。广度优先顶点序列：广度优先顶点序列：v w1 w2 w8 w7 w3 w5 w6 w4 8.3.2 图的广度优先搜索遍历图的广度优先搜索遍历2021/6/754 8.3.2 图的广度优先搜索遍历图的广度优先搜索遍历算法算法8.9广度优先遍历以邻接矩阵为存储结构图的连通分量。广度优先遍历以邻接矩阵为存储结构图的连通分量。void bfs1(AdjMatrix ga,int k)/*k为出发点的序号为出发点的序号*/ r=0;f=0;/*置队空置队空*/ visit(k);/*访问出发点并入队访问出发点并入队*/ visitedk=1; r+; qur=k; while (r!=f) f+;i=quf;/*出队出队*/ for (j=0;jadjvex; if (!(visitedj) visit(j); visited(j)=1; r+;qur=j; p=p-nextarc; 2021/6/756 8.4连通网的最小生成树连通网的最小生成树8.4.1求无向图的连通分量求无向图的连通分量在对无向图进行遍历时，对于连通图，仅需要从图中任意在对无向图进行遍历时，对于连通图，仅需要从图中任意一个顶点出发，进行深度或广度优先搜索遍历，便可访问到图一个顶点出发，进行深度或广度优先搜索遍历，便可访问到图中所有顶点；对于非连通图，则需要从多个顶点出发，每一次中所有顶点；对于非连通图，则需要从多个顶点出发，每一次从一个新的顶点出发进行搜索，得到的顶点访问序列恰好是各从一个新的顶点出发进行搜索，得到的顶点访问序列恰好是各个连通分量中的顶点集合。个连通分量中的顶点集合。要想判断一个无向图是否为连通图，就可以设一个计数变要想判断一个无向图是否为连通图，就可以设一个计数变量量count，初始时值为，初始时值为0，在深度优先搜索算法中，每调用一次，在深度优先搜索算法中，每调用一次DFS，就给，就给count加加1，算法结束时，依据，算法结束时，依据count的值，就可确定的值，就可确定图的连通性和连通分量数。图的连通性和连通分量数。2021/6/757 8.4.1求无向图的连通分量求无向图的连通分量算法算法8.11求以邻接矩阵为存储结构图的无向图的连通分量。求以邻接矩阵为存储结构图的无向图的连通分量。void component(AdjMatrix g) int count=0; for (i=0;in;i+) visitedi=0; for (i=0;in;i+) if (!visitedi) count+; dfs1(g,i); printf(“comp endn”); printf(“total components:%dn”,count); 2021/6/758设边设边E(G)为连通图为连通图G中所有边的集合，则从图中中所有边的集合，则从图中任一顶点出发遍历图时，必将任一顶点出发遍历图时，必将E(G)分成两个集合分成两个集合T(G)和和B(G)，其中，其中T(G)是遍历过程中历经的边的集合；是遍历过程中历经的边的集合；B(G)是剩余的边的集合，则是剩余的边的集合，则T(G)和图中所有顶点构成和图中所有顶点构成连通图连通图G的极小连通子图，按生成树的定义，它是连的极小连通子图，按生成树的定义，它是连通图的一棵生成树。通图的一棵生成树。由深度优先搜索得到的称为由深度优先搜索得到的称为深度优先生成树深度优先生成树，由，由广度优先搜索得到的为广度优先搜索得到的为广度优先生成树广度优先生成树。 8.4.2生成树的概念生成树的概念2021/6/759 8.4.2生成树的概念生成树的概念图图G的深度优先生成树的深度优先生成树图图G的广度优先生成树的广度优先生成树2021/6/760 8.4.2生成树的概念生成树的概念一个连通图的生成树是指包含图中所有一个连通图的生成树是指包含图中所有n个顶点个顶点的极小连通子图。的极小连通子图。生成树的特点：生成树的特点： 有且仅有有且仅有n-1条边。条边。 在生成树中，任意加一条边，必构成回路。在生成树中，任意加一条边，必构成回路。 不惟一性。不惟一性。2021/6/761 8.4.3最小生成树最小生成树因为图的遍历序列不惟一，构造出来的生成树也就不惟一，因为图的遍历序列不惟一，构造出来的生成树也就不惟一，对连通图的不同遍历，就可能得到不同的生成树，生成树是连对连通图的不同遍历，就可能得到不同的生成树，生成树是连通图中的极小连通子图。如果无向连通图是一个网，则所有的通图中的极小连通子图。如果无向连通图是一个网，则所有的生成树中，必有一棵边的权值总和最小的生成树，称这棵生成生成树中，必有一棵边的权值总和最小的生成树，称这棵生成树为最小代价生成树，简称树为最小代价生成树，简称最小生成树或最小生成树或MST树树。最小生成树求解在实际生活中具有很重要的用途。用一个最小生成树求解在实际生活中具有很重要的用途。用一个连通网表示连通网表示 n 个居民点和各个居民点之间可能架设的通讯线路，个居民点和各个居民点之间可能架设的通讯线路，则网中每一条边上的权值表示架设这条线路所需经费。由于在则网中每一条边上的权值表示架设这条线路所需经费。由于在 n 个居民点间构建通讯网只需架设个居民点间构建通讯网只需架设 n-1 条线路，则工程队面临条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？这些问题均的问题是架设哪几条线路能使总的工程费用最低？这些问题均等价于，在含有等价于，在含有 n 个顶点的连通网中选择个顶点的连通网中选择 n-1 条边，构成一棵条边，构成一棵极小连通子图，并使该连通子图中极小连通子图，并使该连通子图中 n-1 条边上权值之和达到最条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。小，则称这棵连通子图为连通网的最小生成树。2021/6/762MST性质性质假设假设G=(V,E)是一个连通网，是一个连通网，U是顶点集是顶点集V的一个的一个非空子集。若非空子集。若(u,v)是一条具有最小权值（代价）的边，是一条具有最小权值（代价）的边，其中其中uU,vV-U，则必存在一棵包含边，则必存在一棵包含边(u,v)的最小的最小生成树。生成树。 8.4.3最小生成树最小生成树2021/6/763 普里姆算法普里姆算法算法要点算法要点首先选取图中任意一个顶点首先选取图中任意一个顶点 v 作为生成树的根，作为生成树的根，之后继续往生成树中添加顶点之后继续往生成树中添加顶点 w，则在顶点，则在顶点 w 和顶点和顶点 v 之间必须有边，且该边上的权值应在所有和之间必须有边，且该边上的权值应在所有和 v 相邻相邻接的边中属最小。在一般情况下，假设图接的边中属最小。在一般情况下，假设图 G=(V,E) 中中已落在生成树上的顶点集为已落在生成树上的顶点集为U，则尚未落在生成树上，则尚未落在生成树上的顶点集为的顶点集为 V-U，则从，则从 (V-U) 顶点集中选取加入生成顶点集中选取加入生成树的顶点树的顶点 w 应满足下列条件：它和生成树上的顶点之应满足下列条件：它和生成树上的顶点之间的边上的权值是在联接这两类顶点的所有边中权值间的边上的权值是在联接这两类顶点的所有边中权值属最小。属最小。 8.4.3最小生成树最小生成树2021/6/764连连通通网网G G8 8BDCEAF6812514161715BDCEAF8612145最最小小生生成成树树以右图所示连通网以右图所示连通网 G8为例，假设首先为例，假设首先选顶点选顶点 A 作为生成树的根，则此时只有顶作为生成树的根，则此时只有顶点点A 在生成树中，其余顶点在生成树中，其余顶点 B,C,D,E,F 均均不在生成树上，连接这两类顶点的边只有不在生成树上，连接这两类顶点的边只有(A,B)和和(A,C) ，其中以边，其中以边 (A,B) 的权值为最的权值为最小，由此应该选择边小，由此应该选择边 (A,B) 将顶点将顶点B加入到加入到生成树中，之后链接生成树中，之后链接 A,B 和和 C,D,E,F 这这两个顶点集的边除了原有的两个顶点集的边除了原有的(A,C) 之外，又之外，又增加了增加了 (B,D) 和和 (B,E)，在这，在这3条边中，权值条边中，权值最小的边为最小的边为(B,D)(权值权值=12)，自然应选边，自然应选边 (B,D)，即将顶点，即将顶点D加入到生成树中。之后加入到生成树中。之后应在链接顶点集应在链接顶点集 A,B,D 和和 C,E,F 的边集的边集 (A,C),(B,E),(D,C),(D,F) 中选择权值最小中选择权值最小的边的边(B,E),，依次类推，直至所有顶点，依次类推，直至所有顶点都落到生成树上为止。都落到生成树上为止。 8.4.3最小生成树最小生成树2021/6/765abcdefg1889320151615191820abcdefg18abcdefg818181593连通网连通网G G9 9最小生成树最小生成树过程中蓝色的边为待选边，过程中蓝色的边为待选边，红色的边为选中的边红色的边为选中的边 8.4.3最小生成树最小生成树2021/6/766BDCEAF8121516171465BDCEAF8612145连连通通网网G G8 8最最小小生生成成树树 克鲁斯卡尔算法克鲁斯卡尔算法基本思想基本思想为使生成树上总的权值之和达为使生成树上总的权值之和达到最小，则应使每一条边上的权值到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的尽可能地小，自然应从权值最小的边选起，直至选出边选起，直至选出 n-1 条条互不构成互不构成回路的权值最小边回路的权值最小边为止。具体作法为止。具体作法如下：首先构造一个只含如下：首先构造一个只含 n 个顶点个顶点的森林，然后依权值从小到大从连的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网成一棵树为止，这棵树便是连通网的最小生成树。的最小生成树。 8.4.3最小生成树最小生成树2021/6/767由于生成树上不允许有回路，由于生成树上不允许有回路，因此并非每一条当前权值最小的因此并非每一条当前权值最小的边都可选，例如，对右图所示连边都可选，例如，对右图所示连通网通网G9，在依次选中了，在依次选中了(e,f),(b,c),(e,d) 和和 (f,g) 的四条边之的四条边之后，权值最小边为后，权值最小边为 (g,d)，由于，由于 g 和和 d 已经连通，若加上已经连通，若加上(g,d) 这条这条边将使生成树上产生回路，显然边将使生成树上产生回路，显然这条边不可取，同理边这条边不可取，同理边 (f,d) 也不也不可取，之后则依次取可取，之后则依次取 (a,g) 和和 (a,b) 两条边加入到生成树。两条边加入到生成树。89320151615191820abcdefg18连通网连通网G G9 9 8.4.3最小生成树最小生成树2021/6/768 8.4.3最小生成树最小生成树两种算法的比较两种算法的比较 普里姆算法为普里姆算法为“加点法加点法”，克鲁斯卡尔算法为，克鲁斯卡尔算法为“加边加边法法”。 设设n为无向网中的顶点数，为无向网中的顶点数，e为其边的数目，可以证为其边的数目，可以证明普里姆算法的时间复杂度为明普里姆算法的时间复杂度为O(n2) ,克鲁斯卡尔算法克鲁斯卡尔算法的时间复杂度为的时间复杂度为O(e*loge)，前者与边数无关，适合较，前者与边数无关，适合较稠密的图，后者与边数相关，适合稀疏图。稠密的图，后者与边数相关，适合稀疏图。2021/6/769 8.5最短路径最短路径图或网还经常用于描述一个城市或城市间的交通运输网络，图或网还经常用于描述一个城市或城市间的交通运输网络，以图中顶点表示一个城市或某个交通枢纽，以边或弧表示两地以图中顶点表示一个城市或某个交通枢纽，以边或弧表示两地之间的交通状况，边或弧上的权值可表示各种相关信息，例如之间的交通状况，边或弧上的权值可表示各种相关信息，例如两地之间的路程长度，交通费用或行程时间等等。那么对于网两地之间的路程长度，交通费用或行程时间等等。那么对于网来说，两个顶点之间的路径长度就不再是来说，两个顶点之间的路径长度就不再是8.1节中所定义的路节中所定义的路径中径中“弧的数目弧的数目”，而是路径中，而是路径中“弧的权值之和弧的权值之和”。当两个顶点之间存在多条路径时，其中必然存在一条当两个顶点之间存在多条路径时，其中必然存在一条“最最短路径短路径”，即路径中弧的权值和取最小值的那条路径，本节就，即路径中弧的权值和取最小值的那条路径，本节就是讨论如何求得这条最短路径的算法。考虑到交通图的有向性，是讨论如何求得这条最短路径的算法。考虑到交通图的有向性，本节将讨论带权有向图本节将讨论带权有向图(有向网有向网)，并称路径中的第一个顶点为，并称路径中的第一个顶点为“源点源点”，路径中的最后一个顶点为，路径中的最后一个顶点为“终点终点”。以下讨论两种最常。以下讨论两种最常见的路径问题。见的路径问题。2021/6/770 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径从一个源点路到其他各顶从一个源点路到其他各顶点的最短路径问题是指：已知点的最短路径问题是指：已知一个有向网和网中某个源点，一个有向网和网中某个源点，求得从该源点到图中其它各个求得从该源点到图中其它各个顶点之间的最短路径。顶点之间的最短路径。如图如图 G10中，从源点中，从源点 a 到终点到终点 b 存在多条路径，如路径存在多条路径，如路径 a,b 的的长度为长度为24，路径，路径 a,c,e,g,b 的长的长度为度为27等，其中以路径等，其中以路径 a,d,g,b 的长度的长度(=22)为最短。类似地，为最短。类似地，从源点从源点 a 到其它各顶点也都存到其它各顶点也都存在一条路径长度最短的路径。在一条路径长度最短的路径。有向网有向网G G10101015abcdefg243453869272021/6/771如何求得这些最短路径？如何求得这些最短路径？迪杰斯特拉提出了一个迪杰斯特拉提出了一个“按各条按各条最短路径长度递增的次序最短路径长度递增的次序” 产生产生最短路径的算法。最短路径的算法。从有向网从有向网G10的例子可见，的例子可见，如果从源点到某个终点存在路如果从源点到某个终点存在路径，必存在一条路径长度取最径，必存在一条路径长度取最小值的路径，这些最短路径彼小值的路径，这些最短路径彼此之间的长度不一定相等，则此之间的长度不一定相等，则迪杰斯特拉算法正是按右侧所迪杰斯特拉算法正是按右侧所示，从源点示，从源点 a 到其它各终点的到其它各终点的最短路径长度递增的次序先后最短路径长度递增的次序先后产生这些最短路径。产生这些最短路径。1015abcdefg24345386927有向网有向网G G1010 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径2021/6/7721015abcdefg24345386927从源点从源点 a 到图中其它各终点到图中其它各终点的最短路径按路径长度从短到长的最短路径按路径长度从短到长依次为：依次为：路径路径a, c的长度为的长度为8，路径路径a, c, f的长度为的长度为11，路径路径a, c, f, e的长度为的长度为13，路径路径a, d的长度为的长度为15，路径路径a, d, g的长度为的长度为19，路径路径a, d, g, b的长度为的长度为22。 这应该是可以理解的，因为若它这应该是可以理解的，因为若它是由经过其它顶点构成的路径，是由经过其它顶点构成的路径，那么必定不是所有最短路径中长那么必定不是所有最短路径中长度最短的那条。度最短的那条。有向网有向网G G1010 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径2021/6/773a ab bc cd de ef fg ga a0 024248 81515b bc cd de ef f1010g g3 30 0G G1010的邻接矩阵的邻接矩阵1015abcdefg24345386927有向网有向网G G1010 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径2021/6/774假设假设 n 为图为图 G=(V,E) 中的顶点数，中的顶点数，distn 存放从源点到存放从源点到每个终点当前最短路径的长度，每个终点当前最短路径的长度，pathn 存放相应路径，存放相应路径，S 为为已求得最短路径的终点的集合。则迪杰斯特拉算法求最短路已求得最短路径的终点的集合。则迪杰斯特拉算法求最短路径的过程为：径的过程为： 令令 S=v0; /* v0 为源点为源点*/ disti=G.arcsv0vi并设定并设定disti的初始值为：的初始值为： 0当当=S时时wsi当当iS，且，且E，为弧上的权值，为弧上的权值当当iS，且，且E空串当空串当iS，或，或E“vs vi ”当当iS，且，且Edisti=pathi= 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径2021/6/775 选择顶点选择顶点k，使得，使得 distk=mindisti| viV-S，则，则vk为目为目前求得的从前求得的从v0出发的最短路径的终点，将顶点出发的最短路径的终点，将顶点 k并入到集合并入到集合S中。中。 修改从修改从v0出发到集合出发到集合V-S上每个顶点上每个顶点vi的最短路径的长度。的最短路径的长度。若若distk+G.arcskidisti，则将，则将disti修改为修改为distk+G.arcski。即若经过。即若经过vk中转会使路径长度更短，则中转会使路径长度更短，则修改路径长度。修改路径长度。 重复重复和和共共n-1次，即可按最短路径长度的递增顺序，次，即可按最短路径长度的递增顺序，逐个求出逐个求出v0到其他每个顶点的最短路径。到其他每个顶点的最短路径。例如对有向网例如对有向网 G10 执行迪杰斯特拉算法的过程如动画所示。执行迪杰斯特拉算法的过程如动画所示。 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径2021/6/776 8.5.1求某一顶点到其他各顶点的最短路径求某一顶点到其他各顶点的最短路径终点终点从从a到各个顶点的到各个顶点的D值和最短路径的求解算法值和最短路径的求解算法i=1i=2i=3i=4i=5i=6ba,b24a,b24a,b24a,b24a,b24a,d,g,b22ca,c8da,d15a,d15a,d15a,d15ea,c,e15a,c,f,e13fa,c,f11ga,c,f,g21vivcvfvevdvgvbSa,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b迪杰斯特算法执行过程中参数的变化迪杰斯特算法执行过程中参数的变化2021/6/777 8.5.2求任意一对顶点间的最短路径求任意一对顶点间的最短路径迪杰斯特拉算法实现的是从一个顶点到其余各顶点的最短路迪杰斯特拉算法实现的是从一个顶点到其余各顶点的最短路径问题。径问题。求任意一对顶点间的最短路径有如下方法求任意一对顶点间的最短路径有如下方法 依次将每个顶点为源点，重复执行迪杰斯特拉算法依次将每个顶点为源点，重复执行迪杰斯特拉算法n次。次。 采用专门解决此类问题的算法弗洛伊德算法。采用专门解决此类问题的算法弗洛伊德算法。弗洛伊德算法的基本思想弗洛伊德算法的基本思想首先以首先以vi到到vj的直接路径作为的直接路径作为vi到到vj的最短路径，然后每次在的最短路径，然后每次在路径上加入一个顶点，共进行路径上加入一个顶点，共进行n次测试和修正，分别得到中间顶次测试和修正，分别得到中间顶点序号不大于点序号不大于0的最短路径，中间顶点序号不大于的最短路径，中间顶点序号不大于1的最短路径，的最短路径，最后一次得到中间顶点序号不大于，最后一次得到中间顶点序号不大于n-1的最短路径即为最终的最短路径即为最终的最短路径。的最短路径。求得一个求得一个 n 阶方阵的序列阶方阵的序列D(-1), D(0), D(1), ,D(k),D(n-1)其中：其中：D(-1)ij 表示从顶点表示从顶点vi不经过其它顶点直接到达顶点不经过其它顶点直接到达顶点vj的路径长度，即的路径长度，即2021/6/778D(-1)ij=G.arcsij，D(k)ij 则表示中间只可能经过则表示中间只可能经过v0, v1 , , vk 等顶点，且不等顶点，且不可能经过可能经过 vk+1, vk+2, , vn-1等顶点的最短路径长度。等顶点的最短路径长度。由此，由此，D(n-1)ij 自然是从顶点自然是从顶点vi到顶点到顶点vj的最短路径长度。的最短路径长度。为了记下路径，和上列路径长度序列相对应有路径的方阵序列为了记下路径，和上列路径长度序列相对应有路径的方阵序列P(-1), P(0), P(1), ,P(k),P(n-1)弗洛伊德算法的基本操作为：弗洛伊德算法的基本操作为：if (Dik+Dkj Dij) Dij = Dik+Dkj; Pij = Pik+Pkj 其中其中 k 表示在路径中新增添考虑的顶点号，表示在路径中新增添考虑的顶点号，i 为路径的起始为路径的起始顶点号，顶点号，j 为路径的终止顶点号。为路径的终止顶点号。 8.5.2求任意一对顶点间的最短路径求任意一对顶点间的最短路径2021/6/779有向网有向网G11G11的邻接矩阵的邻接矩阵 8.5.2求任意一对顶点间的最短路径求任意一对顶点间的最短路径ABCDA063B501C302D8202021/6/780 8.5.2求任意一对顶点间的最短路径求任意一对顶点间的最短路径DD(-1)D(0)加顶点加顶点A AD(1)加顶点加顶点B BD(2)加顶点加顶点C C012301230123012300630630673067315015018501840132302390239023902382082072306230PP(-1)P(0)P(1)P(2)01230123012301230ABABADADABABADADABABA AB BC CADADABABA AB BC CADAD1BABABCBCBABABCBCB BA AD DBABABCBCB BA AD DB BC CA ABCBCB BC CD D2CACACDCDCACAC CA AB BCDCDCACAC CA AB BCDCDCACAC CA AB BCDCD3DADADBDBDADADBDBDBADBAD DB BA ADBDBD DB BC CD DB BC CA ADBDBD DB BC C有向网有向网G G1111各对顶点间的最短路径及其路径长度各对顶点间的最短路径及其路径长度2021/6/781DD(3)加顶点加顶点D D012300563140132340236230PP(3)01230A AD DB BA AD DB BC CADAD1B BC CA ABCBCB BC CD D2CACAC CD DB BCDCD3D DB BC CA ADBDBD DB BC C 8.5.2求任意一对顶点间的最短路径求任意一对顶点间的最短路径有向网有向网G G1111各对顶点间的最短路径及其路径长度各对顶点间的最短路径及其路径长度2021/6/782 8.6拓扑排序拓扑排序一个有向图中不存在环，则称作有向无环图，一个有向图中不存在环，则称作有向无环图，简称简称DAG图，它在工程计划和管理方面有着广泛而图，它在工程计划和管理方面有着广泛而重要的应用。除最简单的情况之外，几乎所有的工重要的应用。除最简单的情况之外，几乎所有的工程程(project)都可分为若干个称作都可分为若干个称作“活动活动”的子工程，的子工程，并且这些子工程之间通常受着一定条件的约束，例并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才如其中某些子工程必须在另一些子工程完成之后才能开始。对整个工程和系统，人们关心的是两方面能开始。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。本节和下一节将分别讨论这两排序和求关键路径。本节和下一节将分别讨论这两个算法。个算法。2021/6/783一项工程往往可以分解为一些具有相对独立性一项工程往往可以分解为一些具有相对独立性的子工程，通常称这些子工程为的子工程，通常称这些子工程为“活动活动”。子工程之。子工程之间在进行的时间上有着一定的相互制约关系，例如，间在进行的时间上有着一定的相互制约关系，例如，盖大楼的第一步是打地基，而房屋的内装修必须在盖大楼的第一步是打地基，而房屋的内装修必须在房子盖好之后才能开始进行等。可用一个有向图表房子盖好之后才能开始进行等。可用一个有向图表示子工程及其相互制约的关系，其中以顶点表示活示子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络，或图为活动在顶点上的网络，简称活动顶点网络，或AOV(Activity On Vertex)网。网。 8.6.1AOV网网2021/6/784在在AOV网中，若从顶点网中，若从顶点i到顶点到顶点j之间存在一条有之间存在一条有向路径，称顶点向路径，称顶点i是顶点是顶点j的前驱，或者顶点的前驱，或者顶点j是顶点是顶点i的后继。若的后继。若是图中的弧，则称是图中的弧，则称i为为j的直接前驱，的直接前驱，j为为i的之间后继。的之间后继。AOV网中弧表示了活动之间存在的网中弧表示了活动之间存在的制约关系。制约关系。 8.6.1AOV网网2021/6/785例如，假设一个软件工程人例如，假设一个软件工程人员必须系统学习如右所列各员必须系统学习如右所列各门课程，每个接受培训的人门课程，每个接受培训的人都必须学完和通过计划中的都必须学完和通过计划中的全部课程才能颁发合格证书。全部课程才能颁发合格证书。整个培训过程就是一项工程，整个培训过程就是一项工程，每门课程的学习就是一项活每门课程的学习就是一项活动，一门课程可能以其它若动，一门课程可能以其它若干门课程为先修基础，而它干门课程为先修基础，而它本身又可能是另一些课程的本身又可能是另一些课程的先修基础，各门课程之间的先修基础，各门课程之间的先修关系可以右图的活动顶先修关系可以右图的活动顶点网络表示。点网络表示。编号编号课程名称课程名称先修课程先修课程c1程序设计基础程序设计基础无无c2离散数学离散数学c9c3数据结构数据结构c1c2c4微机原理微机原理c5c5计算机系统结构计算机系统结构无无c6操作系统操作系统c3 c5c7数据库应用数据库应用c3c8编译原理编译原理c1 c3c9高等数学高等数学无无c10线性代数线性代数c9c11数值分析数值分析c1 c9 c10c12计算机网络计算机网络c5 c6c7 8.6.2拓扑排序拓扑排序2021/6/786在在AOV网中不允许出现有向环，否则意味着某项子工程网中不允许出现有向环，否则意味着某项子工程的开始以本身的完成为先决条件，显然这说明这个工程的施工的开始以本身的完成为先决条件，显然这说明这个工程的施工设计图存在问题。而如果这个有向图表示的是数据流图的话，设计图存在问题。而如果这个有向图表示的是数据流图的话，则表明存在着一个死循环。则表明存在着一个死循环。判别有向网中是否存在有向环的一个办法就是对此判别有向网中是否存在有向环的一个办法就是对此AOV网进行网进行“拓扑排序拓扑排序”，即构造一个包含图中所有顶点的，即构造一个包含图中所有顶点的“拓扑有拓扑有序序列序序列”，如果在，如果在AOV网中存在一条从顶点网中存在一条从顶点a到顶点到顶点b之间的弧，之间的弧，则在拓扑有序序列中顶点则在拓扑有序序列中顶点 a 必须领先于顶点必须领先于顶点 b，反之如果在，反之如果在AOV网中顶点网中顶点a和顶点和顶点b之间没有弧，则在拓扑有序序列中这之间没有弧，则在拓扑有序序列中这两个顶点的先后次序关系可以随意。两个顶点的先后次序关系可以随意。 8.6.2拓扑排序拓扑排序2021/6/787在在AOV活动中构造线性序列的性质活动中构造线性序列的性质 在在AOV网中，若顶点网中，若顶点i优先于顶点优先于顶点j，则在线性序列中仍然优，则在线性序列中仍然优先于顶点先于顶点j。 对于网中原来没有优先关系的顶点之间，在线性序列中确定对于网中原来没有优先关系的顶点之间，在线性序列中确定一个先后关系。一个先后关系。满足这样性质的线性序列称为拓扑序列，构造拓扑序列的满足这样性质的线性序列称为拓扑序列，构造拓扑序列的过程就是拓扑排序。过程就是拓扑排序。对对AOV网实施拓扑排序的方法和步骤：网实施拓扑排序的方法和步骤： 从从AOV网中选择一个没有前驱的顶点网中选择一个没有前驱的顶点(入度为入度为0)并输出。并输出。 从网中删除该顶点以及与其相关联的全部有向边。从网中删除该顶点以及与其相关联的全部有向边。 重复上述操作，直到剩余的网中不再存在没有前驱的顶点。重复上述操作，直到剩余的网中不再存在没有前驱的顶点。 8.6.2拓扑排序拓扑排序2021/6/788编编号号课程名称课程名称先修先修课程课程c1程序设计基础程序设计基础无无c2离散数学离散数学c9c3数据结构数据结构c1c2c4微机原理微机原理c5c5计算机系统结构计算机系统结构无无c6操作系统操作系统c3 c5c7数据库应用数据库应用c3c8编译原理编译原理c1 c3c9高等数学高等数学无无c10线性代数线性代数c9c11数值分析数值分析c1 c9 c10c12计算机网络计算机网络c5 c6c7c11c10c9c2c1c8c5c6c4c12c7c3 8.6.2拓扑排序拓扑排序有向图有向图G132021/6/789操作结果操作结果 网中所有顶点均被输出，网中所有顶点均被输出，网中不存在回路。网中不存在回路。 网中顶点未被全部输出，网中顶点未被全部输出，剩余的顶点均无前驱顶点，剩余的顶点均无前驱顶点，网中存在有向回路。网中存在有向回路。根据描述课程学习顺序制约根据描述课程学习顺序制约关系的关系的AOV网，可以得到以网，可以得到以下两个拓扑有序序列：下两个拓扑有序序列： 8.6.2拓扑排序拓扑排序C9 C10 C2 C1 C11 C3 C8 C7 C5 C6 C4 C12C5 C4 C1 C3 C6 C7 C12 C8 C9 C10 C11 C2有向图有向图G13c11c10c9c2c1c8c5c6c4c12c7c32021/6/790对上图的对上图的AOV网还可以得到更多的拓扑有序序列。网还可以得到更多的拓扑有序序列。显然，如果显然，如果AOV网中存在有向环，则不可能将所有顶点纳网中存在有向环，则不可能将所有顶点纳入到一个拓扑有序序列中，反之，如果从入到一个拓扑有序序列中，反之，如果从 AOV 网不能得到拓网不能得到拓扑有序序列，则说明网中必定存在有向环。扑有序序列，则说明网中必定存在有向环。v1v2v6v3v5v4有向图有向图G14拓扑排序结果拓扑排序结果V1 V2 V3 V4 V5 V6V1 V3 V4 V2 V5 V6注意注意拓扑排序结果不惟一。拓扑排序结果不惟一。 8.6.2拓扑排序拓扑排序2021/6/791 8.6.2拓扑排序拓扑排序例试列出图中所有拓扑排序。例试列出图中所有拓扑排序。解拓扑排序有解拓扑排序有1 5 6 2 3 45 1 2 6 3 41 5 2 6 3 45 6 1 2 3 41 5 2 3 6 45 1 6 2 3 45 1 2 3 6 42021/6/792 8.7图的应用举例图的应用举例2021/6/793图是一种比线性表和树更复杂的数据结构。在线性表中，图是一种比线性表和树更复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间存在着明驱和一个直接后继。在树形结构中，数据元素之间存在着明显的层次关系，并且每层的元素可能和下一层的多个元素显的层次关系，并且每层的元素可能和下一层的多个元素（即其孩子结点）相邻，但只能和上一层的一个元素（即其（即其孩子结点）相邻，但只能和上一层的一个元素（即其双亲结点）相关。而在图形结构中，结点之间的关系可以是双亲结点）相关。而在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都可能相邻。任意的，图中任意两个元素之间都可能相邻。和树类似，图的遍历是图的一种主要操作，可以通过遍和树类似，图的遍历是图的一种主要操作，可以通过遍历判别图中任意两个顶点之间是否存在路径、判别给定的图历判别图中任意两个顶点之间是否存在路径、判别给定的图是否是连通图并可求得非连通图的各个连通分量，但对于带是否是连通图并可求得非连通图的各个连通分量，但对于带权图（网），其最小生成树或最短路径都取决于弧或边上的权图（网），其最小生成树或最短路径都取决于弧或边上的权值，则需要有特定的算法求解。权值，则需要有特定的算法求解。 8.8本章小结本章小结2021/6/794部分资料从网络收集整理而来，供大家参考，感谢您的关注！