第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用

Presentation on theme: "第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用"— Presentation transcript:

1 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

2 本章重点难点 重点：(1)图的定义、术语和性质；(2)ADT图的设计和实现；(3)图的邻接矩阵、邻接表的存储结构及其构造方法；(4)图的两种遍历方法：深度优先遍历和广度优先遍历；(5)最小生成树的算法、拓扑排序的算法；(6)理解关键路径的算法，构造最短路径的Dijkstra算法和Floyed算法。 难点：有向无环图的关键路径算法，求最短路径的Dijkstra算法和Floyed算法。

3 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

4 7.1 图的定义和术语 图的定义 例 G1=<V1,E1> V1={v0 ,v1,v2,v3,v4 }
图G由两个集合构成，记作G=<V,E> 其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。 例 G1图示 V0 V4 V3 V1 V2 G1=<V1,E1> V1={v0 ,v1,v2,v3,v4 } E1={ (v0,v1),(v0,v3),(v1,v2), (v1,v4),(v2,v3)(v2,v4) }

5 7.1 图的定义和术语 图的术语 无向图(Undigraph) ：在图G中，若所有边是无向边，则称G为无向图；
有向图(Digraph) ：在图G中，若所有边是有向边，则称G为有向图；有向边也称为弧(Arc)。 V0 V1 V0 V1 V2 V3 V4 V2 V3 G1图示 无向图 有向图 G2 图示

6 7.1 图的定义和术语 图的术语 无向完全图(Undirected Complete Graph)： 无向图且边数为n(n-1)/2，则称其为无向完全图； 有向完全图(Directed Complete Graph)： 有向图且边数为n(n-1) ，则称其为有向完全图 邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关连边e

7 7.1 图的定义和术语 图的术语 顶点的度： 一个顶点v的度是与它相关联的边的条数，记作D(v)。 顶点v的入度是以v为终点的有向边的条数, 记作ID(v); 顶点v的出度是以v为始点的有向边的条数,记作 OD(v)。 顶点数、边数e和度数D（v）之间的关系：

8 7.1 图的定义和术语 图的术语 路径、回路: 有向图D=（V，E）中的顶点序列v1,v2,… ,vk, 若<vi,vi+1>E (i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路； 路径、回路:无向图G=（V，E）中的顶点序列v1,v2,… ,vk,若(vi,vi+1)E( i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；

9 7.1 图的定义和术语 例 在图1中，V0,V1,V2,V3 是V0到V3的路径；V0,V1,V2,V3,V0是回路；
无向图G1 有向图G2

10 7.1 图的定义和术语 图的术语 简单路径和简单回路: 在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径；由简单路径组成的回路称为简单回路；

11 7.1 图的定义和术语 例 在图1中，V0,V1,V2,V3 是简单路径； V0,V1,V2,V4,V1不是简单路径。
无向图G1 有向图G2

12 7.1 图的定义和术语 图的术语 连通图（强连通图）: 在无(有)向图G=< V, E >中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）

13 7.1 图的定义和术语 图的术语 子图: 设有两个图G=（V，E）、G1=（V1，E1），若V1 V，E1  E，E1关联的顶点都在V1中，则称 G1是G的子图； 权: 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。

14 7.1 图的定义和术语 图的术语 生成树:连通图的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G 的生成树。 T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路

15 见下页 7.1 图的定义和术语 图的抽象数据类型定义 ADT Graph { 数据对象V： V是具有相同特征的数据元素的 集合,称为顶点集。
基本操作 } ADT Graph V是具有相同特征的数据元素的 集合,称为顶点集。 R={VR} VR={<v,w>︱v,w∈V且P(v,w) 见下页

16 7.1 图的定义和术语 基本操作 CreatGraph(&G) //建立图 DestroyGraph(&G) //销毁图 InsertVEx(&G, v) //插入顶点 DeleteVEx(&G, v) //删除顶点 InsertArc(&G, v, w) //插入弧 DeleteArc(&G, v, w) //删除弧 DFSTraVErse(G, v, Visit()) //深度优先搜索 BFSTraVErse(G, v, Visit()) //广度优先搜索

17 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

18 7.2 图的存储结构 7.2.1、数组表示法 7.2.2、邻接表

19 ？ 7.2 图的存储结构 图的存储结构至少要保存两类信息： (1)顶点的数据 (2)顶点间的关系 如何表示顶点间的关系？ 约定:
图G=<V, E>, V={v0,v1,v2, … vn-1 },顶 点的角标为它的编号。

20 7.2.1 数组表示法 邻接矩阵 (Adjacency Matrix) G的邻接矩阵是满足如下条件的n阶矩阵： 1 若(vi,vi+1)E 或 <vi,vi+1>E 0 否则 A[i][j]=

21 7.2.1 数组表示法 例 无向图的邻接矩阵 V0 V1 V2 V3 讨论： (1)无向图中第i个顶点的度在邻接矩阵中如何体现？ (2)图的总度数怎么求, (3)边数怎么求?

22 7.2.1 数组表示法 例 无向图的邻接矩阵 V0 V1 V2 V3 答案： (1)第i行(或第i列)的非零元素个数之和； (2)非零元个数之和； (3)边数为总度数的一半。

23 7.2.1 数组表示法 例 有向图的邻接矩阵 1 2 3 4 v0 v1 v4 v3 v2 讨论： 有向图中第i个顶点的出度和入度在邻接矩阵中如何体现？ 边数是多少？

24 7.2.1 数组表示法 例 有向图的邻接矩阵 1 2 3 4 v0 v1 v4 v3 v2 答案： 第i行的非零元个数之和； 第i列的非零元个数之和； 边数为非零元的个数。

25 7.2.1 数组表示法 网络的邻接矩阵 网络的邻接矩阵是满足如下条件的n阶矩阵： Wij 若(vi,vi+1)E 或 <vi,vi+1>E 0 或 否则 A[i][j]=

26 7.2.1 数组表示法 例 边带权图(网)的邻接矩阵示例： 2 v0 v1 2 ∞ ∞ ∞ ∞ 1 2 3 4 ∞ ∞ ∞ ∞ 4 v4 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 2 ∞ ∞ ∞ ∞ 2 v3 v2 2 讨论：无穷大在实际应用中怎么表示？ 答案：用一个足够大的数表示。

27 7.2.1 数组表示法 邻接矩阵的类型实现 #define INFINITY INT_MAX //最大值 #define MAX_VERTEX_NUM //最大顶点个数 Typedef enum {DG,DN,UDG,UDN} GraphKind; typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

28 7.2.1 数组表示法 图的类型实现 typedef struct { // 图的类型定义 VErtexType // 顶点信息 vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; // 弧的信息 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 } MGraph; MGraph G;

29 7.2.1 数组表示法 例 网的存储示例图 2 5 20 40 70 1 4 50 30 80 6 3

30 7.2.1 数组表示法 建立无向网络(边带权图)G的算法概要： 首先读入顶点数G.VExnum，边数G.arcnum，图的种类G.kind 1、给顶点域赋值：G.vexs[i]; 2、给边域赋值： ① 边域初始化：G.arcs[i][j].adj=INFINITY; ② 读入边及权重i,j,w, G.arcs[i][j].adj=W; G.arcs[j][i].adj=W。

31 见下页 7.2.1 数组表示法 建立无向网络(边带权图)G的算法详解： void Creatgraph(MGraph &G)
{int i,j,k;float w; scanf(“%d,%d,%d”,G.VExnum,G.arcnum,G.kind); for(i=1;i<=G.VExnum;i++) G.VExs[i]=getchar(); 见下页

32 接上页 7.2.1 数组表示法 for(i=1;i<=G.VExnum;i++)
for(j=1;j<=G.VExnum;j++) G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; for (k=1;k<=G.arcnum;k++) {scanf(“%d,%d,%f”,&i,&j,&w); G.arcs[i][j]=w; G.arcs[j][i]=w; }

33 7.2.1 数组表示法 邻接矩阵的特点 (1)空间复杂度O(n2) (2)操作特点 边或弧的删除和插入操作容易。顶点的插入删除操作不容易。

34 讨论：如何求无向图邻接表中第i个顶点的度？图的总度数,边数?
7.2.2 邻接表 例 无向图的邻接表示例： V0 V1 顶点表 边表 V2 V3 1 2 3 4 v1 v2 v3 v4 讨论：如何求无向图邻接表中第i个顶点的度？图的总度数,边数? 2 3 4 ^ 1 4 ^ 1 4 ^ 1 2 3 ^

35 讨论：如何求无向图邻接表中第i个顶点的度？ 图的总度数？ 边数?
7.2.2 邻接表 例 无向图的邻接表示例： V0 V1 V2 V3 讨论：如何求无向图邻接表中第i个顶点的度？ 图的总度数？ 边数? 答案：第i个顶点的边链表结点个数之和。 所有边链表结点个数之和。 所有边链表结点个数之和的一半。

36 讨论：求有向图邻接表中第i个顶点的出度？图的边数?
7.2.2 邻接表 例 有向图的邻接表示例： v2 v1 顶点表 出边表 v3 v1 v2 v3 v4 v5 v5 v4 2 ^ 1 5 ^ 讨论：求有向图邻接表中第i个顶点的出度？图的边数? 2 4 ^ 1 ^ 4 ^

37 7.2.2 邻接表 例 有向图的邻接表示例： v2 v1 v3 v5 v4 讨论：求有向图邻接表中第i个顶点的出度？图的边数? 答案：第i个顶点的边链表结点个数之和。 所有边链表结点个数之和。

38 边链表：与顶点V关联的所有边组成一个链表，称为顶点V的边链表。在边链表中，其结点结构如下：
7.2.2 邻接表 邻接表的定义 边链表： 顶点表： 邻接表的定义分两部分： 边链表：与顶点V关联的所有边组成一个链表，称为顶点V的边链表。在边链表中，其结点结构如下： adjvex nextarc info 表结点

39 顶点表：用顺序存储方式存储图的顶点表v1,v2,v3,…vn，每个顶点的结构。
7.2.2 邻接表 邻接表的定义 顶点表：用顺序存储方式存储图的顶点表v1,v2,v3,…vn，每个顶点的结构。 data info firstarc 邻接表：由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表。

40 7.2.2 邻接表 邻接表的存储实现 #define MAX_VERTEX_NUM 20 (1)边表的存储类型： typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 该弧相关信息的指针 } ArcNode;

41 7.2.2 邻接表 邻接表的存储实现 (2)顶点表的存储类型： typedef struct vnode { vertextype data; // 顶点信息 Arcnode *firstarc; // 指向第一条依附该顶点的弧 } vnode, adjlist[MAX_VERTEX_NUM];

42 (3)图的邻接表存储类型： 7.2.2 邻接表 邻接表的存储实现 typedef struct { adjlist vertices;
int vexnum, arcnum; int kind; // 图的种类标志 } ALGraph; ALGraph G;

43 7.2.2 邻接表 建立无向图G的邻接表的算法概要： (1)、给顶点表中顶点域赋值，指针域赋值 G.VErtices[i].data=getchar(); G.VErtices[i].firstarc=NULL; (2)、读入边的邻接顶点编号i,j： ① 生成结点s; 前插法建表；s->nextarc= G.VErtices[i].firstarc; G.VErtices[i].firstarc=s; ②生成结点s; 前插法建表；…………. 3、重复第二步。

44 见下页 7.2.2 邻接表 建立无向网络(边带权图)G的算法详解： void Creatadilist(ALGraph &G)
{ int i,j,k;ArcNode *s; scanf(“%d,%d,%d”,G.VExnum,G.arcnum,G.kind); for(i=1;i<=G.VExnode;i++) {G.VErtices[i].data=getchar(); G.VErtices[i].firstarc=NULL;} 见下页 图示

45 接上页 7.2.2 邻接表 建立无向网络(边带权图)G的算法详解： for(k=0;k<G.arcnum;k++)
{scanf(“%d%d”,&i,&j); s=new ArcNode; s->adjVEx=j; s->info=NULL; s->nextarc= G.VErtices[i].firstarc; G.VErtices[i].firstarc=s; …………. } 图示

46 7.2.2 邻接表 邻接表的特点 (1)对于顶点多边少的图采用邻接表存储节省空间；空间复杂度O(n+e)。 (2)容易找到任一顶点的第一个邻接点。

47 7.2.2 邻接表 图的存储结构总结 在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。

48 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

49 7.3 图的遍历 图的遍历是指：从图的某一顶点出发访问图中的所有顶点，且每个顶点仅访问一次。 7.3.1、深度优先搜索 7.3.2、广度优先搜索

50 7.3.1 深度优先搜索 深度优先搜索的示例演示 v1 v2 v7 v6 v3 v9 v8 v5 v4 Visited[9] 1 1 1 1
1 1 1 1 1 1 1 1 1

51 7.3.1 深度优先搜索 算法的基本思想 (1)首先访问图中某一个顶点Vi，以该顶点为出发点； (2)任选一个与顶点Vi邻接的未被访问的顶点Vj；访问Vj; (3)以Vj为新的出发点继续进行深度优先搜索，直至图中所有和Vi有路径的顶点均被访问到。

52 7.3.1 深度优先搜索 深度优先搜索算法概要 从某点v(设v为某顶点编号)出发。 步骤: 1、访问v; 2、改变访问标志； 3、任选一个与v相邻又没被访问的顶点w，从w开始继续进行深度优先搜索。

53 7.3.1 深度优先搜索 深度优先搜索算法详解 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)) if (!visited[w]) DFS(G, w); // 对v的尚未访问的邻接顶点w // 递归调用DFS } // DFS

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

55 7.3.1 深度优先搜索 深度优先搜索算法详解(绪) 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 }

56 7.3.1 深度优先搜索 算法分析 假设图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿每个链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。

57 7.3.1 深度优先搜索 深度优先搜索的功能 利用深度优先搜索可以实现以下目标 (1) 求深度优先生成树 (2) 判断图是否连通 (3) 求图的连通分量

58 7.3.2 广度优先搜索 广度优先搜索示例演示 出发点 0 1 2 3 4 5 6 7 8 T T T T T T T T T V0 V1
9 v2 v8 v7 v8 v7 8 v4 v3 6 v4 v3 7 F Visit[v] T T T T T T T T T Q V0 V1 V5 V2 V6 V4 V3 V7 V8 V0 V1 V5 V2 V6 V4 V3 V7 V8

59 7.3.2 广度优先搜索 广度优先搜索的思想 广度优先搜索(Breadth First Search)遍历类似于树的按层次遍历。 (1)首先访问图中某一个指定的出发点vi； (2)然后依次访问vi的所有邻接点vi1,vi2…vit； (3)再依次以vi1,vi2…vit为顶点，访问各顶点未被访问的邻接点，依此类推，直到图中所有顶点均被访问为止。

60 7.3.2 广度优先搜索 广度优先搜索算法详解 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 尚未访问 ………………… } } // BFSTraVErse 见下页

61 接上页 7.3.2 广度优先搜索 广度优先搜索算法详解 EnQueue(Q, v); // v入队列
visited[v] = TRUE; Visit(v); // 访问u 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入队列 }

62 7.3.2 广度优先搜索 算法分析 如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。

63 7.3.2 广度优先搜索 广度优先搜索的功能 利用广度优先搜索可以实现以下目标 (1) 求广度优先生成树 (2) 判断图是否连通 (3) 求图的连通分量

64 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

65 7.4、图的连通性问题 7.4.1 无向图的连通分量和生成树 **7.4.2 有向图的强连通分量 7.4.3 最小生成树
**7.4.4 关节点和重连通分量

66 7.4.1 无向图的连通分量 连通分量求解过程 深度优先搜索和广度优先搜索在基于一点的搜索过程中，能访问到该顶点所在的最大连通子图的所有顶点，即一个连通分量。 通过变换搜索顶点，可求得无向图的所有连通分量。

67 7.4.1 最小生成树 最小生成树的定义 对于边带权图(网)来说：在所有的生成树中，各边的权值(边长)总和最小的生成树称作最小生成树。

68 小,必然在一棵 生成树中 7.4.1 最小生成树 最小生成树的性质（MST性质）
假设G=(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U，v∈V-U，则必存在一棵包含边(u,v)的最小生成树。 19 如图所示：连接 两 部分的边有 (f,e), (f,d),(g,d), (c,d)其中(f,e)最 小,必然在一棵 生成树中 f 3 a 15 18 e 16 18 g 20 9 15 b 8 c d 20

69 7.4.1 最小生成树 最小生成树算法--普里姆(Prim)算法思想 设G=(V,E)是连通网，用T来记录G上最小生成树边的集合。 (1)算法开始时，U={1|1∈V}(选一个初始顶点)，T={ }； (2)找到满足min{weight(u,v)|u∈U，v∈V-U}的边(ui,vi)，把它并入集合T中，同时vi并入U； (3)反复执行b，直到U=V时终止算法。

70 7.4.1 最小生成树 普里姆(Prim)算法示例演示 0 1 2 3 4 5 adjVEx closedge[n] lowcost 6 6
100 100 3 4 2 6 6 v5 v6 v5 v6 adjVEx v1 closedge[n] lowcost 6 1 5 100

71 7.4.1 最小生成树 普里姆(Prim)算法示例演示 打印v1-v3 顶点: 0 1 2 3 4 5 adjVEx v3 v3 v3
6 v1 5 6 v1 5 打印v1-v3 1 1 v2 v2 5 5 v4 v4 v3 v3 3 100 100 4 2 6 6 v5 v6 v5 v6 顶点: adjVEx v1 v3 v3 v3 closedge[n] lowcost 6 1 5 100 5 6 4

72 7.4.1 最小生成树 普里姆(Prim)算法示例演示 打印v1-v3 打印v3-v6 0 1 2 3 4 5 adjVEx v6
adjVEx v3 v1 v6 closedge[n] lowcost 5 6 4 2

73 7.4.1 最小生成树 普里姆(Prim)算法示例演示 0 1 2 3 4 5 adjVEx v2 closedge[n] lowcost
打印v1-v3 6 v1 v1 5 1 打印v3-v6 1 5 v2 v2 v4 5 5 v4 v3 打印v6-v4 v3 2 3 4 2 6 6 4 打印v3-v2 6 v5 v6 v5 v6 打印v2-v5 adjVEx v3 v1 v6 v2 closedge[n] lowcost 5 2 6 3

74 见下页 7.4.1 最小生成树 普里姆(Prim)算法详解
void MiniSpanTree_P(MGraph G, VErtexType u) { 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; // 初始，U＝{u} for (i=0; i<G.VExnum; ++i) { } 继续向生成树上添加顶点; 见下页

75 接上页 7.4.1 最小生成树 普里姆(Prim)算法详解 k = minimum(closedge);
printf(closedge[k].adjVEx, G.VExs[k]); // 输出生成树上一条边 closedge[k].lowcost = 0; // 第k顶点并入U集 for (j=0; j<G.VExnum; ++j) //修改其它顶点的最小边 if (G.arcs[k][j].adj < closedge[j].lowcost) closedge[j] = { G.VExs[k], G.arcs[k][j].adj };

76 7.4.1 最小生成树 普里姆(Prim)算法分析 时间复杂性主要体现在两层循环上，复杂性是O（n2） 空间复杂性主要体现在两个辅助数组，复杂性是O（n）

77 7.4.1 最小生成树 Kruskal算法思想 设G=(V,E)是连通网，用T来记录G上最小生成树边的集合。 (1)从G中取最短边e，如果边e所关联的两个顶点不在T的同一个连通分量中，则将该边加入T； (2)从G中删除边e； (3)重复(1)和(2)两个步骤，直到T中有n-1条边。

78 7.4.1 最小生成树 Kruskal算法示例演示 6 15 5 11 1 1 5 15 7 1 3 3 13 3 2 2 4 12 2 5 14 6 4 5 4 5

79 7.4.1 最小生成树 Kruskal算法概要 输入:连通图G=(V,E),其中V={1,2,…,n}, 输出:一颗最小生成树: void Kruskal(V,T) {T=V; ncomp=n;//连通分量 while(ncomp>1) {从E中取出删除权最小的边(v,u); if(v和u属于T中不同的连通分量) {T=T∪{(v,u)}; ncomp--;} }

80 7.4.1 最小生成树 Prim算法和Kruskal算法比较 算法名 普里姆算法 克鲁斯卡尔算法 时间复杂度 O(n2) O(eloge) 适应范围 稠密图 稀疏图

81 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

82 7.5 有向无环图的应用 7.5.1 拓扑排序 7.5.2 关键路径

83 7.5 有向无环图的应用 问题提出 一个无环的有向图称作有向无环图，简称DAG图。 DAG图在工程计划和管理方面应用广泛。几乎所有的工程(project)都可分为若干个称作“活动”的子工程， 并且这些子工程之间通常受着一定条件的约束。

84 某些子工程必须在另外的一些子工程完成之后才能开始。对整个工程和系统，人们主要关心的是两方面的问题：
7.5 有向无环图的应用 问题提出 某些子工程必须在另外的一些子工程完成之后才能开始。对整个工程和系统，人们主要关心的是两方面的问题： （1）工程能否顺利进行； （2） 完成整个工程所必须的最短时间。 拓扑排序 关键路径

85 7.5.1 拓扑排序 拓扑排序事例分析 计算机专业课程次序的安排就是一个简单的工程，每一门课程的学习都是整个工程的活动。其中有些课程要求先安排，有些则不需要，如何安排好课程学习的先后次序，这是一个典型的拓扑排序问题。

86 7.5.1 拓扑排序 拓扑排序事例分析 编号 课程名称 先修课程 1 计算机原理 编译原理 ,5 3 操作系统 ,5 4 程序设计 无 5 数据结构 ,6 6 离散数学 7 形式语言 8 电路基础 9 高等数学 无 10 计算机网络

87 7.5.1 拓扑排序 拓扑排序事例分析 编号 先修课程编号 1 8 2 4,5 3 4,5 4 无 5 4,6 6 9 7 6 8 9
编号 先修课程编号 ,5 ,5 无 ,6 无 10 1 8 2 生成DAG图 5 9 4 3 6 7

88 7.5.1 拓扑排序 拓扑排序有关概念 顶点活动网(AOV网) ：将顶点表示活动，边表示活动之间的关系的网称为顶点活动网。 拓扑序列：把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：若AOV网中存在从vi到vj的路径，则在该序列中，vi必位于vj之前。 拓扑排序：构造AOV网的拓扑序列的操作被称为拓扑排序。

89 7.5.1 拓扑排序 拓扑排序特点 (1)一个有向图的拓扑序列不一定唯一; (2)有向无环图一定存在拓扑序列; (3)有向有环图不存在拓扑序列; (4)通过构造拓扑序列，可判定AOV网是否存在环。

90 7.5.1 拓扑排序 拓扑排序算法的基本思想 (1)在有向图中选一个入度为0的顶点输出。 (2)从图中删除该顶点及所有它的出边。 (3)重复执行a和b，直到全部顶点均已输出，或图中剩余顶点的入度均不为0(说明图中存在回路，无法继续拓扑排序)。

91 讨论：如果顶点还没有输出完而找不到入度为零的顶点怎么办？
7.5.1 拓扑排序 拓扑排序算法的示例演示 1 8 9 7 1 2 3 5 4 3 4 6 8 9 7 2 5 6 讨论：如果顶点还没有输出完而找不到入度为零的顶点怎么办？ 答案：存在环路，无法进行拓扑排序，退出。

92 7.5.1 拓扑排序 拓扑排序算法演示 v3 v6 v4 v1 栈 indegree[] 1 1 2 v1 v2 ^ V3 V4 V5 V6
2 1 3 1 1 2

93 7.5.1 拓扑排序 拓扑排序算法概要 增加一个存放各顶点入度的数组indegree[] (1)扫描indegree[],将入度为零的顶点入栈; (2)while(栈非空) { 弹出栈顶元素vi并输出; 检查vi的出边表,将每条出边<vi,vj>的终点vj的入度减1, 若vj的入度减至0,则vj入栈; } (3)若输出的顶点数小n,则“有回路”；否则正常结束。

94 7.5.1 拓扑排序 求各顶点入度的算法详解 void FindInDegree(ALGraph G, int indegree[]) {int i; ArcNode *p; for (i=0;i<G.VExnum;i++) {p=G.VErtices[i].firstarc; while (p) {indegree[p->adjvex]++; p=p->next; }

95 见下页 7.5.1 拓扑排序 拓扑排序算法详解 Status TopologicalSort(ALGraph G) {
SqStack S; int count,k,i; ArcNode *p; int indegree[MAX_VERTEX_NUM]; FindInDegree(G, indegree); // 对各顶点求入度 InitStack(S); for (i=0; i<G.VExnum; ++i) // 建零入度顶点栈S if (!indegree[i]) Push(S, i); // 入度为0者进栈 count = 0; // 对输出顶点计数 见下页

96 接上页 7.5.1 拓扑排序 拓扑排序算法详解 while (!StackEmpty(S)) { Pop(S, i);
printf(i, G.VErtices[i].data); ++count; for (p=G.VErtices[i].firstarc; p; p=p->nextarc) { k = p->adjVEx; if (!(--indegree[k])) Push(S, k); } if (count<G.VExnum) return ERROR; else return OK; } // TopologicalSort

97 7.5.1 拓扑排序 算法分析 设AOV网有n个顶点，e条边。 初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)； 拓扑排序算法的时间复杂度为O(n+e)。

98 7.5.2 关键路径 关键路径的有关概念 AOE网：带权的有向图,顶点表示事件,边表示活动，权表示活动持续的时间。 AOE网的特点 (1)表示实际工程计划的AOE网应该是无回路的; (2)只有一个入度为零的顶点(称作源点),表示整个活动开始; (3)只有一个出度为零的顶点(称作汇点)表示整个活动结束。

99 源点 汇点 7.5.2 关键路径 AOE网图示 讨论： (1)整个工程需要多少时间？ (2)哪些活动是影响工程进度的关键？ v2 v6 12
10 2 20 20 2 12 v1 v4 v5 v7 v9 15 2 10 v8 12 V3 源点 汇点 讨论： (1)整个工程需要多少时间？ (2)哪些活动是影响工程进度的关键？

100 源点 汇点 7.5.2 关键路径 AOE网图示 答案： 最短时间是从源点到汇点的最长路径长度。 最长路径上的活动是影响工程进度的关键。 v2
12 10 2 20 20 2 12 v1 v4 v5 v7 v9 15 2 10 v8 12 V3 源点 汇点 答案： 最短时间是从源点到汇点的最长路径长度。 最长路径上的活动是影响工程进度的关键。

101 7.5.2 关键路径 关键路径 在AOE 网中，有些活动可以同时进行，完成一个工程所需的最短时间是从源点到汇点的最长路径长度。 长度最长的路径称为关键路径。 关键活动 关键路径上的活动都是关键活动。

102 讨论：关键活动延长是否必然影响工期？关键活动缩短是否必然缩短工期？
7.5.2 关键路径 v2 v6 12 10 2 20 20 2 12 v1 v4 v5 v7 v9 15 2 10 v8 12 V3 讨论：关键活动延长是否必然影响工期？关键活动缩短是否必然缩短工期？ 结论：关键活动延长必然影响工期？关键活动缩短不一定能缩短工期？

103 事件vi的最早发生时间是从源点v1到vi的最长路径长度，记作ve(i)。
7.5.2 关键路径 v2 v6 12 10 2 20 20 2 12 v1 v4 v5 v7 v9 15 2 10 v8 12 V3 事件的最早发生时间与最迟发生时间 事件vi的最早发生时间是从源点v1到vi的最长路径长度，记作ve(i)。 事件vk的最迟发生时间是vn的最早发生时间ve(n)减去vk到vn的最长路径长度，记作 vl(k)。。

104 活动<vi,vj>的最早开始时间是vi的最早开始时间，记作e(i)。
7.5.2 关键路径 v2 v6 12 10 2 20 20 2 12 v1 v4 v5 v7 v9 15 2 10 v8 12 V3 活动的最早发生时间与最迟发生时间 活动<vi,vj>的最早开始时间是vi的最早开始时间，记作e(i)。 活动<vi,vj>的最迟开始时间是vj的最迟开始时间减去<vi,vj>的持续时间，记作l(i) 。

105 最早发生时间与最迟发生时间相等的活动为关键活动。
7.5.2 关键路径 v2 v6 12 10 20 2 20 2 12 v1 v4 v5 v7 v9 15 2 10 v8 12 V3 活动的最早发生时间与最迟发生时间的性质 最早发生时间与最迟发生时间相等的活动为关键活动。 我们的目的就是要找出关键活动，为缩短工期提供帮助。

106 7.5.2 关键路径 求关键活动算法要点 (1)求出每个事件i的最早发生时间ve(i)和vl(i) (2)设活动ai所对应的边为<j,k>,dut(<j,k>)表示其持续时间,用如下公式计算活动ai的最早发生时间e(i)和最迟发生时间l(i): e(i)=ve[j] l(i)=vl[k]-dut(<j,k>) (3)比较e(i)和l(i)， e(i)和l(i)相等的活动即为关键活动。

107 7.5.2 关键路径 求事件的最早发时间和最晚发生时间步骤 第一步为前进阶段:从ve[1]=0开始,沿着路径上每条边的方向,用如下公式求每个事件的最早发生时间: ve[j]= 第二步为回退阶段:从已求出的vl[n-1]=ve[n-1]开始,沿着路径上每条边的相反方向,用如下公式求每个事件的最迟发生时间: vl[i]=

108 7.5.2 关键路径 关键路径算法所用数据结构 float ve[n],vl[n]; //记录事件的最早发生时间和最晚发生时间 邻接表的存储表示 #define MAX_VERTEX_NUM 20 (1)边表： typedef struct ArcNode { int adjVEx; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType info; // 存权值 } ArcNode;

109 7.5.2 关键路径 (2)顶点表： typedef struct VNode { VErtexType data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList VErtices; int VExnum, arcnum; int kind; // 图的种类标志 } ALGraph; ALGraph G;

110 见下页 7.5.2 关键路径 关键路径算法详解 status TopologicalOrder(ALGraph G, Stack &T) {
// 求各顶点事件的最早发生时间ve(全局变量)。 // T为拓扑序列定点栈，S为零入度顶点栈。 // 若G无回路，则用栈T返回G的一个拓扑序列， //且函数值为OK，否则为ERROR。 见下页

111 接上页 见下页 7.5.2 关键路径 关键路径算法详解 Stack S;int count=0,k; char indegree[40];
ArcNode *p; InitStack(S); FindInDegree(G, indegree); for (int j=0; j<G.vexnum; ++j) // 建零入度顶点栈S if (indegree[j]==0) Push(S, j); // 入度为0者进栈 InitStack(T); //建拓扑序列顶点栈T count = 0; 见下页

112 7.5.2 关键路径 关键路径算法详解 接上页 for (int i=0; i<G.vexnum; i++) ve[i] = 0; // 初始化 while (!StackEmpty(S)) { Pop(S, j);Push(T, j);++count; for (p=G.vertices[j].firstarc; p; p=p->nextarc) { k = p->adjvex; // 对j号顶点的每个邻接点的入度减1 见下页

113 接上页 见下页 7.5.2 关键路径 关键路径算法详解 if (--indegree[k] == 0) Push(S, k);
// 若入度减为0，则入栈 if (ve[j]+p->info > ve[k]) ve[k] = ve[j]+p->info; } if (count<G.vexnum) return ERROR; else return OK; } // TopologicalOrder 见下页

114 7.5.2 关键路径 关键路径算法详解 Status CriticalPath(ALGraph G) { // G为有向网，输出G的各项关键活动。 Stack T; int a,j,k,el,ee,dut; char tag; ArcNode *p; if (!TopologicalOrder(G, T)) return ERROR; for(a=0; a<G.vexnum; a++) vl[a] = ve[G.vexnum-1]; // 初始化顶点事件的最迟发生时间

115 7.5.2 关键路径 关键路径算法详解 Status CriticalPath(ALGraph G) { // 算法7.14 while (!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值 for (Pop(T, j), p=G.vertices[j].firstarc; p; p=p->nextarc) { k=p->adjvex; dut=p->info; //dut<j,k> if (vl[k]-dut < vl[j]) vl[j] = vl[k]-dut; }

116 7.5.2 关键路径 关键路径算法详解 for (j=0; j<G.vexnum; ++j) // 求ee,el和关键活动 for (p=G.vertices[j].firstarc; p; p=p->nextarc) { k=p->adjvex;dut=p->info; ee = ve[j]; el = vl[k]-dut; tag = (ee==el) ? '*' : ' '; printf(j, k, dut, ee, el, tag); // 输出关键活动 } return OK; } // CriticalPath

117 7.5.2 关键路径 算法分析 在拓扑排序求Ve[i]和逆拓扑有序求Vl[i]时, 所需时间为O(n+e)； 求各个活动的e[k]和l[k]时所需时间为O(e)； 总共花费时间仍然是O(n+e)。

118 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用
7.6 最短路径

119 7.6 最短路径 问题的提出 路径长度：路径上边的权值之和 最短路径：两结点间权值之和最小的路径 交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路径 交通咨询系统：A 到 B 最短路径 计算机网发送 节省费用,A到B沿最短路径传送

120 7.6 最短路径 7.6.1 单源最短路径 7.6.2 每一对顶点之间的最短路径

121 7.6.1 单源最短路径 单源最短路径：给定有向图G和源点vi，求vi到G中其余各顶点的最短路径。 算法思想 示例演示 算法要点 存储结构 算法 算法分析

122 7.6.1 单源最短路径 算法思想 Dijkstra提出按路径长度的递增次序，逐步产生最短路径。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 5 6 v1 v3 讨论：边权值能否为负值？ 3 v0 2 2 3 v2 v4 4 答案：不能。 参考图

123 7.6.1 单源最短路径 示例演示 0 1 2 3 4 5 D[5] 5 6 7 6 3 2 2 final[5] 1 3 4 2 P[5]
距离值 5 6 3 60 D[5] 5 6 7 6 v1 v3 3 v0 2 2 1 final[5] 1 3 v2 v4 4 -1 2 P[5] 2 2 参考图 已求出顶点 结点前趋

124 7.6.1 单源最短路径 示例演示 0 1 2 3 4 5 6 D[5] 3 2 2 final[5] 1 1 1 3 4 P[5] v1
5 6 v1 v3 5 3 6 7 D[5] 3 2 2 v0 1 final[5] 1 1 1 3 v2 v4 4 -1 2 P[5] 参考图

125 7.6.1 单源最短路径 算法要点 设源点为vi，已求出最短距离的顶点集合为S。 用数组D记录当前从源点vi到各顶点的最短路径。 初值：S={vi} D的初态是：若从v到vi有弧，D[i]记录弧上的权值。否则为无穷大。

126 7.6.1 单源最短路径 算法要点 (1)假设用带权的邻接矩阵arcs来表示带权的有向图，arcs[i][j]表示<vi,vj>上的权值。若边不存在，则为无穷。 初值：S={vi} D的初态是：若从v到vi有弧D[i]记录弧上的权值。否则为无穷大。 (2)选择vj使得 vj就是当前求得的从v出发的最短路径的终点，把j并入S。

127 7.6.1 单源最短路径 算法要点 (3)修改从v出发到集合V-S上任一顶点vk可达的最短路径 D[j]+arcs[j][k]<D[k] 则修为： D[k] =D[j]+arcs[j][k] (4)重复(2),(3)共n-1次。

128 7.6.1 单源最短路径 存储结构 原来的邻接矩阵存储结构： typedef struct ArcCell { // 弧的定义 VRType adj; InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

129 7.6.1 单源最短路径 存储结构 typedef struct { // 图的定义 VErtexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; // 弧的信息 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 } MGraph; MGraph G;

130 7.6.1 单源最短路径 存储结构 实用存储结构： typedef struct { // 图的定义 VErtexType vexs[MAX_VERTEX_NUM]; float arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 弧的信息 int vexnum, arcnum; // 顶点数，弧数 } MGraph; MGraph G;

131 7.6.1 单源最短路径 算法概要分析 (1)引入一个辅助数组D[],D[i]表示当前所找到的源点到每个终点i的最短路径长度。 最短路径的初值即为有向边的权值： D[i]=G.arcs[v0][i] 引入辅助数组final[],final[i]=1表示顶点i的最短路径已求出，final[i]=0表示顶点i的最短路径还没有求出。 初始状态：S[v0](源点)标志为1，其它为0。 引入数组P[]来记录路径。

132 7.6.1 单源最短路径 算法概要分析 (2)选择D[]中路径最小值的顶点v(已求出最短路的顶点除外) ， v就是当前求得的一条从v出发的最短路径的终点。 修改final[v]=1。 (3)修改未求出最短路径的顶点的最短路径长度，如果：D[v]+G.arcs[v][w]<D[w] 则修改D[w]为：D[w]=D[v]+G.arcs[v][w] 同时修改P[w]=v； (4)重复操作(2)、(3)n-1次。求得从v0到图上其余各顶点的最短路径长度递增序列。

133 见下页 7.6.1 单源最短路径 算法详解 void ShortestPath_DIJ(MGraph G,int v0,
int &P,float &D) { int i=0,j, v,w,min;bool final[MAX_VERTEX_NUM]; for (v=0; v<G.vexnum; ++v) { final[v] = FALSE; D[v] = G.arcs[v0][v]; P[v] = -1; // 设空路径 if (D[v] < INFINITY) P[v] = v0; } final[v0] = TRUE; P[v0]=-1 见下页

134 接上页 见下页 7.6.1 单源最短路径 算法详解 for (i=1; i<G.vexnum; ++i) {
min = INFINITY; // 当前所知离v0顶点的最近距离 for (w=0; w<G.vexnum; ++w) if (!final[w]) // w顶点在V-S中 if (D[w]<min) { v = w; min = D[w]; } 见下页

135 接上页 7.6.1 单源最短路径 算法详解 final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w=0; w<G.vexnum; ++w) if (!final[w] && (min+G.arcs[v][w]<D[w])) { D[w] = min + G.arcs[v][w].adj; P[w] = v; }//if }//for } // ShortestPath_DIJ

136 输出v0到各顶点的最小距离值和路径 7.6.1 单源最短路径 算法详解 for (i=0;i<=G.vexnum;i++)
{printf(“%f\n%d”,D[i],i); pre=p[i]; while(pre!=-1) {printf(“%d”,pre); pre=p[pre]; }

137 Dijkstra算法的时间复杂性主要体现在求每顶点的最短路径时，需要修改距离值和求最小值，时间复杂性O(n2)
7.6.1 单源最短路径 算法分析 Dijkstra算法的时间复杂性主要体现在求每顶点的最短路径时，需要修改距离值和求最小值，时间复杂性O(n2) Dijkstra算法的空间复杂性主要体现在两个辅助数组，空间复杂性是O(n)

138 (1) 求一个顶点到其余各顶点的最短路 求各顶点之间的最短路。 (2) 判断任意两顶点i,j之间是否有路
7.6.1 单源最短路径 算法功能 (1) 求一个顶点到其余各顶点的最短路 求各顶点之间的最短路。 (2) 判断任意两顶点i,j之间是否有路 (3) 判断有没有包括任意两顶点i,j的环路

139 7.6 最短路径 7.6.1 单源最短路径 7.6.2 每一对顶点之间的最短路径

140 依次把有向网络的每个顶点作为源点，重复执行Dijkstra算法n次，即可求得每对顶点之间的最短路径。
7.6.2 各顶点之间的最短路径 依次把有向网络的每个顶点作为源点，重复执行Dijkstra算法n次，即可求得每对顶点之间的最短路径。 是否有更简洁的方法？ Floyd算法

141 7.6.2 各顶点之间的最短路径 Floyd算法的思想 Floyd算法示例分析 Floyd算法要点 Floyd算法详解

142 对顶点进行编号，设顶点为0,1,...,n-1，算法仍采用邻接矩阵G.arcs[n][n]表示有向网络.
7.6.2 各顶点之间的最短路径 算法思想 对顶点进行编号，设顶点为0,1,...,n-1，算法仍采用邻接矩阵G.arcs[n][n]表示有向网络. D(-1)[n][n]表示中间不经过任何点的最短路径；它就是邻接距阵G.arcs[n][n] ； D(0)[n][n]中间只允许经过0的最短路径； D(1)[n][n]中间只允许经过0、1的最短路径； ……………………… D( n-1)[n][n],中间可经过所有顶点的最短路径。

143 7.6.2 各顶点之间的最短路径 算法思想示例分析 两点之间直达的距阵D(-1)： 例 求下图各顶点之 间的最短路径 8 5
AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD 6 60 3 5 1 2 8 求下图各顶点之 间的最短路径 8 5 两点之间只允许经过A点的距阵D(0)： 6 A 3 3 2 AA AB AC AD BA BB BC BAD CA CAB CC CD DA DB DC DD 6 60 3 5 1 8 9 2 B D 1 2 C

144 D(k+1)[i][j]是i与j间只可能经过1,2,…,k+1的最短路径。 如果i与j经过k+1,则可以写成如下形式： i……k+1……j
7.6.2 各顶点之间的最短路径 算法要点 设D(k)[n][n],中间只允许经过0,...k-1,k的最短路径已经求出； 求D(k+1)[n][n]，中间只允许经过0,...k-1,k,k+1的最短路径； D(k+1)[i][j]是i与j间只可能经过1,2,…,k+1的最短路径。 如果i与j经过k+1,则可以写成如下形式： i……k+1……j D(k)[i][k+1]+ D(k)[k+1][j] 比较D(k)[i][k+1]+ D(k)[k+1][j]与D(k)[i][j]的大小，把小值写进D(k+1)[i][j]。

145 见下页 初始化算法 7.6.2 各顶点之间的最短路径 算法详解 void ShortestPath_FLOYD(MGraph G,
PathMatrix P[], DistancMatrix &D) { int v,w,u,i; for(v=0; v<G.vexnum; ++v) for(w=0;w<G.vexnum;++w) {D[v][w] = G.arcs[v][w]; for (u=0; u<G.vexnum; ++u) P[v][w][u] = FALSE; if (D[v][w] < INFINITY) P[v][w][v] = P[v][w][w] = TRUE; } 见下页

146 7.6.2 各顶点之间的最短路径 算法详解 for (u=0; u<G.vexnum; ++u) //经过的顶点 for (v=0; v<G.vexnum; ++v) for (w=0; w<G.vexnum; ++w) if (D[v][u]+D[u][w] < D[v][w]) { // 从v经u到w的一条路径更短 D[v][w] = D[v][u]+D[u][w]; for (i=0; i<G.vexnum; ++i) P[v][w][i] =(P[v][u][i] || P[u][w][i]); }

147 7.6.2 各顶点之间的最短路径 算法分析 Floyd算法的时间复杂性主要体现在三重循环，时间复杂性为O(n3) Floyd算法的空间复杂性主要体现在三重利用了一个二维数组，空间复杂性为O(n2)

148 7.6.2 各顶点之间的最短路径 算法分析 讨论：权值是否可以是负值？ 答案：权值可以是负值，但不能有长度是负值的环路。

149 7.6.2 各顶点之间的最短路径 算法功能 (1) 求出了任意两点i,j之间的最短路径。 (2) 可以判断任意两点之间是否有路。 可以判断是不是强连通图。 (3) 可以判断有向图经过任意两点是否有环路。

150 本章小结 (1) 熟练掌握图的定义、术语和性质； (2) 熟练掌握ADT图的设计和实现；
(3) 熟练掌握图的邻接矩阵、邻接表的存储结构 及其构造方法； (4) 熟练掌握图的两种遍历方法：深度优先遍历和广度优先遍历； (5) 掌握最小生成树的算法、拓扑排序的算法； (6) 理解关键路径的算法，构造最短路径的Dijkstra算法和Floyed算法。