数据结构 Data Structure CSU 主讲人：王国军，郑瑾 中南大学信息院计科系 {csgjwang,zhengjin}@csu.edu.cn http://trust.csu.edu.cn/ 电话：0731-88877711 手机：13508486821 办公室：校本部计算机楼406-B 本PPT根据《数据结构》教材（清华大学）制作，仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。

Connectedness problems（连通性问题） Spanning tree problems（生成树问题） 图问题例 Path problems（路径问题） Connectedness problems（连通性问题） Spanning tree problems（生成树问题） Central point problems（中心点问题） Coloring problem（图着色问题） AOV/AOE （加权图） …（还有很多问题可以模型化为图问题）

第七章 图 7.1 抽象数据类型图的定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.6 拓扑排序 *7.7 关键路径 第七章 图 7.1 抽象数据类型图的定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.6 拓扑排序 *7.7 关键路径 7.8 两点之间的最短路径问题

7.1 抽象数据类型图的定义 v w v w 一、 图的定义和术语 (u,v) <u,v> 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 有向图——有向图G是由两个集合V(G)和E(G)组成的 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头(顶点对是有序的） 无向图——无向图G是由两个集合V(G)和E(G)组成的 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) （顶点对是无序的） (u,v) <u,v> v w 问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。 v w

图的示例 有向图G1=（V，E）中：V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>} 例 1 5 7 3 2 4 G2 6 无向图G2=（V，E）中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}

图的定义和术语（续） 有向完全图——有n(n-1)条弧和n个顶点的有向图 无向完全图——有n(n-1)/2条边和n个顶点的无向图 稀疏图--若边或弧的个数 e<nlogn，则称作稀疏图，否则称稠密图。 权—把图的边或弧赋予一个有意义的数，此数叫权 带权图-网—弧或边带权的图分别称作有向网或无向网。 子图——如果图G(V,E)和图G’(V’,E’)满足： V’V 且 E’E，则称G’为G的子图 顶点的度 无向图中，顶点的度为与该顶点相连的边数 有向图中，顶点的度分成入度和出度 入度：以该顶点为弧头的弧的数目 出度：以该顶点为弧尾的弧的数目 证明： ①完全无向图有n(n-1)/2 条边。 证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，…，顶点n-1有1条边,顶点n有0条边. 总边数＝ n-1＋ n-2＋…＋1＋0=（n-1+0)n/2= n(n-1)/2 ② 完全有向图有n(n-1)条边。 证明：若是完全有向图，则顶点1必必与所有其他顶点各有2条连线，即有2(n-1)条边， 顶点2有2(n-2)条边，…，顶点n-1有2条边,顶点n有0条边. 总边数＝2( n-1＋ n-2＋…＋1＋0)=2(n-1+0)n/2= n(n-1)

n = 3 n = 2 n = 4 n = 1 完全图 4

1 2 1 1 2 2 3 3 3 3 邻接点 如果(u, v)是E(G)中的一条边，则称u 与v互为邻接的顶点。  与v互为邻接的顶点。 子图 设有两个图G＝(V, E)和G’＝(V’, E’)。若 V’V且E’E，则称图G’ 图G的子图。  子图 1 2 1 1 2 2 3 3 3 3 权 某些图的边具有与它相关的数，称之为权。  这种带权图叫做网络。 5

无向图 G1 有向图 G2 G1的某些子图 G2的某些子图 6

B 有向网 A E C F 15 9 7 21 11 3 2 例 2 1 3 有向完全图 无向完全图 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 顶点的度(TD)=出度(OD)+入度(ID)

路径： 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)要求是属于E的边。 非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。 路径长度： 简单路径： 路径上各顶点 v1,v2,...,vm 均不重复。 回路： 若路径上第一个顶点 v1 与最后一个顶点vm 重复，则称这样的路径为回路或环。 例 2 4 5 1 3 6

路径1→3：1,2,3 |（ 1，2，3，5，6，3 ） 路径长度：2 (5) 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 例 2 4 5 1 3 6 G1 路径1→3：1,2,3 |（ 1，2，3，5，6，3 ） 路径长度：2 (5) 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3 例 1 5 7 3 2 4 G2 6 路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1

连通图 2 3 8 1 4 5 9 6 7 在无向图中, 若从顶点vi到顶点vj有路径, 则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 强连通图 4 5 6 例2 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj的路径和从一条vj到vi的路径, 则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。 例3 2 3 1

非连通图，连通分量 2 3 8 10 1 4 5 9 11 6 7

对非连通图，则称由各个连通分量的生成树的集合 为该非连通图的生成森林。 生成树 一个连通图的生成树是其极小连通子 图，在n个顶点的情形下，有n-1条边。 对非连通图，则称由各个连通分量的生成树的集合 为该非连通图的生成森林。 A A B C B C G E D F D E F G 深度优先生成树 10 有向图

二、图的基本操作 图结构的建立和销毁 对顶点的访问操作 插入和删除顶点 插入和删除弧（边） 对邻接点的操作 遍历

结构的建立和销毁 CreateGraph(&G, V, VR): // 按定义(V, VR) 构造图 DestroyGraph(&G): // 销毁图

对顶点的访问操作 LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在 图中的“位置”; 否则返回其它信息。 GetVex(G, v); // 返回 v 的值。 PutVex(&G, v, value); // 对 v 赋值value。

对邻接点的操作 FirstAdjVex(G, v); // 返回 v 的“第一个邻接点”。若该顶点 NextAdjVex(G, v, w); // 返回 v 的（相对于 w 的）“下一个邻接点”。若 w 是 v 的最后一个邻接点，则 返回“空”。

插入和删除顶点 InsertVex(&G, v); // 在图G中增加新顶点v。 DeleteVex(&G, v);

插入和删除弧 InsertArc(&G, v, w); // 在G中增加弧<v, w>，若G是无向的， // 则还增加对称弧(w, v)。 DeleteArc(&G, v, w); // 在G中删除弧<v, w>，若G是无向的， // 则还删除对称弧(w, v)。

图的遍历--（用的最多，最重要） DFSTraverse(G, v, Visit()); // 从顶点v起深度优先遍历图G，并对每 个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); // 从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。

7.2 图的存储表示 一、图的数组存储表示-- (邻接矩阵) 二、图的邻接表存储表示（很常用！） 三、有向图的十字链表存储表示 7.2 图的存储表示 一、图的数组存储表示-- (邻接矩阵) 二、图的邻接表存储表示（很常用！） 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示

定义：设G=(V, E)是有n1个顶点的图，G的邻接矩阵A（二维数组）是具有以下性质的n阶方阵： 一、图的数组(邻接矩阵)存储表示 用两个数组分别存储顶点信息和顶点之间的关系信息(邻接矩阵—表示顶点之间相邻关系的矩阵) 定义：设G=(V, E)是有n1个顶点的图，G的邻接矩阵A（二维数组）是具有以下性质的n阶方阵： 例 G1 2 4 1 3      例 1 5 3 2 4 G2 　由于图结构中任意两个顶点之间都可能存在"关系"，因此无法以顺序存储映象表示这种关系，即图没有顺序存储结构。    

邻接矩阵的特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和 (第i行非0元素即1的个数) 先讲无向图的邻接矩阵，引导学生归纳特点，再引有向图邻接矩阵及其特点，以便省时          例 1 5 3 2 4 G2 例 G1 2 4 1 3

加权图（网）的邻接矩阵示意图 加权图的邻接矩阵可定义为： ∞ 反之 ∞ 反之      例 1 4 5 2 3 7 8 6 引导学生设想网的存储结构，然后点评 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。 邻接矩阵的优点： 邻接矩阵的缺点：

一、图的数组(邻接矩阵)存储表示 #define MAX_VERTEX_NUM 20 // 定义图的类型 { 有向图, 有向网,无向图, 无向网} typedef enum{ DG, DN, UDG, UDN } GraphKind; typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型, //对无权图， 用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针( 有时忽略此项） } ArcCell , AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { // 图的定义 VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组 AdjMatrix arcs; //邻接矩阵，可设二维 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 } MGraph;

一、图的数组(邻接矩阵)存储表示实例 G2.vexs={[1，2，3，4，5}； G1.vexs={1，2，3，4}； G1.arcs= MGraph G2; MGraph G1; G2.vexs={[1，2，3，4，5}； G1.vexs={1，2，3，4}；          G1.arcs=     G2.arcs= G1.vexnum=4； G1.arcnum=4； G1.kind=DG； G2.vexnum=5； G2.arcnum=6； G2.kind =UDG；

二、图的邻接表存储表示 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）；同时，为每个单链表附设一个表头结点，并将所有的表头结点顺序存储（数组），以便随机访问任一顶点的链表。 表头结点结构: 数据域（data）用于存储顶点的名或其它有关信息； 链域（firstarc）用于指向链表中与顶点 vi邻接的第一个邻接结点） 弧（边）结点结构：adjvex 与顶点vi邻接的点在图中的位置 info 存储和边相关的信息(若无，则置空NULL) nextarc 指向下一条弧的指针 data firstarc adjvex info nextarc 表头结点 弧结点

图的邻接表存储实例 提示：在无向图，每一个边结点在图的单链表中出现两次，故无向图中若有n个顶点和e条边，则需要存储空间为：n+2e 1 2 3 4 a c d b vexdata firstarc ^ adjvex nextarc 例 G1 b d a c 1 2 3 4 a c d b vexdata firstarc ^ adjvex nextarc 5 e 例 a e c b d G2 提示：在无向图，每一个边结点在图的单链表中出现两次，故无向图中若有n个顶点和e条边，则需要存储空间为：n+2e

二、图的邻接表存储表示 typedef struct ArcNode // 弧结点 adjvex nextarc info typedef struct ArcNode // 弧结点 { int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *nextarc; //链域，指示依附于vi的下一条边或弧的结点， VRType weight; InfoType *info; // 可省略此项 }ArcNode ; 　　 　 //定义 指向该弧相关信息的指针　　　　　 typedef struct VNode //表头结点 { VertexType vexdata; //存放顶点信息 ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }VNode，AdjList[MAX_VERTEX_NUM]; vexdata firstarc typedef struct { //图的结构定义 AdjList vertices; //顶点向量 int vexnum, arcnum; GraphKind kind; // 图的种类标志 } ALGraph;

邻接表特点 无向图中顶点vi的度为第i个单链表中的结点数 有向图中 顶点vi的出度为第i个单链表中的结点个数 顶点vi的入度为整个单链表中邻接点域值是i的结点个数（以vi为弧头）。 注：需遍历整个邻接表才能得到某个顶点的入度。改善办法：逆邻接表。

逆邻接表 为了便于求任一顶点的入度，我们可以对每一个顶点vi再建立一个逆邻接表，即对每个顶点vi建立一个所有以顶点vi为弧头的弧的表，如图所示。 例 G1 b d a c 1 2 3 4 a c d b vexdata firstarc ^ adjvex nextarc 1 2 3 4 a c d b vexdata firstarc ^ adjvex nextarc 表述思想，引导学生分析设计，培养抽象、建模能力 图G1的邻接表 和 逆邻接表

练习： 求下图各顶点的出度、入度，图的邻接矩阵、邻接表和逆邻接表 图 G1 c d a b e

讨论：邻接表与邻接矩阵有什么异同之处？ 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于该行中非零元素的个数。 2. 区别： ① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 ② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 3. 用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)。

0 A 4 1 1 B 5 4 0 2 C 5 3 3 D 5 2 4 E 1 0 5 F 3 2 0 补充：建立（有/无向图的邻接表） 图的邻接表是应用较多的一种存储结构。从邻接表的结构定义可见，建立邻接表的主要操作是在链表中插入一个结点。以下是输入无向图的顶点和边建立邻接表的算法步骤。 头插法 B C A F E D vexdata firstarc adjvex nextarc 0 A 4 1 1 B 5 4 0 2 C 5 3 3 D 5 2 4 E 1 0 5 F 3 2 0 从算法执行步骤可见，每生成一个表结点之后是按在第2章中惯用的“头插法”建立链表的方法将生成的结点插入到相应顶点的邻接表中的。并且对于无向图，每输入一条边需要生成两个结点，分别插入在这条边的两个顶点的链表中。即无向图的邻接表中弧结点的个数为图中边的数目的两倍。 依次输入的数据为： 1.顶点、边数： 6 7 UDG 2.顶点： A B C D E F 3. 边：AB AE BE BF CD CF DF

A B C D E A B E C D 1 4 2 3 0 1  0 1 2 3 4 建立有向图的邻接表（续） 建立邻接表的主要操作是在链表中插入一个结点。以下是输入有向图的顶点和弧建立邻接表的算法。 尾插法 A B E C D 1 4 2 3 0 1 0 1 2 3 4 A B C D E  依次输入的数据为： 1.　5 7 DG 2.　A B C D E 3.　AB AE BC CD DA DB EC

建立有（无）向图（网）的邻接表算法描述 void CreateGraph(ALGraph &G) {// 生成图G的存储结构-邻接表 cin >> G.vexnum >> G.arcnum >> G.kind; // 输入顶点数、边数和图类：1 for (i=0; i<G.vexnum; ++i) { 　 // 构造顶点数组： 2 cin>> G.vertices[i].data;　　　// 输入顶点 G.vertices[i].firstarc = NULL; } // 初始化链表头指针为"空" for (k=0; k<G.arcnum; ++k) // 输入各边并构造邻接表： 3 { cin>> sv >> tv; 　　　　　// 输入一条边（弧）的始点和终点 i = LocateVex(G, sv); j = LocateVex(G, tv); // 确定sv和tv //在G中位置，即顶点在G.vertices中的序号 vexdata firstarc adjvex nextarc pi = new ArcNode; if (!pi) exit(-1); 　　　　　　　 // 存储分配失败 pi -> adjvex = j; 　　　　　　　　// 对弧结点赋邻接点"位置" if (G.kind==DN || G.kind==DG)　cin >> w >> p; // 有向图输入权值和其它信息存储地址 else { w=0; p=NULL; } pi->weight = w; pi->info = p; pi -> nextarc = G.vertices[i].firstarc; //头插法，将tv结点插入到第i个单链表中 G.vertices[i].firstarc = pi;　　　 // 插入链表G.vertices[i]

建立有（无）向图（网）的邻接表算法描述（续） if (G.kind==UDG || G.kind==UDN) { // 对无向图或无向网尚需建立tv的邻接点：4 pj = new ArcNode; if (!pi) exit(-1); 　　　　// 存储分配失败 pj -> adjvex = i;　// 对边结点赋邻接点“位置” pj -> weight = w; pj->info = p; //头插法，将sv结点插入到第j个单链表中, 插入链表G.vertices[j] pj -> nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = pj; } // if } // for } // CreateGraph 　　 对于一个含 n 个顶点和 e 条边的无向图，e 的最大值为 n(n-1)/2。称含有 n 个顶点和 n(n-1)/2 条边的图为完全图。如果图中边的数目 e<nlogn，则称为稀疏图，反之称为稠密图。容易理解，由于邻接矩阵的存储空间是 n2 级的，而邻接表的空间复杂度是 O (n+e)。因此通常，稠密图的存储结构取"数组表示"，稀疏图的存储结构取"邻接表表示"。

三、有向图的十字链表存储表示 是有向图的邻接表和逆邻接表的组合 引导学生回忆有向图的邻接表和逆邻接表，与此对比讲解十字链表较好，便于学生理解其实质

有向图 十字链表表示示意图 提示：演示先画出有向图的邻接表，然后再建立其逆邻接表 特点：很容易求结点的出度和入度，而且不浪费存储空间

三、有向图的十字链表存储表示 弧结点： tailvex headvex hlink tlink info typedef struct ArcNode { int tailvex, headvex; //弧尾、弧头在表头数组中位置 struct ArcNode *hlink；//指向弧头相同的下一条弧 struct ArcNode *tlink; //指向弧尾相同的下一条弧 VRType weight; InfoType *info; // 定义弧的相关信息，如权值，可没有此项 } ArcNode; 顶点结点： data firstin firstout typedef struct VexNode { int data; //存与顶点有关信息 ArcNode *firstin； //指向以该顶点为弧头的第一个弧结点 ArcNode *firstout; //指向以该顶点为弧尾的第一个弧结点 }VexNode; 虽然在有向图的邻接表和逆邻接表中分别可以找到从顶点出发的弧和指向顶点的弧，但对于同一个有向图需要用两个结构来表示它毕竟不方便，因此当应用问题中同时需要对这两种弧进行处理时就需要采用十字链表来表示有向图。 十字链表是有向图的另一种链式存储结构，目的是将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。 是邻接表和逆邻接表两者的结合：对于有向图中的每一条弧有一个弧结点，每一个顶点有一个顶点结点。 typedef struct { //图的定义 VexNode xlist[MAX_VERTEX_NUM]; // 顶点结点(表头向量) int vexnum, arcnum; //有向图的当前顶点数和弧数 } OLGraph; 图示演示 7-2-1

四、无向图的邻接多重表存储表示 类似于有向图的十字链表，若将无向图中表示同一条边的两个结点合在一起，将得到无向图的另一种表示方法--邻接多重表。（便于对边进行标记或插入删除边等操作） 例如，无向图G2的邻接多重表如下所示(忽略相关信息指针） B C A F E D 43

四、无向图的邻接多重表存储表示 mark ivex ilink jvex jlink info 顶点结点： data firstedge 在邻接多重表中，每一条边用一个结点表示，边结点结构如下： mark ivex ilink jvex jlink info const MAX_VERTEX_NUM = 20; typedef enum {unvisited, visited} VisitIf; typedef struct EdgeNode{ 　　　　// 边结点结构定义 　VisitIf mark; 　　　　　　　　　// 访问标记 　int ivex, jvex; 　　　// 该边依附的两个顶点（vi，vj）在图中的位置 　struct EdgeNode *ilink, *jlink; // 分别指向依附这两个顶点的下一条边 　VRType weight; 　　　　　　 // 与弧相关的权值，无权则为0 　InfoType *info; 　　　　　　　　// 与该边相关信息的指针 } ; typedef struct { 　// 顶点结点结构定义　　　 VertexType data; 　 EdgeNode *firstedge;　// 指向第一条依附该顶点的边 　} VexNode; typedef struct { 　　// 多重链表结构定义 　VexNode adjmulist[MAX_VERTEX_NUM]; 　int vexnum, edgenum;　// 无向图的当前顶点数和边数 　GraphKind kind; 　　　　// 图的种类标志 } AMLGraph; 顶点结点： 由于无向图的邻接表中每一条边有两个结点，给对图的边进行访问的操作带来不便。以无向图G2为例，当从顶点A出发访问了边(A,E)之后，为了下次不再对这条边进行访问，就需要找到表示这条边的另一个结点加上访问标志。由此可类似于有向图，只用一个结点表示一条边，即将该边的所有信息(边两端的两个顶点、与其中一个端点有相同端点的下一条边的信息等)放在一个结点中，由于无向图中的边是没有方向性的，因此所有有一个端点相同的边均链接在同一链表中，所以在顶点结点中只有一个链表的头指针。另一方面，因为每一条边有两个顶点，因此每个边结点都链接在两个链表中，但它们之间并不形成“十字”关系。 类似于有向图的十字链表，若将无向图中表示同一条边的两个结点合在一起，将得到无向图的另一种表示方法--邻接多重表。 data firstedge 44 44

各种存储结构的适用类型 数组(邻接矩阵)：有向图和无向图 邻接表（逆邻接表）：有向图和无向图 十字链表：有向图 邻接多重表：无向图

7.3 图的遍历 图的遍历（Traversing Graph）: 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。 V1 V2 V4 V5 V3 V7 V6 V8 例 提示：前面学习过树的遍历有递归遍历（先序、中序和后序）和非递归算法 演示 提问：树的遍历能否用于图的遍历？不能！因为图有回路，若用树的遍历算法可能导致无限循环。为防止循环，需设置访问标志。而且，图可能不连通，若不加修改地使用树的遍历，还可能会遗漏图中的一部分顶点。

根据搜索路径方向不同： 深度优先搜索（纵向↓） 广度优先搜索（横向→） 遍历应用举例 vi未被访问: visited[i]值为false 为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此我们为图设置一个访问标志数组visited［n］: vi未被访问: visited[i]值为false vi已被访问：visited[i]值为true 根据搜索路径方向不同： V1 V2 V4 V5 V3 V7 V6 V8 例 深度优先搜索（纵向↓） 广度优先搜索（横向→） 遍历应用举例

一、深度优先搜索遍历图 深度优先搜索(Depth-First Search—DFS)是指按照深度方向搜索,它类似于树的先根遍历,是树的先根遍历的推广。 深度优先搜索连通子图的基本思想是： 假设图G初态为所有顶点未被访问（visited[i]=false），从G中任选一顶点vi： ⑴ 从该顶点vi出发,首先访问vi,置visited [vi ]=true; ⑵ 然后依次搜索vi的每一个邻接点vj； ⑶ 若vj未被访问过，则以vj为新的初始出发点，重复⑴ 若vj已被访问过，则返回到vi另一个邻接点，重复⑶ ⑷ 如果经过⑴、⑵、⑶后,图中仍有未被访问的顶点,再从中任选一顶点,重复⑴、⑵、⑶，直至所有顶点都被访问过，遍历结束。 深度优先搜索DFS（Depth_First Search） 1. 从图中任一个顶点v出发，访问该顶点； 2. 然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到； （连通图） 3. 此时若图中尚有顶点未被访问，则另选图中下一个未被访问的顶点作起始点，访问该顶点，继续过程2，直到图中所有顶点都被访问到为止。 V1 V2 V4 V5 V3 V7 V6 V8 例 无向图 V1 V2 V4 V5 V3 V7 V6 V8 例 有向图 深度优先遍历：V1 V2 V4  V8 V5 V3 V6 V7

Depth-First Search Example 2 3 8 10 1 4 5 9 11 6 7 2 1 Start search at vertex 1. Label vertex 1 and do a depth first search from either 2 or 4. Suppose that vertex 2 is selected.

Depth-First Search Example 2 2 2 3 8 1 1 4 5 5 9 10 6 7 11 Label vertex 2 and do a depth first search from either 3, 5, or 6. Suppose that vertex 5 is selected.

Depth-First Search Example 2 2 2 3 8 1 1 4 5 5 5 9 9 10 6 7 11 Label vertex 5 and do a depth first search from either 3, 7, or 9. Suppose that vertex 9 is selected.

Depth-First Search Example 2 2 2 3 8 8 1 1 4 5 5 5 9 9 9 10 6 7 11 Label vertex 9 and do a depth first search from either 6 or 8. Suppose that vertex 8 is selected.

Depth-First Search Example 2 2 2 3 8 8 8 1 1 4 5 5 5 9 9 9 10 6 6 7 11 Label vertex 8 and return to vertex 9. From vertex 9 do a dfs(6).

Depth-First Search Example 2 2 2 3 8 8 8 1 1 4 4 5 5 5 9 9 9 10 6 6 6 7 11 Label vertex 6 and do a depth first search from either 4 or 7. Suppose that vertex 4 is selected.

Depth-First Search Example 2 2 2 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 11 Label vertex 4 and return to 6. From vertex 6 do a dfs(7).

Depth-First Search Example 2 2 2 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 7 11 Label vertex 7 and return to 6. Return to 9.

Depth-First Search Example 2 2 2 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 7 11 Return to 5.

Depth-First Search Example 2 2 2 3 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 7 11 Do a dfs(3).

Depth-First Search Example 2 2 2 3 3 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 7 11 Label 3 and return to 5. Return to 2.

Depth-First Search Example 2 2 2 3 3 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 7 11 Return to 1.

Depth-First Search Example 2 2 2 3 3 3 8 8 8 1 1 4 4 4 5 5 5 9 9 9 10 6 6 6 7 7 7 11 Return to invoking method.

思考题：按图的存储结构如何遍历？ 深度优先遍历：v1 v1 v2 v4 v5 v3 v7 v6 v8 例 v3  v7  v6  算法思想：（设 vi=v1） 访问 vi 。 求 vi的邻接点 vj 。 若vj未被访问过，则以vj为新的初始出发点，重复⑴； 若vj已被访问过，则返回到vi另一个邻接点，重复⑶。 深度优先遍历：v1 v3  v7  v6  v2  v5  v8  v4 1 2 3 4 v1 v3 v4 v2 vexdata firstarc 7 8 ^ adjvex next 5 v5 6 v6 v7 v8 邻接矩阵如何？

v1 v2 v4 v5 v3 v7 v6 v8 例 深度优先遍历：v1 v3  v7  v6  v2  v4  v8  v5 1 2 3 4 vexdata firstarc 7 8 ^ adjvex next 5 6

从上页的遍历过程可见: 1. 深度优先搜索遍历连通图的过程类似于树的先根遍历。 2. 如何判别v的邻接点是否已被访问？ 解决的办法是：为每个顶点v设立一个 “访问标志 visited[v]”。 3. 如何求v的邻接点？ 解决的办法是：根据图的存储结构来确定。 对于邻接表而言，通过顶点向量和对应的单链表查找邻接点。

深度优先遍历算法-递归算法 开始 访问v,置标志 求v邻接点 有邻接点w？ 求V的下一邻接点 w→v w访问过？ 返回 N Y DFS

void DFS(Graph G, int v) { // 从顶点v出发，深度优先搜索遍历连通图 G 开始 访问v,置标志 求v邻接点 有邻接点w？ 求下一邻接点 w→v w访问过？ 返回 N Y DFS void DFS(Graph G, int v) { // 从顶点v出发，深度优先搜索遍历连通图 G visited[v] = TRUE; VisitFunc(v); for ( w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w)) //返回v的(相对于w)下一邻接点 if (!visited[w]) DFS(G, w); // 对v的尚未访问的邻接顶点w 递归调用DFS } // DFS 提示： 对于连通图，从任一顶点v出发，能够深度优先搜索遍历 整个图 G，访问所有结点； 而对于非连通图，则需从多个顶点出发，方可以完全遍历。

非连通图的深度优先搜索遍历 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点进行深度优先搜索遍历，否则继续检查下一个顶点。

a a b b g g c c d d e e f f h h i k a c h d i f e b g 例如: a a b b g g c c d d e e f f h h i k 0 1 2 3 4 5 6 7 8 访问标志: F F F F F F F F F T T T T T T T T T 访问次序: a c h d i f e b g

VisitFunc = Visit; //初始化访问函数 for (v=0; v<G.vexnum; ++v) void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图 G 作深度优先遍历。 VisitFunc = Visit; //初始化访问函数 for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; // 访问标志数组初始化 if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS } 开始 标志数组初始化 v=0 v访问过? DFS v=v+1 v<vexnum? 结束 N Y

DFS 算法效率分析: （设图中有 n 个顶点，e 条边） 如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行中的每一条边，因此遍历全部顶点所需的时间为O(n2)。 如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历（∵判断访问标志），加上访问 n 个头结点的时间，因此遍历图的时间复杂度为O(n+e)。 结论： 稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。

二、广度优先搜索遍历图（树的层次遍历的推广） 1. 从图中某顶点v出发，在访问v之后， 2. 依次访问v的各个未曾被访问过的邻接点， 3. 然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已经被访问的顶点的邻接点都被访问到； 4. 若图中尚有顶点未曾被访问，则另选图中一个未曾被访问的顶点作起始点，访问该顶点，继续过程2、3，直至图中所有顶点都被访问到为止。 V1 V2 V4 V5 V3 V7 V6 V8 例 无向图 V1 V2 V4 V5 V3 V7 V6 V8 例 有向图 序列：V1 V2 V3 V4 V5 V6 V7 V8 序列：V1 V2 V3 V4V6 V7 V8 V5

Breadth-First Search Example 2 3 8 10 1 4 5 9 11 6 7 Start search at vertex 1.

Breadth-First Search Example FIFO Queue 1 2 3 8 1 1 4 5 9 10 6 7 11 Visit/mark/label start vertex and put in a FIFO queue.

Breadth-First Search Example FIFO Queue 1 2 3 8 1 1 4 5 9 10 6 7 11 Remove 1 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 2 4 8 1 1 4 4 5 9 10 6 7 11 Remove 1 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 2 4 8 1 1 4 4 5 9 10 6 7 11 Remove 2 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 4 5 3 6 8 1 1 4 4 5 5 9 10 6 6 7 11 Remove 2 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 4 5 3 6 8 1 1 4 4 5 5 9 10 6 6 7 11 Remove 4 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 5 3 6 8 1 1 4 4 5 5 9 10 6 6 7 11 Remove 4 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 5 3 6 8 1 1 4 4 5 5 9 10 6 6 7 11 Remove 5 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 3 6 9 7 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 5 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 3 6 9 7 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 3 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 6 9 7 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 3 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 6 9 7 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 6 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 9 7 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 6 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 9 7 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 9 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 7 8 8 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 9 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 7 8 8 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 7 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 8 8 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 7 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 8 8 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Remove 8 from Q; visit adjacent unvisited vertices; put in Q.

Breadth-First Search Example 2 FIFO Queue 2 3 3 8 8 1 1 4 4 5 5 9 9 10 6 6 7 7 11 Queue is empty. Search terminates.

思考题：按图的存储结构如何遍历？ 广度遍历：V1 邻接矩阵如何？ V1 V2 V4 V5 V3 V7 V6 V8 例 算法思想（设vi=v1） 广度遍历：V1 V3  V2  V7  V6  V5  V4  V8 1 2 3 4 v1 v3 v4 v2 vexdata firstarc 7 8 ^ adjvex next 5 v5 6 v6 v7 v8 邻接矩阵如何？

说明： 的路径长度为1； V1 ->V4, V1 ->V5, V1 ->V6, V1 ->V7 的路径长度为2； 例 V1 ->V4, V1 ->V5, V1 ->V6, V1 ->V7 的路径长度为2； V1 ->V8 的路径长度为3。

为避免重复访问, 需要一个辅助数组 visited[n]，给被访问过的顶点加标记。 为了实现逐层（按顶点的路径长度递增）访问, 算法中需使用一个队列,以记录正在访问的这一层和下一层的顶点,以便于向下一层访问。

广度优先搜索遍历图算法流程图 BFS a 开始 V入队 Y 结束 N 访问V,置标志 求U邻接点W W存在吗 U下一邻接点W W访问过 初始化队列 V入队 队列空吗 队头出队U 访问W,置标志 W入队 a BFS 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

广度优先搜索遍历图算法 void BFSTraverse(Graph G, Status (*Visit)(int v)) { for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; //初始化访问标志 InitQueue(Q); //置空的辅助队列Q for ( v=0; v<G.vexnum; ++v ) if ( !visited[v]) // v 尚未访问 { // 调用BFS() } } // BFSTraverse 开始 标志数组初始化 v=0 v访问过 BFS v=v+1 v<vexnum? 结束 N Y BFS( G, v)；

广度优先搜索遍历图算法-续 BFS void BFS(Graph G, int v){ 开始 访问v,置标志 求u邻接点w w存在吗 u下一邻接点w w访问过 结束 N Y 初始化队列 v入队 队列空吗 队头出队u 访问w,置标志 w入队 a BFS void BFS(Graph G, int v){ visited[v] = TRUE; Visit(v); // 访问v EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u); // 队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE; Visit(w); EnQueue(Q, w); // 访问的顶点w入队列 } // if } // while }

BFS 算法效率分析: 同DFS （设图中有 n 个顶点，e 条边） DFS与BFS之比较： 邻接表存储图，则BFS的时间复杂度：O(n+e)； 邻接矩阵存储图，则BFS的时间复杂度：O(n2)。 DFS与BFS之比较： 空间复杂度相同，都是O(n)(借用了堆栈或队列）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

2. 求两个顶点之间的一条最短的路径 课下思考 若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?

g f b a c e d k h 深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。 因此，求路径长度最短的路径可以基于广度优先搜索遍历进行。

3 2 例如:求下图中顶点 3 至顶点 5 的一条最短路径。 1 4 7 链队列的状态如下所示: 5 6 8 9 Q.front Q.rear 3 1 2 4 7 5

修改链队列的结点结构及其入队列 和出队列的算法 1) 将链队列的结点改为“双链”结点。即 结点中包含next 和prior两个指针； 3) 修改出队列的操作。出队列时，仅移动队头指针，而不将队头结点从链表中删除。

typedef DuLinkList QueuePtr; void InitQueue(LinkQueue& Q) { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front->next = Q.rear->next = NULL } void EnQueue( LinkQueue& Q, QelemType e ) { p = (QueuePtr) malloc (sizeof(QNode)); p->data = e; p->next = NULL; p->priou = Q.front Q.rear->next = p; Q.rear = p; void DeQueue( LinkQueue& Q, QelemType& e ) { Q.front = Q.front->next; e = Q.front->data

思考2：对非连通图进行遍历，得到的是什么？ 7.4 图的生成树和生成森林 连通图的生成树：是连通图的一个极小连通子图，它含 有图中全部顶点，但只有n-1条边。 非连通图的生成森林：由若干棵生成树组成，含图中全部 顶点，但构成这些树的边是最少的。 思考1：对连通图进行遍历，得到的是什么？ ——得到的将是一个极小连通子图，即图的生成树！ 由深度优先搜索得到的生成树，称为深度优先搜索生成树。 由广度优先搜索得到的生成树，称为广度优先搜索生成树。 思考2：对非连通图进行遍历，得到的是什么？ —— 得到的将是各连通分量的生成树，即图的生成森林！ 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度优先生成森林

说明：连通图的生成树不唯一 V1 V2 V4 V5 V3 V7 V6 V8 例 深度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 广度优先生成树 说明：连通图的生成树不唯一

说明 所有生成树具有以下共同特点： 一个有n个顶点的连通图的生成树只有n-1条边 在生成树中再加一条边必然形成回路 生成树的顶点个数与图的顶点个数相同（是连通图的极小连通子图） 一个有n个顶点的连通图的生成树只有n-1条边 在生成树中再加一条边必然形成回路 生成树中任意两个顶点间的路径是唯一的 如何判断一个图就是一棵树？ 遍历该图，若遍历序列正好饱含图中全部顶点和n-1边，既是。实现：可以在遍历过程中增加两个计数器（顶点计数器和边计数器，在访问时计数） 如何判断一个图有生成树？（假设不知道图的类型） 一个图有生成树，在遍历时，必经过n-1边 。 思想同上 V1 V2 V4 V5 V3 V7 V6 V8 广度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8

说明（续） 生成树的权：对连通网络来说，边附上权，生成树也带权，我们把生成树各边的权值总和称为生成树的权。 从不同顶点出发或搜索次序不同，可得到不同的生成树。 生成树的权：对连通网络来说，边附上权，生成树也带权，我们把生成树各边的权值总和称为生成树的权。 最小代价生成树：在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树(MST)。

问题： 假设要在 n 个城市之间建立通信联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通信网？ 7.4 (连通网的)最小生成树 问题： 假设要在 n 个城市之间建立通信联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通信网？ n个城市间，若任意两个城市都有一条通信线路，则最多可设置n(n-1)/2条线路，但实际上仅需n-1条线路，即可实现n个城市相互通信。

7.4 (连通网的)最小生成树 问题演化 问题分析 要在n个城市间建立通信联络网 顶点——表示城市 边的权——城市间建立通信线路所需花费代价 7.4 (连通网的)最小生成树 问题演化 要在n个城市间建立通信联络网 顶点——表示城市 边的权——城市间建立通信线路所需花费代价 问题分析 n个城市间，最多可设置n(n-1)/2条线路 n个城市间建立通信网，只需n-1条线路 如何在可能的线路中选择n-1条， 能把所有城市（顶点）均连起来， 且总耗费（各边权值之和）最小。 1 6 5 4 3 2 7 13 17 9 18 12 24 10

该问题等价于： 在n个顶点的连通网中，构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边(不构成回路)，使“权值之和”为最小。 找最经济通信网 求最小生成树

如何求最小生成树？ 两种方法： Prim算法 Kruskal算法 最小生成树有如下重要性质： 设 N=(V, {E}) 是一连通网，U 是顶点集V的一个非空子集。若（u, v）是一条具有最小权值的边，其中u∈U，v∈V-U，则存在一棵包含边（u, v）的最小生成树。 换而言之：连通网的最小生成树的n-1边中一定包含连通网中代价最小的边。 例如 在1-10 中选择3个数 ，使得这三个数之和 最小 ，则这三个数中必定包含1。

我们用反证法来证明这个MST性质： V-U U v u 假设不存在这样一棵包含边（u , v）的最小生成树。任取一棵最小生成树T，将（u , v）加入T中。根据树的性质，此时T中必形成一个包含（u , v）的回路，且回路中必有一条边 (u’, v’)的权值大于或等于( u, v)的权值。删除（u’, v’)，则得到一棵代价小于等于T的生成树T′，且T′为一棵包含边（u , v）的最小生成树。 这与假设矛盾， 故该性质得证。 V-U v U u

（1）初始状态： U ={u0 },（ u0 ∈V ）， TE= φ, 普里姆（Prim）算法 设：N =（V, E）是个连通网， 另设：U为最小生成树的顶点集，TE为最小生成树的边集。 构造步骤: （1）初始状态： U ={u0 },（ u0 ∈V ）， TE= φ, （2）在uU, vV-U所有的边(u,v)E中，找一条代价最小的边(u0,v0)，并且将边(u0,v0)并入集合TE，同时v0并入U。 （3）重复（2），直到U=V为止。 此时TE中必有n-1条边，T＝(V, {TE}） 就是最小生成树。

Prim’s Algorithm Start with vertex v1. It is the initial current tree which we will grow to an MST 2 v1 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7 A connected, undirected graph G is given above.

Prim’s Algorithm Step 1 Select an edge from graph: that is not in the current tree, that has the minimum cost, and that can be connected to the current tree. Step 1 2 v1 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

The edges that can be connected are: Prim’s Algorithm The edges that can be connected are: (v1,v2): cost 2 (v1,v4): cost 1 (v1,v3): cost 2 Step 1 2 v1 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Prim’s Algorithm Step 1 The edge that has the minimum cost is: (v1,v4): cost 1 (there could be more than one. In that case we could choose of of them randomly) Step 1 2 v1 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Prim’s Algorithm We include the vertex v4, that is connected to the selected edge, to the current tree. In this way we grow the tree. Step 2 2 v1 v1 v2 10 4 1 3 2 7 v3 v4 v4 v5 8 4 6 5 v6 1 v7

Prim’s Algorithm Repeat previous steps: 1, 2 You can add either edge (v1, v2) or (v1, v3). Do a random tie-break. Lets add edge (v1, v2) 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v4 v4 v5 8 4 6 5 v6 1 v7

Prim’s Algorithm Current tree grows! 2 v1 v1 v2 v2 4 1 3 10 2 v3 v4 v4 7 v5 8 4 6 5 v6 1 v7

Prim’s Algorithm Repeat steps: 1, and 2 Add either edge (v4, v3) 2 v1 10 4 1 3 2 7 v3 v3 v4 v4 v5 8 4 6 5 v6 1 v7

Prim’s Algorithm Grow the tree! 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 v4 6 5 8 v6 1 v7

Prim’s Algorithm Add edge (v4, v7) 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 6 5 8 v6 1 v7 v7

Prim’s Algorithm Grow the tree! 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 v4 6 5 8 v6 1 v7 v7

Prim’s Algorithm Add edge (v7, v6) 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 5 8 v6 v6 1 v7 v7

Prim’s Algorithm Grow the tree! 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 v4 8 4 6 5 v6 v6 1 v7 v7

Prim’s Algorithm Add edge (v7, v5) 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 8 4 6 5 v6 v6 1 v7 v7

Prim’s Algorithm Grow the tree! 2 v1 v1 v2 v2 10 4 1 3 2 7 v3 v3 v4 v4 8 4 6 5 v6 v6 1 v7 v7

The resulting MST is shown below! Prim’s Algorithm Finished! The resulting MST is shown below! 2 v1 v1 v2 v2 1 2 v3 v3 v4 v4 v5 v5 4 6 v6 v6 1 v7 v7

u从U（u1~un）中挑选，选择U中到顶点vi边的权值最小的顶点 如何实现Prim（普里姆）算法？ 假设采用邻接矩阵作为图的存储表示。 设计思路： ① 增设一辅助数组closedge[ n ]，以记录从U到V-U具有最小代价的边， 每个数组分量都有两个域： closedge[ i] adjvex lowcost u与vi之间对应的边权 V-U中顶点vi vi 在U中的邻接点u （u，vi） 要求：使closedge[ i].lowcost = min( ( u ,vi ) ) u  U struct { VertexType adjvex; // u在U集中的顶点序号 VRType lowcost; // 边的权值 } closedge[MAX_VERTEX_NUM]; u从U（u1~un）中挑选，选择U中到顶点vi边的权值最小的顶点

具体示例： 有关程序参见：① 严蔚敏，教材P175 ②李春葆，数据结构习题与解析（C语言篇），P271-272 V-U U 6 5 4 3 adjvex lowcost V-U U 6 5 4 3 2 v closedge 2 3 4 5 6 具体示例： 起点 16 11 15 1∞ {2,3,4,5,6} 1 4 2 3 5 6 {1} 1 35 15 36 34 {2, 4, 5, 6} {1, 3} 4 35 62 36 {1,3,6} {2, 4,5} 2 35 36 {1,3, 6,4} {2, 5} 5 1 2 3 4 5 6 23 {1,3,6,4,2} {5} 3 {1,3,6,4,2,5} {} 有关程序参见：① 严蔚敏，教材P175 ②李春葆，数据结构习题与解析（C语言篇），P271-272

算法流程 k=locateVex(G,u); 初始化过程 for(j=0; j<G.vexnum;++j) i<=G.vexnum k=locateVex(G,u); for(j=0; j<G.vexnum;++j) if(j!=k) closedge[j] ={u, G.arcs[k,j].adj; closedge[k].lowcost=0; k=minmum(closedge); End N printf(closedge[k].adjvex,G.vexs(k)); j<G.vexnum G.arcs[k,j].adj< closedge[j].lowcost closedge[j] ={G.vexs[k],G.arcs[k,j].adj}; ++j; ++i; Y 初始化过程 求出权值最小的边(u,vk) 重新求V-U中每个 顶点的closedge[ ]； closedge[j]是V-U到U中所有边中权值最小的边的权值，当U中加入k后，只须在两者之间选较小者作为closedge[ ]

void MiniSpanTree_P(MGraph G, VertexType u) Prim（普里姆）算法描述 void MiniSpanTree_P(MGraph G, VertexType u) { //用普里姆算法从顶点u出发构造网G的最小生成树T,输出T的各条边 k = LocateVex ( G, u ); //找顶点u在图中的位置k for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 if (j!=k) //u到各顶点的权值 {adjvex，lowcost} （u, vj） closedge[j] = { u, G.arcs[k][j].adj }; closedge[k].lowcost = 0; // 初始，U＝{u}，即将u并入U for (i=1; i<G.vexnum; ++i) //以其边权值大小，选择其余顶点并入 { } }// MiniSpanTree_P 继续向生成树上添加顶点;//即查找下一条最小权值边（u，vi） ， //把该边所依附的另一个顶点vi加入到U中。

k = minimum(closedge); // 求出加入生成树的下一个顶点(k) printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树上一条边（u，vk），其中G.vexs是顶点向量 closedge[k].lowcost = 0; // 把第k个顶点并入U集 for (j=0; j<G.vexnum; ++j) // 新顶点并入U后，（可能）需要修改U中原顶点到V-U中其它顶点的最小边 //为第k个顶点到V-U中其它顶点的最小边 if (G.arcs[k][j].adj < closedge[j].lowcost) closedge[j] = { G.vexs[k], G.arcs[k][j].adj }; typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型, //对无权图， 用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell , AdjMatrix[ MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { 　　　　　　　// 图的定义 　 VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息 　　　AdjMatrix arcs; 　　　　　　　　// 表示顶点之间关系的二维数组 　　　int vexnum, arcnum; 　　　　　 // 图的当前顶点数和弧(边)数 　　 GraphKind kind; 　　　　　　 // 图的种类标志 　　} MGraph

克鲁斯卡尔(Kruskal)算法 算法思想：设连通网N=(V,E)，令最小生成树 初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量 在E中选取代价最小的边，若该边依附的顶点落在T中两个不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边 依此类推,直至T中所有顶点都在同一个连通分量上为止 例 1 6 5 4 3 2 1 6 5 4 3 2 1 6 5 4 3 2 1 5 3 2 4

例如: 19 19 a a b b 5 5 12 12 14 14 c c 7 7 18 18 e e 16 16 8 8 3 3 g g d d 27 21 21 f f

Initial Forest 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Step 1 Initial Forest Candidate edges are shown (edges that have low cost and edges that connect two trees) Step 1 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Step 2 Initial Forest Accept one of the candidate edges: (v1, v4) (we can do random accept here). 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Step 3 Initial Forest Merge the two trees connected by that edge. Obtain a new tree in this way. 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Repeat previous steps! Edge (v6-v7) is accepted. 2 v1 v2 10 4 1 3 2 7 8 4 6 5 v6 1 v7

Merge the two trees connected by that edge! 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Accept edge (v1, v2) 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Merge the two trees connected by that edge! 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Accept edge (v3, v4) 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Merge the two trees connected by that edge! 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Accept edge (v4, v7) 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Merge the two trees connected by that edge! 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Accept edge (v7, v5) 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

Merge the two trees connected by that edge! 2 v1 v2 10 4 1 3 2 7 v3 v4 v5 8 4 6 5 v6 1 v7

The resulting MST is shown below! Finished! The resulting MST is shown below! 2 v1 v2 1 2 v3 v4 v5 4 6 v6 1 v7

如何实现Kruskal算法？ 设计思路： 特点：将边归并——适于求稀疏网的最小生成树。 故采用邻接表作为图的存储表示。 ① 设每条边对应的结构类型为： Lchild vi vj weight Rchild 初态：按权值排序(以堆排序为佳，堆顶即为权值最小的边） ② 取堆顶元素，加入到对应最小生成树的新邻接表中（初始为空），从堆中删除它并重新排序堆，每次耗时log2(e)； ③ 重复上一步，注意每次加入时要判断是否“多余”（即是否已被新表中的连通分量包含）； ④ 直到堆空。 显然， Kruskal算法的时间效率＝O（elog2e）

算法描述: { 构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数, void MiniSpanTree_Kruskal(ELGraph G, SqList& ST) { 构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数, while (k<G.Arcnum) { ++i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路（即，判断u，v是否在 同一个连通分量（集合））， 则 输出边(u,v); 且 k++; // flags[G.Vexnum], flags[u], flags[v]=1? }//while }//

若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。 *7.5 重连通图和关节点 应用实例 可靠的通讯系统一般都有两条以上的通信线路，若某一线路出现故障，可使用其他线路，保证系统仍能正常工作。 问题理论：重（双）连通图 若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。

如何判别给定的连通图是否是双连通图？ 若连通图中的某个顶点和其相关 联的边被删去之后，该连通图被分割 成两个或两个以上的连通分量，则称 此顶点为关节点。 没有关节点的连通图为双连通图。

例如:下列连通图中 深度优先生成树 1 a h g c b f d e a 1 7 2 b g 1 1 8 3 c h 1 1 4 6 d 5 e 3 顶点 a 和顶点 c 是关节点

假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。 关节点有何特征？ 需借助图的深度优先生成树来分析。 假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。

若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点； 对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。

图的应用 有两种常用的活动网络（Activity Network）： ① AOV网(Activity On Vertices)—用顶点表示活动的网络 AOV网定义:若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系。若图中存在有向边<vi,vj>，则Vi 必须先于活动Vj 进行，则这样的有向图称为用顶点表示活动的网络,简称 AOV网。 ② AOE网(Activity On Edges)—用边表示活动的网络 AOE网定义：如果在无环的带权有向图中，用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称 AOE网。 一个无环的有向图称作有向无环图，简称DAG图，它在工程计划和管理方面有着广泛而重要的应用。除最简单的情况之外，几乎所有的工程(project)都可分为若干个称作"活动"的子工程，并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才能开始。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。本节和下一节将分别讨论这两个算法。 　  一项工程往往可以分解为一些具有相对独立性的子工程，通常称这些子工程为"活动"。子工程之间在进行的时间上有着一定的相互制约关系，例如，盖大楼的第一步是打地基，而房屋的内装修必须在房子盖好之后才能开始进行等。可用一个有向图表示子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络，或AOV(Activity On Vertex)网。

7.6 拓扑排序---AOV网的应用 问题提出：教学计划的制定--学生选修课程安排问题: 定义 顶 点—表示课程 顶 点—表示课程 有向弧—表示先决条件，若课程Vi是课程Vj的先决 （先修）条件，则图中有弧<vi, vj> 。 定义 AOV网—用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网，简称AOV网。 若<vi, vj>是图中有向边，则vi是vj的直接前趋；vj是vi的直接后继。活动Vi 必须先于活动Vj 进行。 AOV网中不允许有回路，否则就意味着某项活动以自己为先决条件。 一个无环的有向图称作有向无环图，简称DAG图，它在工程计划和管理方面有着广泛而重要的应用。除最简单的情况之外，几乎所有的工程(project)都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才能开始。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。本节和下一节将分别讨论这两个算法。 　    　　一项工程往往可以分解为一些具有相对独立性的子工程，通常称这些子工程为“活动”。子工程之间在进行的时间上有着一定的相互制约关系，例如，盖大楼的第一步是打地基，而房屋的内装修必须在房子盖好之后才能开始进行等。可用一个有向图表示子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络，或AOV(Activity On Vertex)网。 拓扑排序应用：输入几个字母 和表达式，试确定它们之间的大小关系，如　　ＡＣＭ赛选 输入： 4，6 A<B A<C B<C, B<D, C<D, A<D 输出： A　B　C　D

拓扑排序的方法： 拓扑排序—把AOV网中各顶点（按照它们相互之间的优先关系）排列成一个线性序列的过程称为拓扑排序。步骤： 从图中删除该顶点和所有以它为尾的弧; 重复以上 1、2 步, 直到： 图中全部顶点均已输出，则拓扑排序完成；或者： 图中还有未输出的顶点，但它们都有直接前趋，再也找不到没有直接前趋的顶点了。这时AOV网络中必定存在有向环。 拓扑排序算法：重复选择没有直接前趋（入度为0）的顶点并输出。

拓扑排序实例—课程安排 课程代号 课程名称 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 课程代号 课程名称 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1,C2 C3,C4 C3.C5 C3,C6 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 拓扑排序实例—课程安排 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

注：一个AOV网的拓扑序列不是唯一的 拓扑排序的方法 在有向图中选一个没有直接前趋的顶点并输出 在有向图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前趋的顶点为止 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8 或 ：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 注：一个AOV网的拓扑序列不是唯一的

C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1 （1） C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2 （2）

C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3 （3） C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4 （4）

C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5 （5） C6 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7 （6） C6 C8 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10 （8） C6 C8 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9

C6 C8 C12 拓扑序列： C1--C2--C3--C4--C5--C7--C9--C10--C11 （9） C8 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6 （10） C8 拓扑序列： C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6--C12 （11） 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6--C12--C8 （12）

不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D} 拓扑排序检测AOV网中是否存在环的方法： 对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。 例如：下列有向图 B A D C 不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D}

拓扑排序的算法实现 没有前趋的顶点  入度为零的顶点 删除顶点及以它为尾的弧  弧头顶点的入度减1 拓扑排序的方法 C6 C9 C10 C11 C12 拓扑排序的方法 在有向图中选一个没有前趋的顶点并输出之 从有向图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前趋的顶点为止 在算法中需要用定量的描述替代定性的概念 没有前趋的顶点  入度为零的顶点 在计算机中实现此算法时，需以“入度为零”作为“没有前趋”的量度，而“删除顶点及以它为尾的弧”的这类操作可不必真正对图的存储结构来进行，可用“弧头顶点的入度减1”的办法来替代。并且为了便于查询入度为零的顶点，在算法中可附设“栈”保存当前出现的入度为零的顶点。 由于拓扑排序中对图的主要操作是"找从顶点出发的弧"，并且AOV网多数情况下是稀疏图，因此存储结构取邻接表为宜。 删除顶点及以它为尾的弧  弧头顶点的入度减1 宜以邻接表作存储结构 为便于顶点的入度减1，应增加一个 存放顶点入度的数组indegree[n]。

为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。 拓扑排序的算法实现（续） 为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。 算法实现 求各顶点的入度indegree[0… vexnum-1] 初始化栈 把邻接表中所有入度为0的顶点进栈。 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈。 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。

int TopologicalSort(ALGraph G) { // CountInDegree(G,indegree); //对各顶点求入度，也可在存储结构中增加入度分量in InitStack(S); for ( i=0; i<G.vexnum; ++i) if (!indegree[i]) Push(S, i); //入度为零的顶点入栈 count=0; //对输出顶点计数 while (!EmptyStack(S)) { Pop(S, i); printf(i,G.vertices[i].data); ++count; //输出i号顶点并计数 for (p=G.vertices[i].firstarc; p; p=p->nextarc) { k=p->adjvex; //求 i号顶点的各个邻接点数组中的位序k --indegree[k]; // 对i号顶点的各个邻接点入度减1 if (!indegree[k]) Push(S, k); //新产生的入度为零的顶点入栈 }//for }//while if (count<G.vexnum) printf(“图中有回路”) } // TopologicalSort

算法演示示例 1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 3 2 1 4 top top 6 1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 3 2 1 4 top top 6 top 1

1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 3 2 1 4 6 top top 输出序列：6

1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 p 3 2 1 4 top 输出序列：6

1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 p 3 2 1 4 top 输出序列：6

1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 p 3 2 1 4 top 输出序列：6

1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 p 3 2 1 4 top 输出序列：6

1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 p=NULL 3 2 1 4 top 输出序列：6

1 2 in link 5 4 3 ^ vex next 6 3 2 1 4 top top 输出序列：6 1

1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 输出序列：6 1

1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 4 输出序列：6 1

1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 4 输出序列：6 1

1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 4 输出序列：6 1

2 in link 5 4 3 ^ vex next 1 6 p 3 2 1 4 top 3 4 输出序列：6 1

2 in link 5 4 3 ^ vex next 1 6 p 3 2 1 4 top 3 4 输出序列：6 1

2 in link 5 4 3 ^ vex next 1 6 p 3 2 1 4 top 3 4 输出序列：6 1

1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 3 4 输出序列：6 1

1 in link 5 4 3 ^ vex next 2 6 p=NULL 3 2 1 4 top 3 4 输出序列：6 1

1 in link 5 4 3 ^ vex next 2 6 3 2 1 4 top 3 4 输出序列：6 1 3

1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 4 输出序列：6 1 3

1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 4 输出序列：6 1 3

1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 4 输出序列：6 1 3

in link 5 4 3 ^ vex next 1 2 6 p 3 2 1 4 top 2 4 输出序列：6 1 3

in link 5 4 3 ^ vex next 1 2 6 p 3 2 1 4 top 2 4 输出序列：6 1 3

in link 5 4 3 ^ vex next 1 2 6 p=NULL 3 2 1 4 top 2 4 输出序列：6 1 3

in link 5 4 3 ^ vex next 1 2 6 p=NULL 3 2 1 4 top 2 4 输出序列：6 1 3 2

in link 5 4 3 ^ vex next 1 2 6 p=NULL 3 2 1 4 top 4 输出序列：6 1 3 2

in link 5 4 3 ^ vex next 1 2 6 3 2 1 4 top 4 输出序列：6 1 3 2 4

in link 5 4 3 ^ vex next 1 2 6 p 3 2 1 4 top 输出序列：6 1 3 2 4

in link 5 4 3 ^ vex next 2 1 6 p 3 2 1 4 top 5 输出序列：6 1 3 2 4

in link 5 4 3 ^ vex next 2 1 6 p=NULL 3 2 1 4 top 5 输出序列：6 1 3 2 4

in link 5 4 3 ^ vex next 2 1 6 3 2 1 4 top 5 输出序列：6 1 3 2 4 5

in link 5 4 3 ^ vex next 2 1 6 p=NULL 3 2 1 4 top 输出序列：6 1 3 2 4 5

算法分析 求顶点的入度 ：T(n)=O(e) 入度为0的顶点进栈：T(n)=O(n) 拓扑排序：T(n)=O(n+e)

*7.7 关键路径 --AOE网的应用 AOE网--用边表示活动的网(Activity On Edges) AOE网：如果在带权的有向无环图中，用有向边表示一个工程中的活动 (Activity)，用边上权值表示活动持续时间 (Duration)，用顶点表示事件 (Event)，则这样的有向图叫做用边表示活动的网，简称 AOE网( Activity On Edges ) 。 AOE网在某些工程进度估算方面非常有用。利用它可以解决以下两个问题： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2)为缩短完成工程所需的时间, 应当加快哪些活动? 或者说，哪些活动是影响工程进度的关键？

实例 ： 设一个工程有11项活动，9个事件 事件V1（源点）——表示整个工程开始 事件V9（汇点）——表示整个工程结束 有向边（弧）---表示活动 弧的权值------表示该活动持续时间 每个事件表示在它之前的活动已经结束，在它之后的活动可以开始。 一项工程常需要解决的问题： （1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？ 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4

*7.7 关键路径 --几点说明 在AOE网络中, 有些活动顺序进行，有些活动并行进行。 *7.7 关键路径 --几点说明 在AOE网络中, 有些活动顺序进行，有些活动并行进行。 从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度（活动持续时间之和，而非弧数目）也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。 因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。关键路径上的所有活动都是关键活动，因此要找关键路径，必须先找出各个关键活动。 上图的AOE网从V1到V9的最长路径长度为18，它告诉人们该项工程从开始到完成需要18天，其中a1，a4，a8和a11这四项子工程必须按时开始并计划完成，否则将延误整个工程的工期，即使整个工程不能在18天内完成。称a1，a4，a8和a11为此AOE网的关键活动，称由它们构成的路径{a1,a4,a8,a11}为关键路径。 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4

定义几个与计算关键活动有关的量： ① 事件Vi 的最早可能开始时间Ve(i) 是从源点V1 到顶点Vi 的最长路径长度。 如V5 ② 事件Vi 的最迟允许开始时间Vl [i] 是在保证汇点Vn 在Ve[n] 时刻完成的前提下，事件Vi 的允许的最迟开始时间。 Eg. V6 ：VL[6]=10 （V8:14 ）可以提前3 ③ 活动ak 的最早可能开始时间 e[k] eg。a5 设活动ak 在边< Vi , Vj >上, 则e[k]是从源点V1到顶点Vi 的最长路径长度。因此, 有： e[k] = Ve[i]。 ④ 活动ak 的最迟允许开始时间L [k]， 假设ak 在边< Vi , Vj >上 L [k]是在不会引起时间延误的前提下, 该活动允许的最迟开始时间。 L [k] = V l [j] - dut(<i, j>)。 eg。a5 其中, dut(<i, j>)是完成 ak 所需的时间。 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4

表示活动 ak 的最早可能开始时间和最迟允许开始时间的时间余量。L[k] == e[k] 表示活动 ak 是没有时间余量的关键活动。 为找出关键活动, 需要求各个活动的 e[k] 与 L[k]，以判别是否L[k] == e[k]。

问题分析 如何找e(k)=l(k)的关键活动ai？ 如何求Ve(j)和Vl(j)？ 设活动ak用弧<i,j>表示，其持续时间记为：dut(<i,j>)，由上述定义 则有：（1）e(k)=Ve(i) （2）l(k)=Vl(j)-dut(<i,j>) i j ak 如何求Ve(j)和Vl(j)？ j i (1)从Ve(1)=0开始向后递推 (2)从Vl(n)=Ve(n)开始向前递推 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。 为了简化算法, 假定在求关键路径之前已经对各顶点实现了拓扑排序, 并按拓扑有序的顺序对各顶点重新进行了编号。

求关键路径步骤 求Ve(j) 求Vl(j) 求e(i)（=Ve(j)） 求l(i) （（Vl(k)-dut(<j,k>)） 9 8 7 6 4 5 3 2 1 a2=4 a3=5 a5=1 a6=2 a9=4 a1=6 a4=1 a7=9 a8=7 a10=2 a11=4 求关键路径步骤 求Ve(j) 求Vl(j) 求e(i)（=Ve(j)） 求l(i) （（Vl(k)-dut(<j,k>)） 计算l(i)-e(i) （Min{ Vl(k)-dut(<j,k>)） 活动 e l l-e a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11  顶点 Ve Vl 2 V1 V2 V3 V4 V5 V6 V7 V8 V9 6 4 5 7 16 14 18 6 8 7 10 16 14 18 3 j k ai 6 4 6 2 5 8 3 7 7 7 10 3 16 14

求关键路径的算法实现要点: 以邻接表作存储结构，输入e条弧<j,k>,建立AOE网 从源点V1出发,令Ve[1]=0,按拓扑序列求各顶点的Ve[i] 从汇点Vn出发，令Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的Vl[i] 。逆拓扑序列即为拓扑有序序列的逆序列，应该在拓扑排序的过程中， 另设一个“栈”记下拓扑有序序列。 根据各顶点的Ve和Vl值，计算每条弧的e[i]和l[i], 找出e[i]=l[i]的关键活动 解释说明：请同学们打开教材P184 倒数第二段描述 表头结点： typedef struct tnode { int vexdata; int in; //入度域 struct node *link; //链域 }TD; TD g[M]; //g[0]不用 邻接表结点： typedef struct node { int vex; //顶点域 int length; struct node *next; //链域 }JD;

算法描述（略过，详细算法请参考教材P185 7.13&7.14） 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 令Ve[1]=0，在排序过程中求各顶点的Ve[i]， 将得到的拓扑序列进栈T 令Vl[n]=Ve[n],按逆拓扑序列求顶点的Vl[i] 计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动 9 8 7 6 4 5 3 2 1 a2=4 a3=5 a5=1 a6=2 a9=4 a1=6 a4=1 a7=9 a8=7 a10=2 a11=4

9 8 7 6 4 5 3 2 1 a2=4 a3=5 a5=1 a6=2 a9=4 a1=6 a4=1 a7=9 a8=7 a10=2 略 in link vex next vexdata length 1 2 3 4 5 6 7 8 9 ^ 10

7.8 最短路径 典型用途：交通问题。如：城市S到城市D有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使得总费用（或总时间）最少？ 问题抽象：用带权的有向图表示一个交通运输网，图中： 顶点—表示城市 边—表示城市间的交通联系 权—表示此线路的长度或沿此线路运输所用的时间或费用等 在有向图中从S点（源点）到达D点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。 （注：最短路径与最小生成树不同，路径上不一定包含n个顶点。） 两种常见的最短路径问题： 一、 单源点最短路径—用Dijkstra（迪杰斯特拉）算法 二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法 一顶点到其余各顶点 任意两顶点之间

一、单源最短路径 (Dijkstra算法) 设一有向图G=（V, E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于0。 例1： 1 2 3 4 源点 终点 最 短 路 径 路径长度 v v 1 2 3 4 ( v , 1 ) 10 ( v , 1 2 ) ( v , 3 2 ) 60 50 ( v , 3 ) 30 ( v , 4 ) ( v , 3 4 ) ( v , 1 2 4 ) 100 90 70 ( v , 3 2 4 ) 60

对各最短路径按路径长度递增排列 v 源点 终点 1 3 2 4 ( , ) 最 短 路 径 10 路径长度 30 50 60 可以证明从源点V0到某顶点Vk的最短路径，必定或是从V0到Vk的直接路径（仅含一条弧）；或是从V0经中间顶点vi再到Vk的路径，其中中间顶点vi是指已求得的最短路径的顶点或顶点序列。

求从源点到其余各点的最短路径的算法的基本思想: 依最短路径的长度递增的次序求得各条最短路径 v1 其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。 v2 … 源点

图中路径长度最短的最短路径的特点： 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长度次短的最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。 依此类推，其余最短路径的特点： 它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。

迪杰斯特拉(Dijkstra)算法思想 把图的顶点集V分成两组： 按路径长度递增次序产生最短路径的算法： S：已求出最短路径的顶点的集合 V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中，并保证： 从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 设置辅助数组Dist[n]，其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径长度。 其初始值为： V0和k之间存在弧 V0和k之间不存在弧

求最短路径步骤： 算法的C语言程序见教材P189； （1）设A[n][n]为有向网的带权邻接矩阵，A[i][j]表示弧（vi，vj )的权值，S为已找到从源点v0出发的最短路径的终点集合，它的初始状态为{ v0 }。辅助数组Dist[n]为各终点当前找到的最短路径的长度，它的初始值为： Dist[i]＝A[v0,vi]，i=1…n （2）选择vj，使得 Dist[j]＝min{Dist[i] | vi∈V-S } // vi是S集之外的顶点 // vj就是当前求得的一条从源点v0到S集外所有顶点中最短路径的终点。 并令：S= S ∪{vj} //将vj加入S集 （3）修改从v0出发到V-S上任一顶点（未确定的终点vk）的最短 路径长度，若 Dist[j]+ A[j,k]< Dist[k] // 即(v0,vj)＋(vj,vk)<(v0,vk) 则修改Dist[k]为：Dist[k]＝Dist[j]+ A[j,k] //由于vj的加入， //使v0到vk的最短距离变小 （4）重复操作（2）、（3）共n-1次（S=V），由此求得从v0到各终点的最短路径。

Zhengjin,Central South University //选择d 值最小的节点u Zhengjin,Central South University 224

Zhengjin,Central South University 225

Zhengjin,Central South University 226

Zhengjin,Central South University 227

Zhengjin,Central South University 228

Zhengjin,Central South University 229

Zhengjin,Central South University 230

Zhengjin,Central South University 231

Zhengjin,Central South University 232

Zhengjin,Central South University 233

Zhengjin,Central South University 234

Zhengjin,Central South University 235

二、每一对顶点之间的最短路径 （算法设计与分析课程中会讲） 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n³) 方法二：弗洛伊德(Floyd)算法(动态规划方法） 算法思想：逐个顶点试探法(vi,vj) 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为 逐步试着在原直接路径中增加中间顶点（依次为v0,v1,…），若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束

求每一对顶点之间的最短路径的示例： 例 A C B 2 6 4 3 11 0 4 11 6 0 2 3  0 初始： 路径： AB AC 0 4 11 6 0 2 3  0 初始： 路径： AB AC BA BC CA 0 4 11 6 0 2 3 7 0 加入A： 路径： AB AC BA BC CA CAB 0 4 6 6 0 2 3 7 0 加入B： 路径： AB ABC BA BC CA CAB 0 4 6 5 0 2 3 7 0 加入C： 路径： AB ABC BCA BC CA CAB

算法分析：T(n)=O(n³) 算法实现 算法描述 图用邻接矩阵存储 length[][]存放最短路径长度 path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号 算法描述 初始： 0 4 11 6 0 2 3  0 length= 0 1 1 2 0 2 3 0 0 path= 例 1 3 2 6 4 11 加入V1： 0 4 11 6 0 2 3 7 0 length= 0 1 1 2 0 2 3 1 0 path= 加入V2： 0 4 6 6 0 2 3 7 0 length= 0 1 2 2 0 2 3 1 0 path= 加入V3： 0 4 6 5 0 2 3 7 0 length= 0 1 2 3 0 2 3 1 0 path= 算法分析：T(n)=O(n³)

本章作业 P47 基础题： 算法设计题： 课外作业： 7.1 7.7 7.10 7.11 (7.13) 7.22 7.27 7.1 7.7 7.10 7.11 (7.13) 算法设计题： 7.22 7.27 课外作业： 7.3 7.9 7.14 7.23 7.24 7.25 7.28 7.36

本章小结-体系结构图 图 Dijkstra算法 Floyd算法 最短路径 拓扑排序 关键路径 邻接矩阵 邻 接 表 十字链表 AOV网,AOE网 拓扑排序 关键路径 邻接矩阵 邻 接 表 十字链表 有向(无环)图的应用 存储结构 图 应用 深度优先搜索DFS 广度优先搜索DFS 无向图的应用 遍 历 图的连通分量 图的生成树 （利用DFS） Prim算法 Kruskal算法 最小生成树 (利用DFS和BFS)

1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 本章小结 （续） 　1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 　2. 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 3. 理解求最小生成树算法、求最短路径算法。