Chapter 07 Graph 第七章 图 Prof. Qing Wang.

Presentation on theme: "Chapter 07 Graph 第七章 图 Prof. Qing Wang."— Presentation transcript:

1 Chapter 07 Graph 第七章 图 Prof. Qing Wang

2 本章学习的线索 主要线索 重点 难点 图的定义及表示 图的遍历和生成树 最小代价生成树和最短路径 拓扑排序 图的遍历和最短路径 图的定义、
表示和存储 图的遍历 及生成树 最小代价生成树和最短路径 拓扑排序 关键路径 Prof. Q. Wang

3 Contents Definition and notations of graph Storage structure of graph
Graph traversal Connected component and spanning tree Mini spanning tree Shortest path Topological sorting & Critical path Conclusion Prof. Q. Wang

4 图 (Graph)是一种较线性结构和树更为复杂的数据结构。 在线性表中，一个元素只能和其直接前驱或直接后继相关；
在树中，一个结点可以和其下一层的所有孩子结点相关，以及上一层的双亲结点相关，但不能和其他的任何结点直接相关； 而对于图来说，图中任意两个结点之间都可以直接相关，因此图形结果非常复杂。 但是图的用途也极其广泛，已渗入到语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学等其他分支学科当中。 在本课程当中，我们主要讨论如何在计算机上实现图的操作，因此主要学习图的存储结构以及图的若干操作的实现。 Prof. Q. Wang

5 Example Prof. Q. Wang

6 Contents Definition and notations of graph Storage structure of graph
Graph traversal Connected component and spanning tree Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

7 7.1 Definition and notations of graph
Vertex (顶点)：图中的数据元素。设它的集合用V表示。 Arc (弧)：设两个顶点之间关系的集合用VR(Vertex Relationship)来表示，且v, wV，若<v, w>VR，则<v, w>表示从v到w的一条弧(Arc)。这里称v为弧尾(Tail)，w为弧头(Head)。 此时的图称为Directed graph (有向图)。 Undirected graph (无向图)：若<v, w> VR必能推导出<w, v> VR，即VR是对称的，则用无序对(v, w)代替有序对，表示v和w之间的一条边(Edge)。此时的图称为无向图。 Prof. Q. Wang

8 因此，图由顶点的有穷非空集合V和顶点的偶对(边)集合E组成，记为G=(V, E)。
ADT Graph See P.156 Prof. Q. Wang

9 返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回“空”
返回v的（相对于w的）下一个邻接顶点，若w是v的最后一个邻接顶点，则返回“空” Prof. Q. Wang

10 A＝{<v1,v2>, <v1,v3>, …<vn-1vn>}
二元组G=(V, A)表示有向图，其中 V＝{v1, v2, …, vn}， A＝{<v1,v2>, <v1,v3>, …<vn-1vn>} V1 V2 V3 V4 有向图 V1 V2 V4 V5 V3 无向图 二元组G=(V, E) 表示无向图，其中 E＝{(v1,v2), (v1,v3), …(vn-1vn)} 在以后的讨论中，我们不考虑顶点到其自身的弧或边， 那么对于有n个顶点的无向图，边的最大数目为n(n-1)/2； 对于n个顶点的有向图，弧的最大数目为n(n-1)。由此我们 可以得到下面的定义： Prof. Q. Wang

11 2. Weight related & sub-graph
Concepts of Graph 1. Categorization 2. Weight related & sub-graph 3. Adjacency related 4. Path related 5. Connectivity related 6. Spanning tree & forest Prof. Q. Wang

12 Complete graph (完全图)：有n(n-1)/2条边的无向图。
1. Categorization Complete graph (完全图)：有n(n-1)/2条边的无向图。 Directed Complete graph (有向完全图)：有n(n-1)条边的有向图。 Sparse Graph (稀疏图)：有很少条边或弧的图(e < nlogn) Dense Graph (稠密图)：(e>=nlogn) Prof. Q. Wang

13 2. Weight related & sub-graph
网 (Network)：带权的图。 Subgraph (子图)：设两个图G＝(V, {E})和G’=(V’,{E’})，如果V’V且 & E’ E，则称G’为G的子图。 Prof. Q. Wang

14 Degree (顶点的度D) ：和该顶点相关联的边的数目。 OutDegree (顶点的出度OD) ：以该顶点为弧尾的弧的数目。
3. Adjacency related 邻接点：对于无向图G＝(V,{E})，如果边(v, w)E，则称顶点v和w互为邻接点(Adjacent)；边(v, w)依附于(Incident)顶点v和w，或者说，v和w相关联。 Degree (顶点的度D) ：和该顶点相关联的边的数目。 OutDegree (顶点的出度OD) ：以该顶点为弧尾的弧的数目。 InDegree (顶点的入度ID) ：以该顶点为弧头的弧的数目。 Prof. Q. Wang

15 Path (路径)：在图中从顶点v到顶点w所经过的所有顶点的序列。 Simple path (简单路径)：序列中顶点不重复出现的路径。
4. Path related Path (路径)：在图中从顶点v到顶点w所经过的所有顶点的序列。 Simple path (简单路径)：序列中顶点不重复出现的路径。 Loop (回路或环)：第一个顶点和最后一个顶点相同的路径。 Simple Loop (简单回路或环)：除第一个和最后一个顶点，其余顶点不重复出现的路径。 Rooted graph (有根图)：在有向图中，若存在一顶点v，从该顶点有路径可以到图中其它所有顶点，则称此有向图为有根图，v称为图的根。 Prof. Q. Wang

16 Connected (连通)：在无向图中，如果从v到w存在路径，则称v和w是连通的。
5. Connectivity related Connected (连通)：在无向图中，如果从v到w存在路径，则称v和w是连通的。 Connected graph (连通图)：无向图G中如果任意两个顶点vi,vj之间都是连通的，则称图G是连通图。 Connected component (连通分量)：无向图中的极大连通子图。 Strong connected graph (强连通图)：在有向图G中，如果对于每一对vi,vjV, vivj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。 Strong connected component (强连通分量)：有向图中的极大强连通子图。 Prof. Q. Wang

17 如果一个有向图恰有一个顶点入度为0，其余顶点入度均为1，则该图必定是一棵有向树。所有树可以看成是图的特例。
6. Spanning tree & forest 连通图的生成树：是连通图的一个极小连通子图，它含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边。因此，对于生成树而言，只要再增加一条边，就会出现环。而如果图中有n个顶点，小于n-1条边，则该图是非连通图；但有n-1条边的图却不一定是生成树。 如果一个有向图恰有一个顶点入度为0，其余顶点入度均为1，则该图必定是一棵有向树。所有树可以看成是图的特例。 有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有构成若干棵不相交的有向树的弧。 Prof. Q. Wang

18 Contents Storage structure of graph Definition and notations of graph
Graph traversal Connected component and spanning tree Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

19 Question How about the complexity of these two functions?
FirstAdjVex(G,v) NextAdjVex(G,v,w) Prof. Q. Wang

20 7.2 Storage structure of graph
图存储的特殊性： 顶点之间的关系无法用他们在内存中的存储位置来表示。 用多重链表来表示图是自然的事情，它用一个由一个数据域和多个指针域组成的结点表示图中的一个结点。其中，数据域存放该顶点的信息，指针域存放指向其邻接点的地址。 常用的存储方法有： ★ 邻接矩阵表示法 ★ 邻接表表示法 十字链表表示法 邻接多重表表示法 Prof. Q. Wang

21 7.2.1 Adjacent matrix (邻接矩阵表示法)
图需要存储的信息：顶点和弧。 图的数组表示法：用两个数组分别存放图中顶点的信息（数据元素）和图中边（或弧）的信息（数据元素之间的关系）。 顶点信息的存储方法：数组 顶点类型：整型、字符型等 typedef char VexType; VexType vexs[MAXVEX]; 弧或边的存储：二维数组 弧的两个顶点的关系类型： typedef float AdjType; AdjType arcs[MAXVEX][MAXVEX]; Prof. Q. Wang

22 Declaration of adjacent matrix typedef struct {
VexType vexs[MAXVEX]; /* 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 邻接矩阵信息 */ int arcCount, vexCount; /* 图的顶点个数 */ } Graph, *PGraph; Characteristics of adjacent matrix 无向图的邻接矩阵一定是一个对称矩阵。 无向图的邻接矩阵的第i行(或第i列)非零元素(或非∞元素)个数为第i个顶点的度D(vi)。 有向图的邻接矩阵的第i行非零元素(或非∞元素)个数为第i个顶点的出度OD(vi)，第i列非零元素(或非∞元素)个数就是第i个顶点的入度ID(vi)。 邻接矩阵表示图，很容易确定图中任意两个顶点之间是否有边相连。 Prof. Q. Wang

23 1 if <vi, vj> or (vi, vj)  VR 0 otherwise arcs[i][j] =
Adjacent matrices of G1 and G2 V1 V2 V3 V4 Directed graph G1 G1.arcs = V1 V2 V4 V5 V3 Undirected graph G2 G2.arcs = Prof. Q. Wang

24 The adjacent matrix for network (weighted graph):
Wi,j if <vi, vj> or (vi, vj)  VR 0 or ∞ otherwise A[i][j] = For example, the matrix of G1 is Directed network G1 V1 V2 V3 V4 5 4 9 7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 7 4 ∞ ∞ ∞ G1.arcs = Prof. Q. Wang

25 The initialization of adjacent matrix of graph
Status CreateGraph (PGraph pG){ int i， j; AdjType w; VexType v1, v2; /* 输入顶点数、边数和是否输入边的相关信息的标志 */ scanf (“%d%d”, &pG->vexCount, &pG->arcCount); for (i = 0; i< pG->vexCount; i++) /* 读入所有的顶点 */ scanf (“%c”, &pG->vexs[i]); for (i = 0; i < pG->vexCount; i++) /* 初始化邻接矩阵 */ for (j = 0; j<pG->vexCount; j++) {/* 初始假设所有顶点都互不邻接 */ pG->arcs[i][j] = INFINITY; } for (i=0; i<pG->arcCount; i++) { /* 输入所有的边 */ /* 输入一条边依附的两个顶点和边上的权值*/ scanf (“%c%c%f”, &v1, &v2, &w); /* 查询两个顶点在图中存储的位置 */ i = LocateVex(pG, v1); j = LocateVex(pG, v2); Prof. Q. Wang

26 pG->arcs[i][j] = w;
pG->arcs[j][i] = pG.arcs[i][j]; /* 根据无向图的对称性填充矩阵 的对称部分 */ } return OK; /* 查找某个顶点在图中的存储位置（下标），找不到返回－1*/ int LocateVex (PGraph pG, VexType vert){ int i; for (i=0; i<pG->vexCount; i++) if (pG->vexs[i] = = vert) return i; return -1; } Prof. Q. Wang

27 Time complexity analysis (Adj. matrix)
下面看看该创建算法的时间效率（设n表示顶点个数，e表示边的条数）: 该算法中共有三个循环，第一个循环的循环次数为n, 第二个循环的次数为n2，第三个循环的次数为e*n其中n为确定边的两个顶点在图中的位置的循环次数。所以其时间效率应为O(n2+e*n)。 邻接矩阵表示法的优缺点： 优点：各种基本操作都易于实现。 缺点：空间浪费严重。某些算法时间效率低。如图的 创建算法。 Prof. Q. Wang

28 7.2.2 Adjacency List (邻接表表示法)
用邻接矩阵存储弧或边的信息，比较浪费空间，如果我们只存储图中已有的弧或边的信息，就可以节省空间。而图中所有顶点都是依附于某两个顶点的，因此如果对图中的所有顶点都建立一个单链表来存储所有依附于该顶点的弧或边，就可以把图中所有已有的弧或边的信息保存下来。而对于图中所有顶点还是使用一个一维数组来存放。这种存储方法就是邻接表表示法。 在邻接表表示法中，对于顶点单元i，需要存放的内容有顶点信息以及指向依附于该顶点的第一条弧或边的指针，用这个指针来指向依附于顶点i的所有的弧或边组成的单链表。对于弧单元，需要存放该弧指向的顶点的位置（也就是该弧依附的另一个顶点的位置）和指向依附于该弧的弧尾顶点的下一条弧的指针。对于弧和顶点分别可以用如下的结构实现： Prof. Q. Wang

29 Declaration of adjacent list
typedef struct EdgeNode { int endvex; /* 相邻顶点字段 */ AdjType weight; /* 边的权 */ struct EdgeNode *nextedge; /* 链字段 */ } EdgeList, *PEdgeList, *PEdgeNode, EdgeNode; /* 边表 */ typedef struct { VexType vertex; /* 顶点信息 */ PEdgeList edgelist; /* 边表头指针 */ } VexNode; /* 顶点表 */ { VexNode vexs[MAXVEX]; int vexNum, edgeNum; /* 图的顶点和边个数 */ } GraphList; Prof. Q. Wang

30 Adjacent list and reverse adjacent list of directed graph
Directed graph G1 V1 2 1 ^ V1 3 ^ 1 1 V2 V2 ^ ^ 2 2 V3 3 ^ V3 ^ 3 3 V4 V4 2 ^ ^ Adjacent list of G1 Reverse adjacent list of G1 Prof. Q. Wang

31 Adjacent list of undirected graph
V1 V2 V4 V5 V3 Undirected graph G2 V1 2 V2 V3 V4 3 4 V5 1 ^ Adjacent list of G2 Prof. Q. Wang

32 有了邻接表作存储结构，下面看看一些基本操作的实现： 1. 求无向图中某个顶点的度： 为该结点所指向的链表中的结点总数。
从邻接表的存储结构可以看出，对于有n个顶点和e条边的无向图，它的邻接表需要n个头结点的空间和2e条边的空间（对于有向图需要多少条弧的空间？），显然，当边稀疏(e <nlogn)时，用邻接表表示图比用邻接矩阵要节省空间，特别是当和边相关的信息较多的情况下更是如此。 有了邻接表作存储结构，下面看看一些基本操作的实现： 1. 求无向图中某个顶点的度： 为该结点所指向的链表中的结点总数。 2. 求有向图的出度： 该结点所指向的链表的结点总数。 3. 求有向图的入度： 必须搜索整个邻接表才能得到。 改进的结构：带入度信息的邻接表 Prof. Q. Wang

33 The initialization of adjacent list for directed network
Status CreateDG (GraphList *g) { int i, j, k, v1, v2; PEdgeNode p; AdjType weight; scanf ("%d %d", &g->vexNum, &g->edgeNum); for (i=0; i<g->vexNum; i++) { scanf("%d", &g->vexs[i].vertex); /* Input vertexes */ g->vexs[i].edgelist = NULL; } for (k=0; k<g->edgeNum; k++) { scanf("%d %d %f", &v1, &v2, &weight); i = LocateVex(*g, v1); j = LocateVex(*g, v2); p = (EdgeNode *)malloc(sizeof(EdgeNode)); assert(p); p->endvex = j; p->weight =weight; p->nextedge = g->vexs[i].edgelist; g->vexs[i].edgelist = p; return OK; } /* End of CreateUDN() */ Prof. Q. Wang

34 Time complexity analysis (Adj. list)
由于求邻接表中某个顶点的入度不方便，所以有时为了 确定顶点的入度，就建立一个有向图的逆邻接表，即对图中 每个顶点vi建立一个以vi为头的弧的表。如下页图所示。 下面看看创建邻接表的时间效率。由于创建邻接表没有 对邻接矩阵初始化的一个循环，所以时间效率为O(n+e*n)。 如果输入的顶点信息即为顶点的编号的话，这时不需要确定 顶点在图中的位置，因此时间复杂度可为O(n+e)。 邻接表的优缺点： 优点：容易找任一结点的第一邻接点和下一个邻接点。 存储量小。 缺点：判定任意两个结点之间是否有边或弧不方便。 Prof. Q. Wang

35 7.2.3 Cross linked list 可以看成是有向图的邻接表和逆邻接表结合起来形成的一种链表。
在邻接表的弧(或边)结点中增加一个指针指向弧头相同的下一条弧，再增加一个该弧依附的弧尾顶点，即可以方便地求某个顶点的入度。 typedef struct _ArcNode { int tailVex, headVex; /* 弧的头尾顶点的位置*/ struct _ArcNode *hLink; /* 弧头相同的弧的链域*/ struct _ArcNode *tLink; /* 弧尾相同的弧的链域*/ AdjType weight; } ArcNode; Declaration of arc node Prof. Q. Wang

36 对于邻接表的顶点结点，需要增加一个指针指向第一条以该顶点为弧头的弧的指针。
typedef struct _VexNode { VexType vertex; ArcNode *firstIn; /* 指向该顶点的第一条入弧*/ ArcNode *firstOut; /* 指向该顶点的第一条出弧*/ } VexNode; typedef struct VexNode xList[Max_Vert_Num]; /* 表头向量*/ int vexNum, arcNum; } OLGraph; Declaration of vertex node Declaration of cross linked list of directed graph Prof. Q. Wang

37 Adjacent matrix and cross linked list for graph V1 V2
∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ 1 ∞ pG.arcs = V1 V3 V4 V2 ^ 1 2 3 Cross linked list of directed graph Prof. Q. Wang

38 从邻接矩阵和十字链表的对比图可以看出，十字链表可以看成是邻接矩阵的链表存储结构，只不过把邻接矩阵的矩阵当成稀疏矩阵用十字链表的方式来存储。
The initialization of cross linked list for directed network 输入: n个顶点和e条弧的信息 Status CreateDG (OLGraph *g) { AdjType weight; /* 非0则输入弧的其他信息*/ VexType v1,v2; int i, j, k; ArcNode *p; scanf("%d %d %d", &g->vexNum, &g->arcNum); /* 构造表头向量，即输入顶点 */ for (i=0; i<g->vexNum; i++) { /* 输入所有顶点并初始化指针成员 */ scanf (“%d”, &g->xlist[i].vertex); /* 输入顶点值 */ g->xlist[i].firstIn = NULL; /* 初始化指针*/ g->xlist[i].firstOut = NULL; /* 初始化指针*/ } Prof. Q. Wang

39 for (k=0; k<g->arcNum; k++) {
/* 输入各弧并构造十字链表 */ for (k=0; k<g->arcNum; k++) { scanf(“%d %d”, &v1, &v2); /* 输入每条弧的始点和终点 */ i = LocateVex(*g, v1); /* 确定v1和v2在图中的位置 */ j = LocateVex(*g, v2); p = (ArcNode *)malloc(sizeof(ArcNode)); /* 创建弧结点*/ assert(p); p->tailVex = i; /* 弧的始点是弧的弧尾*/ p->headVex = j; /* 弧的终点是弧的弧头*/ /* 当前结点插入到十字链表第一个的位置*/ p->hLink = g->xlist[j].firstIn; /* 作为第j个顶点的第一条入弧 */ p->tLink = g->xlist[i].firstOut; /* 作为第i个顶点的第一条出弧 */ /* 重新设置第一条入弧和出弧*/ g->xlist[j].firstIn = g->xlist[i].firstOut = p; } return OK; } /* End of CreateDG() */ Prof. Q. Wang

40 Time complexity analysis (OL List)
创建十字链表的时间复杂度：跟邻接表表示法一样。 十字链表的优缺点： 优点：容易求有向图的入度和出度。 缺点：操作较复杂 Prof. Q. Wang

41 Quick Review ADT of graph Representation and storage Functions Matrix
Linked list Adjacent list Cross list Multiple adjacent list Functions w=FirstAdjVex(G,v) w=NextAdjVex(G,v,w) Prof. Q. Wang

42 Contents Graph traversal Definition and notations of graph
Storage structure of graph Graph traversal Connected component and spanning tree Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

43 7.3 Traversing graph (图的遍历)
Definition of traversing graph (遍历图的定义)： 和树的遍历类似，从图中某一顶点出发访遍图中其余结点，且使每一个结点被访问且仅被访问一次。 遍历图的算法是求解图的连通性问题、拓扑问题和求关键路径等算法的基础。 遍历图比遍历树复杂得多，因为图中任一顶点都可能和其他顶点相邻接。所以可能在访问某个顶点后，沿着某条路径又回到该顶点上，即图中可能存在回路。为了避免一个顶点被访问多次，就需要记下每个已经被访问过的顶点，为此需设立一个数组来存放。 1. Depth First Search (深度优先搜索): DFS 2. Breadth First Search (广度优先搜索): BFS Prof. Q. Wang

44 7.3.1 Depth First Search (深度优先搜索)
类似于树的先根遍历，是树的先根遍历的推广。 假设初始状态是图中所有顶点都未被访问，则可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图直至所有与v有通路的顶点都被访问到。若此时图中还有顶点未被访问到，则另选图中未被访问的顶点作为起点，重复上述过程，直到图中 所有顶点都被访问到为止。 如图所示： V1 V2 V3 V7 V4 V1 V2 V4 V8 V5 V3 V6 V7 V5 V6 V8 Prof. Q. Wang

45 Framework of depth-first search
void traverseDFS (Graph *pgraph) { int visited[MAXVEX]; for (i=0; i<pgraph->n; i++) visited[i]=FALSE; /* 初始化数组visited */ for (i=0; i<n; i++) if (!visited[i]) DFS (pgraph, visited, i); } void DFS (Graph *pgraph, int visited[], int i) { visited[i]=TRUE; printf (“node: %c\n”, pgraph->vexs[i]); /* 访问出发点vi */ for (j=FirstAdjVex(pgraph,i)0; j>=0; j=NextAdjVex(pgraph, i, j)) if ( !visited[j]) DFS (pgraph, visited, j); } Prof. Q. Wang

46 Depth-first Search in adjacent matrix
/* 从vi出发进行深度优先搜索，图采用邻接矩阵表示法 */ void DFSInMatrix (Graph *pgraph, int visited[], int i) { int j; printf (“node: %c\n”, pgraph->vexs[i]); /* 访问出发点vi */ visited[i]=TRUE; for (j=0; j<pgraph->n; j++) if ( (pgraph->arcs[i][j]==1) && (visited[j]==FALSE) ) DFSInMatrix (pgraph, visited, j); } Prof. Q. Wang

47 Depth-first Search in adjacent list
/* 从vi出发进行深度优先搜索，图采用邻接表表示法 */ void DFSInList (GraphList *pgraphlist, int visited[], int i) { int j; PEdgeNode p; printf (“node: %c\n”, pgraphlist->vexs[i].vertex); visited[i]=TRUE; p=pgraphlist->vexs[i].edgelist; /* 取边表中的第一个边结点 */ while (p!=NULL) { /* 该顶点的相邻顶点未被访问 */ if (visited[p->endvex]==FALSE) DFSInList (pgraphlist, visited, p->endvex); /* 继续进行深度优先搜索 */ p=p->nextedge; /* 取边表中的下一个边结点 */ } Prof. Q. Wang

48 Time complexity analysis
void traverseDFS (Graph * pgraph) { int visited[MAXVEX]; for (i=0;i<pgraph->n;i++) /* 初始化数组visited */ visited[i]=FALSE; for (i=0; i<n; i++) if (visited[i]==FALSE) DFSInMatrix(pgraph,visited,i); } Time complexity analysis 从遍历算法来看，遍历图的过程实际上是一个查找某个顶点的邻接点的过程，因此算法的时间效率决定于所采取的存储结构。当用邻接矩阵作存储结构时，查找所有顶点的邻接点的时间效率为O(n2)，而用邻接表作存储结构时，时间效率为O(n＋e)，e为无向图的边数或有向图的弧数。 Prof. Q. Wang

49 7.3.2 Breadth First Search (广度优先搜索)
类似于树的层次遍历。 假设从图中某个顶点v出发，在访问了v之后，依次访问v的各个未曾访问过的邻接点，并保证“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问。直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的顶点，则任选其中之一作 为起点，重新开始上述过程，直至图中 所有顶点都被访问到。 V1 V2 V3 V1 V2 V3 V4 V5 V6 V7 V8 V7 V4 V5 V6 V8 Prof. Q. Wang

50 对于广度优先遍历，其关键之处在于怎么保证“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问。
也就是先到先被访问，这正好是队列的特点，因此可以使用队列来实现． V1 V2 V3 V4 V5 V8 V6 V7 V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V5 V6 V7 V8 Prof. Q. Wang

51 void bFSInMatrix (Graph *pgraph, int visited[], int i) {
PLinkQueue pq; int j, k; pq = creatEmptyQueue_link(); /* 置队列为空 */ printf (“node:%c\n”, pgraph->vexs[i]); visited[i] = TRUE; enQueue_link (pq,i); /* 将顶点序号进队 */ while ( !isEmptyQueue_link(pq) ) { /* 队列非空时执行 */ k = deQueue_link(pq); /* 队头顶点出队 */ for (j=0; j<pgraph->n; j++) if ( (pgraph->arcs[k][j] == 1) && (!visited[j]) ) { /*访问相邻接的未被访问过的顶点 */ printf (“node:%c\n”, pgraph->vexs[j]); visited[j] = TRUE; enQueue_link (pq,j); /* 新访问的顶点入队 */ } Prof. Q. Wang

52 void bFSInList (GraphList *pgraphlist, int visited[], int i) {
PLinkQueue pq; PEdgeNode p; int j; pq = creatEmptyQueue_link(); /* 置队列为空 */ printf (“node:%c\n”,pgraphlist->vexs[i].vertex); visited[i] = TRUE; enQueue_link (pq, i); /* 将顶点序号进队 */ while (!isEmptyQueue_link(pq)) { /* 队列非空时执行 */ j = deQueue_link (pq); /* 队头顶点出队 */ p = pgraphlist->vexs[j].edgelist; while ( p!=NULL) { if (!visited[p->endvex]) { /*访问相邻接的未被访问过的顶点 */ printf (“node:%c\n”,pgraphlist->vexs[p->endvex].vertex); visited[p->endvex] = TRUE; enQueue_link(pq,p->endvex); /* 新访问的顶点入队 */ } p = p->nextedge; Prof. Q. Wang

53 Time complexity analysis
void traverseBFS (Graph *pgraph) { int visited[MAXVEX]; int i,n; n=pgraph->n; for (i=0;i<n;i++) visited[i]=FALSE; for (i=0; i<n; i++) if (visited[i]==FALSE) bFSInMatrix (pgraph,visited,i); } Time complexity analysis 上述算法实质上是通过边或弧找邻接点，同时每个顶点至多进一次队列，因此，广度优先搜索遍历图的时间复杂度与深度优先搜索遍历相同，也是O(n2)（用邻接矩阵作存储结构）或O(n＋e)（用邻接表作存储结构），两者的不同是顶点访问的次序不同。 Prof. Q. Wang

54 Contents Definition and notations of graph Storage structure of graph
Graph traversal Connectivity analysis in undirected graph Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

55 7.4 Connectivity analysis in undirected graph
Connected component and spanning tree 在对无向图进行遍历时，对于连通图，从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点；而对于非连通图，则需从多个顶点出发进行搜索。而每一次从一个新顶点出发搜索得到的顶点序列就是图的各个连通分量中的顶点集。 例如P159图7.3中的G3是非连通图。按照P171图7.14所示的邻接表进行深度优先搜索，三次调用DFS函数（分别从A、D、G出发）得到的顶点序列为： ABMLJFC DE GHKI 这三个顶点集加上所有依附于它们的边，便构成了G3的三个连通分量。 Prof. Q. Wang

56 Connected components in unconnected graph
1 5 A B A B 7 8 9 D E C D E C 10 12 F G H F G H 6 I J K J 13 11 I K 4 L M L M 2 3 Prof. Q. Wang

57 Depth-first spanning tree Breadth-first spanning tree
在我们对连通图进行搜索时，搜索过程中经历的所有边和图中所有的顶点构成了连通图的一个极小连通子图，即连通图的生成树，称由深度优先搜索得到的生成树为深度优先生成树，而由广度优先搜索得到的生成树称广度优先生成树。 V1 V2 V3 V4 V5 V8 V6 V7 Original graph V1 V2 V3 V4 V5 V8 V6 V7 Depth-first spanning tree V1 V2 V3 V4 V5 V8 V6 V7 Breadth-first spanning tree Prof. Q. Wang

58 对于非连通图，其中的每一个连通分量都可以通过遍历得到一棵生成树，所有这些连通分量的生成树就构成了非连通图
生成森林。如果以孩子兄弟链表作生成森林的存储结构(左孩子-右兄弟)，则可以形成非连通图的生成森林。算法如下： 1 5 A B A B 7 8 9 D E C D E C 10 12 F G H F G H 6 I J K J 13 11 I K 4 L M L M 2 3 Prof. Q. Wang

59 A B A B D E C D E C F G H F G H I K J J I K L M L M A A L F C M J B D
Prof. Q. Wang

60 void DFSForest (MGraph g, CSTree *T) { CSTree p, q; int v; *T = NULL;
for (v = 0; v < g.vexNum; v++) visited[v] = FALSE; q = *T; for (v=0; v < g.vexNum; v++) { if (!visited[v]) { p = (CSNode *) malloc(sizeof(CSNode)); assert(p); p->data = GetVex (g, v); p->firstChild = NULL; p->nextSibling = NULL; if (!(*T)) *T = p; else q->nextSibling = p; q = p; DFSTree (g, v, &p); } /* if */ } /* for */ } /* End of DFSForest() */ 目的：根或者根的兄弟 Prof. Q. Wang

61 void DFSTree (MGraph g, int v, CSTree *T) {
BOOL first; CSTree p, q; int w; visited[v] = TRUE; first = TRUE; q = *T; for (w = FirstAdjVex (g, v); w!=-1; w = NextAdjVex (g, v, w)) { if (!visited[w]){ p = (CSTree) malloc(sizeof(CSNode)); p->data = GetVex (g, w); p->firstChild = NULL; p->nextSibling = NULL; if (first) { (*T)->firstChild = p; first = FALSE; } else q->nextSibling = p; q = p; DFSTree (g, w, &q); } /* if */ } /* for */ 目的：第一个孩子或者其他孩子 Prof. Q. Wang

62 Connected components of the unconnected graph
Example Unconnected graph A 4 3 2 1 1 B 5 2 C 3 D 4 E 6 5 5 F 6 4 1 6 G 5 4 7 H 9 8 8 I 9 7 9 J 8 7 10 K 13 12 11 11 L 14 10 12 M 14 10 13 N 10 Connected components of the unconnected graph 14 O 12 11

63 7.4.2 Strongly connected component in directed graph and spanning forest
V1 V2 V3 V4 深度优先搜索结果:V1,V2,V3,V4 (1,3,2,0) 逆向深度优先搜索结果:V1,V3,V4,V2 强连通分量:{V1,V3,V4},{V2} V1 1 2 ^ V2 ^ V3 2 2 3 ^ ^ V4 3 ^ 3 1 ^ 3 2 ^ ^ Prof. Q. Wang

64 【例】以深度优先搜索方法从 出发遍历图, 建立深度优先生成森林。
【例】以深度优先搜索方法从 出发遍历图, 建立深度优先生成森林。 A Directed graph A B C D E F G A B D E C F G Depth-first spanning forest Prof. Q. Wang

65 Contents Definition and notations of graph Storage structure of graph
Graph traversal Connectivity analysis in undirected graph Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

66 7.4.3 Minimum cost spanning tree
Background: 假设要在n个城市之间建立通信网络，连通n个城市只需要n-1条线路，问题是如何铺设线路才能最节省资金。而在n个城市间最多可能有n(n-1)/2条线路，各个线路的费用是不一样的，怎么选择这n-1条线路，使总的耗费最少呢? 如果把城市当作图的顶点看待, 城市之间的通信线路看作图的顶点之间的边，边的权值就相当于通信线路的费用。 28 Lan tian Hu xian 10 14 16 Chang an Xi’an Zhou zhi 24 18 12 25 Lin tong Prof. Q. Wang Xian yang 22

67 7.4.3 Minimum cost spanning tree
Problem description: 在n个城市之间建立n-1条通信线路实际上就是图的一棵生成树。 Definition: 具有n个顶点的图的生成树的数目是很多的， 我们的目标是要选择一棵具有最小代价的生成树(Minimum Cost Spanning Tree, MCST)(简称最小代价生成树)。一棵生成树的代价就是该树上所有边的权值之和。 Prof. Q. Wang

68 Solutions & Algorithms: Prim算法： 不断生长 Kruskal算法： 不断合并
Property of MCST: 假设N＝(V, {E})是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值（代价）的边，其中uU, v  V-U，则必存在一棵包含边(u,v)的最小生成树。 Solutions & Algorithms: Prim算法： 不断生长 Kruskal算法： 不断合并 反证法。假设网N的任何一棵最小生成树都不包含边(u,v)。设T是连通网上的一棵最小生成树，当把边(u,v)加入T中时，T中必存在一条包含(u,v)的回路；那么在这条回路上任意删去除边(u,v)外的一条边(u’, v’)，这条回路上的所有顶点之间以及所有顶点与其他顶点之间必定仍然有通路，从而消除了回路，并生成了一棵新的生成树T’，而(u,v)的代价必定不高于(u’,v’)，所以T’是包含(u,v)的一棵最小生成树，这与假设矛盾。 Prof. Q. Wang

69 Prim algorithm 假设N＝(V, {E})是连通网，TE是N上最小生成树的边的集合。算法首先从U＝{u1} (u1  V), TE={ }开始，重复执行如下操作： 在所有u U，v V-U的边(u,v)E找一条代价最小的边(u1, v1)并入集合TE，同时v0并入U，直到U＝V为止。此时TE中必有n-1条边，T＝(V, {TE})即为N的最小生成树。 Example Prof. Q. Wang

70 Prof. Q. Wang

71 6 V1 V1 5 1 1 5 5 V2 5 V4 V2 V4 V3 V3 4 4 3 6 2 3 2 V5 V6 V5 V6 6 1 (V2) 2 (V3) 3 (V4) 4 (V5) 5 (V6) U V-U k Adjvex lowcost v1 6 v1 1 v1 5 {v1} {v2,v3,v4, v5,v6} 2 Adjvex lowcost v3 5 v1 5 v3 6 v3 4 {v2,v4, v5,v6} {v1,v3} 5 v3 5 v6 2 v3 6 Adjvex lowcost {v1,v3 v6} {v2,v4, v5} 3 Adjvex lowcost v3 5 v3 6 {v1,v3 v6,v4} {v2,v5} 1 Adjvex lowcost v2 3 {v1,v3 v6,v4,v2} {v5} 4 {v1,v3 v6,v4,v5} Adjvex lowcost {} Prof. Q. Wang

72 设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下∶
typedef struct { int start_vex, stop_vex; /* 边的起点和终点 */ AdjType weight; /* 边的权 */ } Edge; Prof. Q. Wang

73 void Prim (Graph *pgraph, Edge mst[]) { int i, j, min, vx, vy;
#define MAX 1e+38 void Prim (Graph *pgraph, Edge mst[]) { int i, j, min, vx, vy; float weight, minweight; Edge edge; for (i=0; i<pgraph->vexCount-1; i++) { mst[i].start_vex = 0; mst[i].stop_vex = i+1; mst[i].weight = pgraph->arcs[0][i+1]; } for (i=0; i<pgraph->vexCount-1; i++) { /* 共n-1条边 */ minweight=MAX; min=i; for (j=i; j<pgraph->vexCount-1; j++) /*从所有边(vx,vy) (vx∈U,vy∈V-U)中选出最短的边 */ if (mst[j].weight < minweight) { minweight = mst[j].weight; min = j; }/* mst[min]是最短的边(vx,vy) (vx∈U, vy∈V-U)，将mst[min]加 入最小生成树 */ 初始化 筛选最小值 Prof. Q. Wang

74 Swap current edge and min edge
edge = mst[min]; mst[min] = mst[i]; mst[i] = edge; vx = mst[i].stop_vex; /* vx为刚加入最小生成树 的顶点的下标 */ for (j=i+1; j<pgraph->vexCount-1; j++) { /* 调整mst[i+1]到mst[n-1] */ vy = mst[j].stop_vex; weight = pgraph->arcs[vx][vy]; if (weight < mst[j].weight) { mst[j].weight = weight; mst[j].start_vex = vx; } 更新 Prof. Q. Wang

75 Time complexity of Prim algorithm
如果顶点数为n, 则该算法的时间复杂度为O(n2)，与网中的边数无关，因此适合求边稠密的图。 Prof. Q. Wang

76 Another Implementation of Prim Algorithm
Auxiliary arrays lowcost[ ] lowest cost (u,v), uU, vV-U nearvex[ ] the serial number of vertex u for vV-U

77 Example Initialization
Lowest cost is (0,5), v=5, mark vertex 5 after selecting edge (0,5)

78 v = 5 Select vertex 5 and add in spanning tree v = 4 repeat

79 Initialization Iteration lowcost[ ] From adjacency matrix nearver[ ]
Set to 0 except the starting vertex (-1) Iteration lowcost [ ] v= nearvex[i]  -1 && min(lowcost[i]) selected edge is (nearvex[v], v), cost is lowcost[v] nearvex[ ] set nearvex[v] = -1, add ( nearvex[v], v, lowcost[v] ) into spanning tree

80 Final result (0, 5, 10), (5, 4, 25), (4, 3, 22), (3, 2, 12), (2, 1, 16), (1, 6, 14) //Prim algorithm void Graph<string, float> ::Prim ( MinSpanTree &T ) { int NumVertices = VerticesList.last; float * lowcost = new float[NumVertices]; int * nearvex = new int[NumVertices]; for ( int i = 1; i < NumVertices; i++ ) { lowcost[i] = Edge[0][i]; nearvex[i] = 0; } nearvex[0] = -1; 初始化

81 O(n2) for adjacency matrix
MSTEdgeNode e; for ( i = 1; i < NumVertices; i++ ) { float min = MAXNUM; int v = 0; for ( int j = 0; j < NumVertices; j++ ) if ( nearvex[j] != -1 && lowcost[j] < min ) { v = j; min = lowcost[j]; } if ( v ) { e.tail = nearvex[v]; e.head = v; e.cost = lowcost[v]; T.Insert (e); nearvex[v] = -1; for ( j = 1; j < NumVertices; j++ ) if ( nearvex[j] != -1 && Edge[v][j] < lowcost[j] ) { lowcost[j] = Edge[v][j]; nearvex[j] = v; } 筛选最小值 更新 Time Analysis O(n2) for adjacency matrix

82 Kruskal algorithm 设连通网N＝(V, {E})。令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝(V, { })，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T中，否则舍去此边而选择下一条代价最小的边，依次类推，直到T中所有顶点都在同一连通分量上为止。 Example Prof. Q. Wang

83 Kruskal算法的时间复杂度为O(eloge) (e为图的边)。适合求边稀疏的网。
用“堆”存放网中的边 连通分量等价类 构造T加入边的过程求等价类 Kruskal算法的时间复杂度为O(eloge) (e为图的边)。适合求边稀疏的网。 Prof. Q. Wang

84 1 2 3 4 5 6 7 8 Prof. Q. Wang

85 9 10 11 12 13 Result Prof. Q. Wang

86 7.4.4 Articulation point and Biconnected component (关节点和重连通分量)
关节点(Articulation point) ：如果删去某个图中的某个顶点v以及和v相关联的各边之后，将图的一个连通分量变成两个或两个以上的连通分量，则称顶点v为该图的一个关节点。 一个没有关节点的图称为重连通图(Biconnected graph)。 在重连通图上，任意一对顶点之间都至少存在两条路径。那么删去图中任意一个顶点及依附于该顶点的各边都不破坏图的连通性。若在连通图上至少删去k个顶点才能破坏图的连通性，则称该图的连通度为k。 关节点和重连通图在实际中有许多应用。如多个站点的通信网络可以看成是图的问题，该图的连通度越高，网络的可靠性也就越高，无论哪一个站点遭到破坏都不影响整个系统的正常使用。而在战争中破坏敌人的运输线，只需要破坏其关节点就可以了。 Prof. Q. Wang

87 例如下面的图中关节点为： v1, v2, v3 V1 V2 V3 V4 V5 V8 V6 V7 V1 V2 V3 V4 V5 V8 V6
Spanning tree Prof. Q. Wang

88 图中关节点为： A, B, D, G A A B L F C D E M F G H J B H D C I J K K E L M G I
1 5 A B L F 12 11 10 C D E M 13 6 F G H J B 8 9 7 H D C I J K 4 2 K E L M 3 G I Prof. Q. Wang

89 利用深度优先搜索可以求得图的关节点，并由此判断图是否为重连通图。
对于连通图的生成树中任一顶点v，其孩子结点为在它之后搜索到的邻接点，而其双亲结点和祖先结点为在它之前搜索到的邻接点。由深度优先生成树可得出两类关节点的特性： (1) 若生成树有两棵或两棵以上的子树，则此根结点必为关节点。如图中v1。 (2) 若生成树中某个非叶子结点v，其某棵子树的根或子树中其他结点均没有指向v的祖先结点的回边，则v为关节点。因为一旦删去v，该子树中的所有结点就和整棵树失去了联系。如图中v2, v3。 若对图重新定义DFS遍历时的访问函数visited，并引入一个新的函数low，则由一次深度优先遍历便可求得连通图中存在的所有关节点。 Prof. Q. Wang

90 定义visited[v]为深度优先遍历连通图时访问顶点v的次序号， 定义 w是顶点v在深度优先生成树上的孩子结点；
k是顶点v在深度优先生成树上由回边连接的祖先结点; (v,w) Edge， (v,k)  Edge， 若对于某个顶点v，存在孩子结点w且low[w] >=visited[v]，则 顶点v必为关节点。 由于visited[v]值即为v在深度优先生成树的前序序列中的 序号，那么在DFS函数中，令visited[v] = ++count就可以了。 low[v]的值可由后序遍历深度优先生成树求得，而v在后序序 列中的次序和前序遍历时退出DFS函数的次序相同，由此修改 DFS遍历的算法，即可得到求关节点的算法。如下所示： low[v] = Min visited[v], low[w], visited[k] Prof. Q. Wang

91 /* 求连通图的所有关节点： 函数中count, visited[], low[]都是全局变量 */ int count;
int visited[MAX_VERT_NUM]; int low[MAX_VERT_NUM]; void FindArticul (Graph g) { int i, v; ArcNode *p; count = 1; visited[0] = count; for (i=1; i<g.vexNum; i++) visited[i] = 0; /* 初始时所有顶点都没有访问 */ p = g.vexs[0].edgelist; v = p->endvex; DFSArticul (g, v); /* 从顶点v出发深度优先查找关节点 */ Prof. Q. Wang

92 if (count < g.vexNum) {/* 从根结点的第一个邻接点v出发不能搜索完 所有顶点，说明根结点有不只一棵子树。*/
printf ("%5d", g.vexs[0].data); while (p->nextedge) {/* 如果根结点还有其他未搜索的邻接点，继 续搜索 */ p = p->nextedge; v = p->endvex; if ( ! visited[v]) DFSArticul (g, v); } /* while */ } /* if */ } /* FindArticul() */ Prof. Q. Wang

93 void DFSArticul (Graph g, int v0) { int w, min; ArcNode *p;
visited[v0] = min = ++count; /* v0's visit order is 'count' */ for (p = g.vexs[v0].edgelist; p; p = p->nextedge) w = p->endvex; if ( ! visited[w]) { /* 如果没有访问则继续深度优先访问 */ DFSArticul (g, w); /* 求得w这棵子树上最低值 */ if (low[w] < min) min = low[w]; if (low[w] >= visited[v0]) printf("%5d", g.vexs[v0].data); } else if (visited[w] < min) /* 其邻接点已经被访问，则为祖先结点 */ min = visited[w]; } /* for */ low[v0] = min; /* 求得v0的最低值 */ } /* End of DFSArticul() */ Prof. Q. Wang

94 Time complexity analysis
第一个循环次数为n，然后DFSArticul函数和第二个循环都是搜索图中所有的边，其循环次数为e，因此总的时间复杂度为O(n+e)。 Prof. Q. Wang

95 Example A A B L F C D E F G H M J B I K J H D C L M K E G I 1 5 12 11
10 L F C D E 13 6 F G H M 8 J B I 9 K 7 J 4 H D C 2 L M 3 K E 若对于某个顶点v，存在孩子结点w且low[w] >=visited[v]，则顶点v必为关节点。 G I Prof. Q. Wang

96 Contents Shortest path Definition and notations of graph
Storage structure of graph Graph traversal Connected component and spanning tree Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

97 7.5 Shortest path (最短路径) 可以用图的结构来表示实际的交通网络，用顶点表示城市，边表示城市之间的交通联系。如果一位旅客想从A城到B城，希望选择中转次数最少的路线。如果在途中每一站都要换车，这个问题反映到图上就是求从A到B的边数最少的路径。 我们只需从A出发作广度优先搜索，一旦遇到B就终止，由此得到的广度优先生成树中，从根结点A到结点B的路径即为中转次数最少的路径。 有时，有些顾客可能更关心交通费用，有些则更关心速度和里程。为了在图上表示有关的信息，可对边赋以权值，用来表示城市间的距离或途中所需时间或交通费用。此时路径长度的度量就是路径上边的权值之和。 Prof. Q. Wang

98 7.5.1 Dijkstra algorithm 从源点到某个顶点的路径可能有多条，问题是怎么选择一条路径最短的路径。
始点 终点 最短路经 路径长度 v0 v v2 (v0,v2) 10 v3 (v0,v4,v3) 50 v4 (v0,v4) 30 v5 (v0,v4,v3,v5) 60 V5 V0 V4 V1 V3 V2 100 60 20 10 30 5 50 Prof. Q. Wang

99 Dijkstra（迪杰斯特拉）提出了一个按路径长度递增的次序产生最短路径的算法（贪心算法）：
首先，引入辅助向量D，它的每个分量D[i]表示当前所找到的从始点v0到每个找到vi的最短路径的长度。它的初始状态为：若从v0到vi有弧，则D[i]为弧上的权值；否则为无穷大。显然长度为 D[j] = Min { D[i] | vi V} 的路径就是从v出发的长度最短的一条路径，此路径为(v,vj)。 那么下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk, 则这条路径或者是(v, vk)，或者是(v, vj, vk)。 一般情况下，假设S为已求得最短路径的终点的集合，可以证明： i 下一条最短路径(设终点为x)或者是弧(v, x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。 Prof. Q. Wang

100 因此，在一般情况下，下一条长度次短的最短路径的长度必然是： D[j] = Min{D[i] | vi  V-s}
反证法：假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比从v到x的路径长度更短的路径。但这是不可能的，因为我们是按路径长度递增的次序来产生各最短路径的。故长度比此路径短的所有路径均已产生，它们的终点必定在S中。 因此，在一般情况下，下一条长度次短的最短路径的长度必然是： D[j] = Min{D[i] | vi  V-s} 其中D[i]或者是弧(v, vi)上的权值，或者是D[k](vk  S)和弧(vk,vi)上的权值之和。 根据上面的分析，可以得到如下的Dijkstra算法： i Prof. Q. Wang

101 D[i] = arcs[LocateVex(pG, v0)][i] viV (2) 选择vj, 使得
(1) 假设用邻接矩阵来表示带权有向图，arc[i][j]表示弧(vi, vj)上的权值。若(vi, vj)不存在，则置arc[i][j]为计算机上允许的最大值。S为已找到的从v出发的最短路径的集合，其初始状态为空集。那么从v0出发到图上其余各顶点vi可能达到的最短路径长度的初值为： D[i] = arcs[LocateVex(pG, v0)][i] viV (2) 选择vj, 使得 D[j] = Min{D[i] | vi  V-s} 那么vj就是当前求得的一条从v出发的最短路径的终点。令 S ＝ S {j} (3) 修改从v出发到集合V－S上任一顶点vk可达的最短路径长度。如果： D[j] + arcs[j][k] < D[k] 则修改D[k]为 D[k] ＝ D[j] + arcs[j][k] (4) 重复(2)~(3)共n-1次，由此求得从v到图上其余各顶点的最短路径长度递增的序列。 Prof. Q. Wang

102 具体实现如下：设置一个数组dist[n]，用于存放顶点v0到其它各顶点的最短路径及其最短路径长度，其存储结构为：
typedef struct { VexType vertex; /* 顶点信息 */ AdjType length; /* 最短路径长度 */ int prevex; /* 从v0到达vi(i=1,2,…n-1)的最短路径上vi 的前趋顶点 */ } Path; Prof. Q. Wang

103 void dijkstra (Graph graph, Path dist[])
#define MAX 1e+38 void dijkstra (Graph graph, Path dist[]) { int i, j, minvex; AdjType min; dist[0].length=0; dist[0].prevex=0; dist[0].vertex=graph.vexs[0]; graph.arcs[0][0]=1; /* 表示顶点v0在集合U中 */ for (i=1; i<graph.vexCount; i++) { /* 初始化集合V-U中顶点的距离值 */ dist[i].length=graph.arcs[0][i]; dist[i].vertex=graph.vexs[i]; if (dist[i].length!=MAX) dist[i].prevex=0; else dist[i].prevex= -1; } min=MAX; minvex=0; for (j=1; j<graph.vexCount; j++) /*在V-U中选出距离值最小顶点*/ if ( (graph.arcs[j][j]==0) && (dist[j].length<min) ) { min=dist[j].length; minvex=j; 初始化 筛选最小值 Prof. Q. Wang

104 if (minvex==0) /* 从v0没有路径可以通往集合V-U中的顶点 */ break;
graph.arcs[minvex][minvex]=1; /* 集合V-U中路径 最小的顶点为minvex */ for (j=1; j<graph.vexCount; j++) { /* 调整集合V-U中的顶点的最短路径 */ if (graph.arcs[j][j]==1) continue; if (dist[j].length>dist[minvex].length+graph.arcs[minvex][j]) { dist[j].length=dist[minvex].length+graph.arcs[minvex][j]; dist[j].prevex=minvex; } 更新 Prof. Q. Wang

105 Example V5 V0 V4 V1 V3 V2 100 60 20 10 30 5 50 ∞ 无 v1 ∞ ∞ ∞ ∞ 10
90 (v0,v4,v5) 60 (v0,v4,V3,v5) v5 vj v2 v4 v3 v5

106 Time complexity analysis
第一个循环：O(n) 第二个循环：(n-1)*(n-1+n-1)  O(n2) 总的时间复杂度为O(n2) Prof. Q. Wang

107 7.5.2 任意顶点间最短路径 Floyd algorithm
解决办法之一：每次以一个顶点为源点，重复执行Dijkstra算法n次。 时间复杂度为O(n3) Prof. Q. Wang

108 Floyd algorithm n个顶点的有向带权图，顶点v0,v1,v2,…,vn-2,vn-1 直接连接arcs[i][j] vi vj
中间顶点的序号 不大于0的最短路径 中间顶点的序号 不大于0的最短路径 v0 v1 中间顶点的序号 不大于k-1的最短路径 中间顶点的序号 不大于k-1的最短路径 D(k-1)[i][k] D(k-1)[k][j] vk 中间顶点的序号 不大于n-2的最短路径 中间顶点的序号 不大于n-2的最短路径 vn-1 Prof. Q. Wang

109 Floyd algorithm 假设求从顶点vi到vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度为arcs[i][j]的路径，但该路径不一定是最短路径。 首先考虑路径(vi,v0,vj)是否存在（即判别弧(vi,v0)和(v0,vj)是否存在）。 如果存在，再比较(vi,vj)和(vi,v0,vj)的长度，并取其较短者作为从vi到vj的中间顶点的序号不大于0的最短路径。 假如在路径上再增加一个顶点v1，也就是说，如果(vi,…,v1)和(v1,…,vj)分别是当前找到的中间顶点序号不大于0的最短路径，那么(vi,…,v1,…,vj)就有可能是从顶点vi到vj的中间顶点序号不大于1的最短路径。将它从已经得到的从vi到vj中间得到序号不大于0的最短路径比较，从中选出长度最小的路径然后再增加一个得到v2，继续试探。 Prof. Q. Wang

110 这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。 我们用n阶矩阵来存放所有顶点之间的最短路径。
在一般情况下，若(vi,…,vk)和(vk,…,vj)分别是从vi到vk和从vk到vj的中间顶点序号不大于k-1的最短路径，则将(vi,…,vk,…,vj)和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径比较，其长度较短者便是从vi到vj的中间顶点序号不大于k的最短路径。 这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。 我们用n阶矩阵来存放所有顶点之间的最短路径。 初始化 D(-1)[i][j] = arcs[i][j] 加入顶点vk后，有 D(k)[i][j] = Min{D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j]} 0<= k <= n-1 该算法的时间复杂度为O(n3)，为什么? Prof. Q. Wang

111 6 例子 B A 4 V1 V2 3 ∞ 0 11 2 3 C V3 D D(-1) D(0) D(1) D(2) 1 2 1 2 1 2 1 2 0(A) 4 11 4 11 4 6 4 6 1(B) 6 2 6 2 6 2 5 2 2(C) 3 ∞ 3 7 3 7 3 7 P P(-1) P(0) P(1) P(2) AB AC AB AC AB ABC AB ABC 1 BA BC BA BC BA BC BCA BC 2 CA Prof. Q. Wang CA CAB CA CAB CA CAB

112 Example of Floyd Algorithm Prof. Q. Wang

113 Example of Floyd Algorithm Prof. Q. Wang

114 Example of Floyd Algorithm Prof. Q. Wang

115 Example of Floyd Algorithm Prof. Q. Wang

116 Example of Floyd Algorithm Prof. Q. Wang

117 这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。 我们用n阶矩阵来存放所有顶点之间的最短路径。
在一般情况下，若(vi,…,vk)和(vk,…,vj)分别是从vi到vk和从vk到vj的中间顶点序号不大于k-1的最短路径，则将(vi,…,vk,…,vj)和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径比较，其长度较短者便是从vi到vj的中间顶点序号不大于k的最短路径。 这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。 我们用n阶矩阵来存放所有顶点之间的最短路径。 初始化 D(-1)[i][j] = arcs[i][j] 加入顶点vk后，有 D(k)[i][j] = Min{D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j]} 0<= k <= n-1 该算法的时间复杂度为O(n3)，为什么? Prof. Q. Wang

118 AdjType a[MAXVEX][MAXVEX]; /* 矩阵A，存放每对顶点间最短路径长度 */
typedef struct { AdjType a[MAXVEX][MAXVEX]; /* 矩阵A，存放每对顶点间最短路径长度 */ int nextvex[MAXVEX][MAXVEX]; /* nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值 */ } ShortPath; #define MAX 1e+38 Prof. Q. Wang

119 void floyd (Graph *pgraph, ShortPath *ppath) { int i, j, k;
for (i=0; i<pgraph->vexCount; i++) for (j=0; j<pgraph->vexCount; j++) { if (pgraph->arcs[i][j] != MAX) ppath->nextvex[i][j] = j; else ppath->nextvex[i][j] = -1; ppath->a[i][j]=pgraph->arcs[i][j]; } for (k=0; k<pgraph->vexCount; k++) if ( (ppath->a[i][k] >= MAX) || (ppath->a[k][j] >= MAX) ) continue; if (ppath->a[i][j] > (ppath->a[i][k] + ppath->a[k][j]) ) { ppath->a[i][j] = ppath->a[i][k] + ppath->a[k][j]; ppath->nextvex[i][j]=ppath->nextvex[i][k]; 初始化 迭代计算 Prof. Q. Wang

120 Analysis Path Adjacency matrix used 10, a[1][0]=11, path[1][0]=2
表示 1-> … ->2->0 path[1][2]=3 表示 1->… ->3 ->2->0 path[1][3]=1 表示 1->3 Conclusion: path:1->3->2->0, length=11 Adjacency matrix used Prof. Q. Wang

121 Practical (5) Shortest path Prof. Q. Wang

122 Lisbon Madrid 75 450 Prague Berlin 55 350 Madrid Lisbon 55 450
Madrid Paris Madrid Bern Paris London Paris Bern Paris Vienna Paris Brussels Paris Madrid London Paris Rome Bern Bern Rome Bern Paris Bern Sarajevo Bern Madrid Brussels Paris Brussels Amsterdam Brussels Berlin Amsterdam Brussels Amsterdam Copenhagen Amsterdam Berlin Copenhagen Amsterdam Berlin Amsterdam Berlin Brussels Berlin Prague Berlin Warsaw Prague Berlin Prague Vienna Prague Warsaw Warsaw Berlin Warsaw Bucharest Warsaw Prague Vienna Prague Vienna Paris Vienna Budapest Budapest Vienna Budapest Bucharest Budapest Sarajevo Sarajevo Bern Sarajevo Sofia Sarajevo Skopja Sarajevo Budapest Sofia Sarajevo Sofia Skopja Skopja Sofia Skopja Tirane Skopja Sarajevo Tirane Athens Tirane Skopja Athens Tirane Bucharest Budapest Bucharest Warsaw Prof. Q. Wang

123 Contents Topological sorting & Critical path
Definition and notations of graph Storage structure of graph Graph traversal Connected component and spanning tree Mini spanning tree Shortest path Topological sorting & Critical path Prof. Q. Wang

124 7.6 Directed acyclic graph (有向无环图及其应用)
定义： 一个无环的有向图称作有向无环图(Directed acyclic graph: DAG)。 有向无环图是描述含有公共子式的表达式的有效工具。 如对下述表达式： ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 可以用二叉树来表示。但实际上该表达式中有相同的子表达式，在二叉树中它们会重复出现，这样就比较浪费空间。如果用有向无环图则可以实现对相同子式的共享，从而节省存储空间。 Prof. Q. Wang

125 ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)
＋ * * * ＋ (c+d)*e e + + e * c d a b b + c d * + e a b c d c d (c+d)*e c+d Prof. Q. Wang

126 Examples Directed tree DAG Directed graph Prof. Q. Wang

127 有向图的环 检查一个有向图是否存在环要比无向图复杂。
对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环； 而对于有向图，这条回边有可能是指向深度优先生成森林中另一棵生成树上的顶点的弧。 但是，如果从有向图上某个顶点v出发的遍历，在DFS(v)结束之前出现一条从顶点u到顶点v的回边，则有向图中必定存在包含顶点v和u的环。 Prof. Q. Wang

128 DAG中的研究问题 有向无环图也是描述一项工程或系统的进行过程的有效工具。绝大多数的工程都可分为若干个称做活动(Activity)的子工程，而这些子工程之间，通常都受着一定条件的约束。对整个工程和系统，人们关心的是两个方面的问题： 一是工程能否顺利进行； 二是工程完成所必须的最短时间，对应于有向图，即为进行拓扑排序和求关键路径的操作。 Prof. Q. Wang

129 7.6.1 Topological Sort (拓扑排序)
定义：如果在AOV(Activity on Vertex)网中，从顶点vi到顶点vj存在一条路径，则在线性序列中，顶点vi一定排在顶点vj之前。具有这种性质的线性序列称为拓扑序列，构造拓扑序列的操作称为拓扑排序。 偏序关系：集合X上的关系R是自反的、反对称的、传递的，则称R是集合X上的偏序关系。 全序关系：设R是集合X上的偏序，如果对每个x, y∈X必有xRy或yRx，则称R是集合X上的全序关系。 V2 V1 V4 V3 偏序 V1 V3 V2 V4 全序 Prof. Q. Wang

130 一个表示偏序的有向图可用来表示一个流程图，它或者是
V2 V1 V4 V3 偏序 V1 V3 V2 V4 全序 一个表示偏序的有向图可用来表示一个流程图，它或者是 一个施工流程图，或者是一个产品生产流程图。图中每一条有向边表示两个子工程之间的次序关系(领先关系)。这种用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity on Vertex Network)，简称AOV-网。 在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱，j就是i的后继。在AOV-网中不应该出现有向环，因为出现有向环，就意味着某个活动以自己为先决条件。因此，对给定的AOV-网需首先判断网中是否有环。 Prof. Q. Wang

131 检测的办法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在其拓扑有序序列中，则该AOV-网必定不存在环。
例子：对下面的图的拓扑序列为 (C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8) C4 C5 C1 C2 C3 C7 C12 C9 C10 C11 C6 C8 Prof. Q. Wang

132 V6, V1, V4, V3, V2, V5 如何进行拓扑排序呢？ (1) 在有向图中选取一个没有前驱的顶点且输出之；
(2) 从图中删去该顶点和所有以它为尾的弧。 重复(1)~(2)直至所有顶点都已输出，或者当前图中不存在无前驱的顶点为止，后一种情况说明图中存在环。 举例： V1 V2 V4 V3 V6 V5 V2 V3 V5 V1 V4 V5 V2 V3 V4 V2 V3 V5 V2 V5 V5 V6, V1, V4, V3, V2, V5 Prof. Q. Wang

133 算法实现： 需要一个数组存放所有顶点的入度（入度为0说明该顶点没有前驱）。而删去该顶点及以它为尾的弧，只要使该弧的弧头顶点的入度减1就可以了。由于在图中入度为0的顶点数可能较多，为例避免重复检测入度为0的顶点，可设一个栈来存放所有入度为0的顶点。 算法细节如下： 说明：采用邻接表作为存储结构 Prof. Q. Wang

134 Status FindInDegree (ALGraph g, int *inDegree) { /* 求出图中所有顶点的入度 */
ArcNode *p; for (i=0; i<MAX_VERT_NUM; i++) inDegree[i] = 0; for (i=0; i<g.vexNum; i++) { p = g.vexs[i].edgelist; while (p) { ++inDegree[p->endvex]; p = p->nextedge; } return OK; } /* End of FindInDegree() */ Prof. Q. Wang

135 初始化 Status TopoSort (ALGraph g) {
int inDegree[MAX_VERT_NUM]; /* 存储所有顶点的入度 */ SeqStack s; /* 存放入度为0的顶点 */ int i, k, count = 0; /* count 对输出顶点计数 */ ArcNode *p; FindInDegree (g, inDegree); /* 得到所有得到的入度 */ InitStack (&s); for (i=0; i<g.vexNum; i++) /* 把所有入度为0的顶点入栈 */ if (!inDegree[i]) Push (&s, i); 初始化 Prof. Q. Wang

136 迭代检测 while (!IsStackEmpty(s)) { Pop (&s, &i); /* 输出i号顶点并计数 */
printf ("%d\n", i, g.vexs[i].vertex); ++count; for (p=g.vexs[i].edgelist; p!=NULL; p=p->nextlist) { /* 对i号顶点的每个邻接点的入度减1 */ k = p->endvex; if (!(--inDegree[k])) /* 入度为0，入栈 */ Push(&s, k); } /* for */ } /* while */ if (count < g.vexNum) return ERROR; else return OK; } /* End of TopoSort() */ 迭代检测 Prof. Q. Wang

137 Question & thinking 逆拓扑排序 寻找出度为0的顶点 V5, V2, V3, V4, V1, V6 V6, V1, V4,
Prof. Q. Wang

138 拓扑排序的实现 C0 C1 C2 C C4 C 1 2 3 4 5 3 0 5 0 C0 C1 C2 C3 C4 C5

139 Efficiency analysis 算法的时间效率： (1) 建立各顶点的入度的时间复杂度为O(e);
(2) 建立入度为0的栈的时间复杂度为O(n); (3) 在拓扑排序过程中，若有向图无环，则每个顶点进栈一次，出栈一次，入度减1的操作在while循环总共执行e次(why?).\ 所以，总的时间复杂度为O(n+e). 如果有向图有环又怎么样？ 当有向图无环时，也可利用深度优先搜索进行拓扑排序，因为图中无环，则由图中某个顶点出发进行深度优先搜索时，最先退出DFS函数的顶点即为出度为0的顶点，是拓扑有序序列中最后一个顶点，由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。 Prof. Q. Wang

140 Critical path (关键路径) AOE-无环图网(Activity on Edge Network)：即用边表示活动的网，是带权的有序无环图，其中顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程完成的时间。如图所示： V2 V1 V3 V5 V7 V8 V9 V4 V6 a6=2 a1=6 a4=1 a7=9 a10=2 a11=4 a9=4 a3=5 a2=4 a5=1 a8=7 AOE网 Prof. Q. Wang

141 由于整个工程只有1个开始点，1个完成点，因此在正常情况下(无环)只有1个入度为0 的点(源点)和1个出度为0的点(汇点)。
对AOE-网，常考虑如下的情况： (1) 完成整个工程至少需要多少时间； (2) 哪些活动是影响工程进度的关键。 a1=6 V2 a4=1 V7 a10=2 a7=9 V1 a2=4 V5 a8=7 V9 a5=1 V3 V8 a11=4 a3=5 a6=2 a9=4 V4 V6 AOE-网 Prof. Q. Wang

142 事件Vi的最早发生时间：从开始点v1到vi的最长路径长度。用ee(i)表示。
由于有些工程可并行地进行，完成所有工程的最短时间即为从开始点到完成点的最长路径的长度（路径长度指的是路径上各持续时间之和）。路径最长的路径叫关键路径(Critical Path)。 事件Vi的最早发生时间：从开始点v1到vi的最长路径长度。用ee(i)表示。 事件Vi的最迟发生时间：在不推迟整个工期的前提下，事件vi允许的最晚发生时间。用le(i)表示。 活动ai的最早开始时间：即为ai的弧尾顶点(事件)的最早发生时间。用e(i)表示。 活动ai的最迟开始时间：在保证不推迟整个工程的完成时间的的前提下，活动ai的最迟开始时间。用l(i)表示。 Prof. Q. Wang

143 l(i) - e(i)意味着完成活动ai的时间余量。 关键活动：l(i) = e(i)的活动。
显然，关键路径上的所有活动都是关键活动。因此，提前非关键活动并不能加快工程的进度。所以分析关键路径的目的是判别哪些是关键活动，以便提高关键活动的工序，缩短整个工期。 判别关键活动就是要找l(i) ＝ e(i)的活动，因此必须首先求出l(i) 和 e(i)，为此，必须先求出事件的最早发生时间ee(j)和最迟发生时间le(j)。如果活动ai由弧<j, k>表示，其持续时间为dur(<j, k>)，则有如下的关系： e(i) = ee(j) l(i) = le(k) - dur(<j, k>) 所以下面的问题就是如何求ee(j)和le(j)了。可以如下进行： Prof. Q. Wang

144 j i （1）ee(0) = 0; ee(j) = Max{ee(i) + dur(<i, j>)}
其中<i, j>T, j = 1,2,…,n-1, T是所有以顶点 j为弧头的弧的集合。 i j 考虑 j 的所有前驱顶点 i Prof. Q. Wang

145 i j （2）从le(n-1) = ee(n-1)起向前递推： le(i) = Min{le(j) - dur(<i, j>)}
其中<i, j>S, i = n-2, n-1, ..., 0, S是所有以顶点 i 为弧尾的弧的集合。 这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。 j i 考虑 i 的所有后继顶点 j Prof. Q. Wang

146 (4) 根据个各顶点的ee和le值，求每条弧s的e(s)和l(s)。若某条弧满足e(s) == l(s)，则s为关键活动。
计算关键路径的算法： (1) 输入e条弧，建立AOE-网。 (2) 从源点v0出发，令ee[0] = 0, 按拓扑有序求各顶点的最早发生时间ee[i](1<=i<n)，如果得到的拓扑序列中顶点个数小于网中顶点数n，说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。 (3) 从汇点vn出发，令le[n-1] = ee[n-1]; 按逆拓扑有序求其余各顶点的最迟发生时间le[i](n-2>=i>=2); (4) 根据个各顶点的ee和le值，求每条弧s的e(s)和l(s)。若某条弧满足e(s) == l(s)，则s为关键活动。 Prof. Q. Wang

147 由于求关键路径需要拓扑序列和逆拓扑序列，因此需要利用拓扑排序的方法。对拓扑排序稍加修改即可求得各顶点的ee和le值。
修改方法如下： (1) 对ee[i]设初值0。 (2) 增加求vj的直接后继vk的最早发生时间的操作： 若ee[j]+dur(<j, k>) > ee[k], 则ee[k] = ee[j]+dur(<j, k>). (3) 为了求逆拓扑序列，只需要把拓扑序列入栈，那么出栈的序列即为逆拓扑序列。 Prof. Q. Wang

148 Critical path: a1->a4->a8->a11
a2 3 a3 8 12 a4 a5 4 9 a6 7 a7 18 22 a8 20 a9 a10 10 a11 30 a12 14 19 a13 15 a14 26 29 activity e(k) l(k) e(k)-l(k) events ee(i) le(i) V1 V2 8 8 V3 4 7 V4 18 22 V5 20 20 V6 7 10 V7 14 19 V8 15 18 V9 30 30 V10 26 29 V11 45 45 V4 V2 V9 dest V1 V5 V11 source V3 V7 Critical path: a1->a4->a8->a11 Critical activities: a1, a4, a8, a11 V10 V6 V8

149 初始化 Status CriticalPath (ALGraph g) {
int inDegree[MAX_VERT_NUM]; /* 存放各顶点的入度 */ SeqStack t, s; /* t-存放拓扑有序序列; s-存放入度为0的顶点 */ int count = 0; /* 计数输出顶点 */ int ee[MAX_VERT_NUM]; /* 各顶点的最早发生时间 */ int le[MAX_VERT_NUM]; /* 各顶点的最迟发生时间*/ int i, j, k, ee, el; int dur; /* 临时存放一个活动的持续时间 */ char tag; ArcNode *p; FindInDegree (g, inDegree); InitStack (&s); InitStack (&t); count = 0; for (i=0; i<MAX_VERT_NUM; i++) /* 初始化最早发生时间 */ ee[i] = 0; for (i=0; i<g.vexNum; i++) /* 所有入度为0的顶点入栈 */ if (!inDegree[i]) Push (&s, i); 初始化 Prof. Q. Wang

150 拓扑排序 while ( !IsStackEmpty (s)) { /* 求所有顶点最早发生时间 */
Pop (&s, &j); //从栈s中出来 Push (&t, j); //进入栈t ++count; for (p=g.vexs[j].edgelist; p!=NULL; p=p->nextedge) { k = p->endvex; if (--inDegree[k] == 0) Push(&s, k); if (ee[j]+(*(p->weight)) > ee[k]) ee[k] = ee[j] + (*(p->weight)); } /* for */ } if (count < g.vexNum) /* 有向网存在回路 */ return ERROR; 拓扑排序 Prof. Q. Wang

151 逆拓扑排序 /* 求各顶点的最迟发生时间 */
for (i=0; i<MAX_VERT_NUM; i++) /* 初始化为最大值 */ le[i] = ee[g.vexNum-1]; while ( !IsStackEmpty (t) ) { /* 求各顶点最迟发生时间 */ for (Pop(&t, &j), p=g.vexs[j].edgelist; p!=NULL; p = p->nextedge) { k = p->endvex; dur = *(p->weight); if (le[k] - dur < le[j]) le[j] = le[k]-dur; } } /* while */ 逆拓扑排序 Prof. Q. Wang

152 for (j=0; j<g.vexNum; j++)
for (p=g.vexs[j].edgelist; p!=NULL; p=p->nextedge) { k = p->endvex; dur = *(p->weight); /* 持续时间 */ ee = ee[j]; /* <j,k>的最早发生时间 */ el = le[k]-dur; /* <j,k>的最迟发生时间 */ tag = (ee == el)? '*‘ : ' '; printf ("%d->%d, During time is %d, ee = %d, el = %d, %c\n", j+1, k+1, dur, ee, el, tag); } } /* End of CriticalPath() */ Prof. Q. Wang

153 Analysis 该算法的时间复杂度为O(n+e).
前面介绍拓扑排序的时候已经说明拓扑排序可以用DFS来实现, 因此这儿求ee和le也可以用DFS来实现, 时间复杂度也为O(n+e). 实践证明，用AOE-网来估算某些工程完成的时间是非常有用的。但网中各活动是互相相关的，任何一项活动的持续时间的改变都可能导致关键路径的改变。因此，只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。 另一方面，若网中存在几条关键路径，则必须同时提高在几条关键路径上的活动的速度才能缩短整个工期。 Prof. Q. Wang

154 Assignments (6) P , 7.7 P , 7.11 P P , 7.42 Prof. Q. Wang

155 Conclusion 图是一种复杂的非线性结构。 图的基本概念 图的邻接矩阵和邻接表 图的遍历 最小生成树 最短路径 拓扑排序及关键路径
重点是掌握图的存储表示和各种算法的基本思想。 Prof. Q. Wang

156 A funny story Prof. Q. Wang

157 Son My father My father Daughter I My wife I My wife My son Daughter
Prof. Q. Wang

158 Conclusion: Prof. Q. Wang