Microsoft PowerPoint - DS_Ch6_EN [兼容模式]

Transcription

1 Data Structure Ch.7 Graph Dr. He Emil Huang School of Computer Science and Technology Soochow University 苏 州 大 学 计 算 机 科 学 与 技 术 学 院 网 络 工 程 系 本 章 ppt 与 教 材 对 应 情 况 本 章 涉 及 所 有 内 容 涵 盖 了 教 材 以 下 章 节 Chapter (P569~P597) Main Content Graph Definition 图 的 定 义 Graph Traversal 图 的 遍 历 Topological Sorting 拓 扑 排 序 A Greedy Algorithm: Shortest Paths 最 短 路 径 贪 心 算 法 简 介 Minimal Spanning Trees 最 小 生 成 树 P59 in our textbook N. Wirth 曾 引 用 过 一 个 故 事 : 我 和 一 个 寡 妇 结 婚 了, 她 有 一 个 已 经 长 大 的 女 儿 我 父 亲 经 常 去 拜 访 我 们, 他 与 我 的 继 女 相 爱 并 结 婚 了 因 此 我 的 父 亲 成 了 我 的 女 婿, 我 的 继 女 也 成 了 我 的 母 亲 几 个 月 后, 我 的 妻 子 生 了 一 个 儿 子, 他 也 成 了 我 父 亲 的 内 弟, 也 成 了 我 的 叔 叔 我 父 亲 的 妻 子, 也 就 是 我 的 继 女, 也 有 了 一 个 儿 子 因 此 我 有 了 一 个 弟 弟, 同 时 他 也 是 外 孙 我 的 妻 子 是 我 的 祖 母, 因 为 她 是 我 母 亲 的 母 亲 因 此 我 是 我 妻 子 的 丈 夫, 同 时 也 是 她 的 继 孙, 换 句 话 说, 我 是 我 自 己 的 祖 父 图 的 应 用 实 例 地 图 网 页 信 息 电 路 任 务 调 度 商 业 交 易 配 对 计 算 机 网 络 社 交 网 络 Graph is a kind of complex nonlinear structure Application scenarios: artificial intelligence engineering mathematics biology computer science The logical relationship among nodes 结 点 间 的 逻 辑 关 系 : any two nodes may be related 任 意 两 个 元 素 之 间 都 可 能 相 关 5 6

2 Instances of Graphs 概 念 concept 8 7. Concept Def:graph is composed of two sets, G=(V, E) V(G): vertex set finite non-empty set of vertices E(G): edge set finite set of ordered pairs ( 序 偶 对 ) of vertices in V Undirected graph: edge is constituted by unordered pairs ( 无 序 对 ) of vertices (V i, V j ) and (V j, V i ) represent the same edge, which is called the undirected edge Directed graph: edge is constituted by ordered pairs ( 有 序 对 ) of vertices <V i, V j > and <V j, V i > represent different directed edges arc tail V i starting point, arc head V j ending point 9 7. Concept Instance G =(V,E ) V =V(G )={v, v, v 3, v E =E(G )={<v, v >, <v, v 3 >, <v 3, v >, <v, v > G =(V,E ) V =V(G )={v, v, v, v 3 E =E(G )={(v, v ), (v, v ), (v, v 3 ), (v, v ), (v, v 3 ) 7. Concept Convention: we only discuss simple graph ( 本 章 我 们 约 定 只 讨 论 简 单 图 ) 反 身 边 ( 自 环 ) is not allowed that is to say, if (v i, v j )or <v i, v j > E, then v i v j parallel edges ( 平 行 边 ) are not allowed in E(G), repeated elements are not allowed 7. Concept Relationship between vertices and edges assume that V = n, E = e Undirected graph: e n(n-)/ when e=, which is null graph 零 图 (E=Φ) when e=n(n-)/, which is (undirected) complete graph there exists an edge between any two vertices in complete graph Directed graph: e n(n-) when e=n(n-), which is directed complete graph 3 Sparse graph, dense graph: 边 少 边 多 :e < nlgn?

3 7. Concept Sparse graph, dense graph: 亦 可 从 直 观 感 受 去 认 识 7. Concept adjacency ( 邻 接 ) and association ( 关 联 ) (lie on, 依 附 ) if e =(v i, v j ) E, 则 v i 和 v j 互 为 邻 接 点 v i and v j are adjacent 若 e =<v i, v j > E, 则 v i 邻 接 到 v j, v j 邻 接 自 v i 边 e 和 e 关 联 ( 依 附 ) 于 顶 点 v i 和 v j it is difficult to define precursor and successor Degree (valence) of the vertex 顶 点 的 度 undirected graph: 关 联 于 顶 点 的 边 数 D(v) 例 v V(G 3 ), D(v)= directed graph: 出 度 以 v 为 起 点 的 边 数 OD(v) D(v)=ID(v)+OD(v) 入 度 以 v 为 终 点 的 边 数 ID(v) 3, for directed or undirected graph, all are correct 7. Concept Subgraph ( 子 图 ) Assume that G=(V, E) is a graph, V V, E Eand vertices associated with edges in E are all in V,thenG =(V,E ) is also graph, which is called the subgraph of G G=({v,v,v 3,v,, { (v,v ), (v,v 3 ), (v 3,v )) G =({v,v, {(v,v ), (v 3,v )), is not the subgraph of G, because it is not a graph 5 7. Concept Path if a vertex sequence v p, v i, v i,,v im, v q exists, which makes (v p, v i ), (v i, v i ),,(v im, v q ) E(G) then we can say that there is a path from v p to v q the number of edges passed by is called the path length the definition in directed path is similar Simple path except starting point and end point, path whose other vertices are all different 除 了 起 点, 终 点 外 其 余 顶 点 均 不 同 的 路 径 简 单 回 路 (cycle 环 ) simple path whose starting point and end point are the same 6 7. Concept 有 根 图 Root graph In directed graph G, if v V and there exist paths from v to all other vertices, then v is called the root, and G is root graph Connectivity ( 连 通 ), connected graph ( 连 通 图 ), connected component ( 连 通 分 量 ) assume that G is undirected graph in G, if there exists a path from v i to v j, then v i and v j are connected if v i,v j V(G), v i and v j are all connected, then G is connected graph 3 in undirected graph, the maximal connected subgraph ( 极 大 连 通 子 图 ) is called connected component 连 通 图 仅 有 一 个 连 通 分 量, 即 自 身 7. Concept Strongly connected graph ( 强 连 通 图 ) assume that G is directed graph, v i,v j V(G), if path from v i to v j and path from v j to v i are all exist, then G is called strongly connected graph ( 强 连 通 图 ) n 个 顶 点 的 强 连 通 图 至 少 有 几 条 边? 有 向 完 全 图 是 强 连 通 图? Strongly connected component ( 强 连 通 分 量 ) the maximal strongly connected subgraph ( 极 大 强 连 通 子 图 ) of directed graph is called the strongly connected component ( 强 连 通 分 量 ) strongly connected graph ( 强 连 通 图 ) has only one strongly connected component ( 强 连 通 分 量 ) for example:g is not a strongly connected graph ( 强 连 通 图 ), which has two strongly connected components ( 强 连 通 分 量 ) Weighted graph ( 加 权 图 ) vertices or edges with weights 顶 点 或 边 上 带 权 3

4 7. Concept Anatomy of a graph 7. Concept A tree is an acyclic connected graph. A disjoint set of trees is called a forest. A spanning tree of a connected graph is a subgraph that contains all of that graph s vertices and is a single tree. A spanning forest of a graph is the union of spanning trees of its connected components. 树 是 无 环 连 通 图 互 不 相 连 的 树 组 成 的 集 合 称 为 森 林 连 通 图 的 生 成 树 是 它 的 一 幅 子 图, 它 含 有 图 中 所 有 的 顶 点 且 是 一 棵 树 图 的 生 成 森 林 是 它 所 有 连 通 子 图 的 生 成 树 的 集 合 7. Concept 一 棵 树 生 成 树 森 林 Graphs: Definitions A graph G consists of a set V, whose members are called the vertices( 顶 点 ) of G, together with a set E of pairs of distinct vertices from V. The pairs in E are called the edges( 边 ) of G. If e=(v,w) is an edge with vertices v and w, then v and w are said to lie on( 依 附 于 ) e, and e is said to be incident with( 与 相 关 连 ) v and w. If the pairs are unordered, G is called an undirected graph( 无 向 图 ). If the pairs are ordered, G is called a directed graph( 有 向 图 ). The term directed graph is often shortened to digraph, and the unqualified term graph usually means undirected graph. Graphs: Definitions Two vertices in an undirected graph are called adjacent ( 邻 接 的 ) if there is an edge from the first to the second. A path ( 路 径 ) is a sequence of distinct vertices, each adjacent to the next. A cycle ( 回 路 ) is a path containing at least three vertices such that the last vertex on the path is adjacent to the first. A graph is called connected ( 连 通 的 ) if there is a path from any vertex. A free tree ( 自 由 树 ) is defined as a connected undirected graph with no cycles ( 没 有 环 的 连 通 无 向 图 ). n 个 顶 点,n- 条 边, 连 通 没 有 回 路 n 个 顶 点 的 连 通 图 中, 至 少 含 有 n- 条 边 Graphs: Definitions

5 Graphs: Definitions In a directed graph a path or a cycle means always moving in the direction indicated by the arrows. Such a path (cycle) is called a directed path (cycle). A directed graph is called strongly connected ( 强 连 通 的 ) if there is a directed path from any vertex to any other vertex. If we suppress the direction of the edges and the resulting undirected graph is connected, we call the directed graph weakly connected( 弱 连 通 的 ). 如 果 不 考 虑 边 的 方 向, 由 此 得 到 的 无 向 图 是 连 通 的, 则 称 有 向 图 是 弱 连 通 的 The valence ( 价, 度 ) of a vertex is the number of edges on which it lies, hence also the number of vertices adjacent to it. 所 有 顶 点 的 度 数 之 和 是 边 数 的 倍 Graphs: Definitions 图 的 存 储 结 构 Storage of the graph 7 7. The storage structure of graph 没 有 前 驱 和 后 继 的 关 系, 任 两 结 点 均 可 能 有 邻 接 关 系 in the undirected graph, adjacent points are symmetric, therefore we cannot distinguish the precursor and the successor in the directed graph, the starting point of edge is precursor, the end point of edge is successor, 但 有 向 环 又 如 何 表 达? assume that in G, V(G)= {v,v,...,v n- there are many representations, 重 点 介 绍 常 用 的 两 种 adjacency matrix (table) representation Adjacency matrix:a matrixrepresenting the adjacent relations of vertices (data elements) 若 顶 点 信 息 不 重 要, 用 two-dimensional array A n n 表 示 n= V(G) For weighted graph 对 于 加 权 图 : 7.. adjacency matrix representation adjacency matrix representation 若 顶 点 信 息 重 要, 则 应 将 其 组 织 成 一 个 sequential list ( 顺 序 表 ): edge table ( 邻 接 矩 阵 ) 邻 接 矩 阵 表 示 法 vertex table type specification ( 类 型 说 明 ) #define MaxVertexNum // 最 大 顶 点 数 typedef int EdgeType; // 边 类 型, 取 值 为,, or weight typedef char VertexType; // 顶 点 类 型 typedef struct{ VertexType vexs[maxvertexnum]; // 顶 点 表 EdgeType edges[maxvertexnum][maxvertexnum]; // 边 表, 邻 接 矩 阵 int n, e; // 顶 点 数, 边 数 the adjacency matrix of undirected graph is symmetric 无 向 图 的 邻 接 矩 阵 是 对 称 的 MGraph; 3 5

6 7.. adjacency matrix representation Build the adjacency matrix representation of undirected graph 7.. adjacency list 邻 接 表 linked storage structure 链 式 存 储 结 构 build a single linked list for the adjacency relationship of every node, put head node into an array to form a vertex table and a edge table node of vertex table 顶 点 表 结 点 结 构 : step: input the numbers of vertices and edges step: input vertex table node of edge table 边 表 结 点 结 构 : step3: initialize the adjacency matrix step: input edges (with weights) 3 representation of edge:(v i, v j ), because v i and v j are stored in the i th and j th components of vertex table respectively, so we only need to store the number j in the edge table of v i 7.. adjacency list example Instance of one adjacency list 7.. adjacency list typedef struct node{ // 边 表 结 点 int adjvex;// 邻 接 点 序 号 struct node * next; // 指 向 下 一 个 边 表 结 点 // 若 有 权, 则 增 加 一 域 EdgeNode; typedef struct vnode{ // 顶 点 表 结 点 VertexType vertex;// 顶 点 数 据 域 EdgeNode * firestedge; // 边 表 头 指 针 VertexNode,AdjList[MaxVertexNum];// 邻 接 表 类 型 typedef struct{ AdjList adjlist; // 邻 接 表 int n, e; // 顶 点 数 和 边 数 ALGraph; 邻 接 表 实 例 adjacency list adjacency list of undirected graph 无 向 图 邻 接 表 的 分 析 : (v i, v j ) E, then there is an edge table node whose adjvex=j in the adjacency list of v i there is an edge table node whose adjvex=i in the adjacency list of v j every edge was represented twice, so there are e edge table nodes in total the space complexity is O(n+e), the space complexity of adjacency matrix is O(n ) sparse graph ( 稀 疏 图 ) adopts adjacency list ( 邻 接 表 ) to save space dense graph ( 稠 密 图 ) adopts adjacency matrix ( 邻 接 矩 阵 ) ( 课 本 P63 最 下 面 的 一 段 话 ) adjacency list adjacency list of directed graph 有 向 图 邻 接 表 的 分 析 : <v i, v j > E, there is an edge table node whose adjvex=j in the adjacency list of v i every edge was represented once, so there are e edge table nodes in total In this situation, edge table is called 出 边 表 it is easy to solve out-degree ( 出 度 ) and difficult to solve in-degree ( 入 度 ) in 出 边 表 inverse adjacency list ( 逆 邻 接 表 ):<v i, v j > E, there is an edge table node whose adjvex=i in the adjacency list of v j In this situation, edge table is called 入 边 表 it is easy to solve in-degree ( 入 度 ) and difficult to solve out-degree ( 出 度 ) in 入 边 表 6

7 7.. adjacency list To establish adjacency list 建 立 邻 接 表 time: O(n+e), the time of adjacency matrix is O(n ) uniqueness ( 唯 一 性 ): not unique, different input sequences, different results, but the adjacency matrix is unique operation Judge whether (v i,v j ) is an edge? adjacency matrix ( 邻 接 矩 阵 ) O(), adjacency list ( 邻 接 表 ) O(n) find out the number of degree of vertex 求 顶 点 度 数 : both are almost the same O(n) 3 detect the number of edges 检 测 边 数 : adjacency matrix O(n ), adjacency list O(n+e) Computer Representation in textbook P57~P Graphs: Representation Set Implementations of Digraphs 集 合 表 示 Definition: A digraph G consists of a set V, called the vertices of G, and, for all v V, a subset A v of V, called the set of vertices adjacent to v. (A v 称 为 v 的 邻 接 点 集 合 ) 有 向 图 G 由 集 合 V 和 对 所 有 v V, V 的 子 集 A v 组 成 V 为 顶 点 集,A v 为 与 顶 点 v 邻 接 的 顶 点 集 Set as a bit string( 位 串 ): template <int max_set> // 模 板 参 数 并 不 局 限 于 类 型, 普 通 值 也 可 以 作 为 模 板 参 数, 编 译 时 确 定 大 小 struct Set { bool is_element[max_set]; // 大 小 为 max_set 的 bool 数 组 ; Graphs: Representation Set Implementations of Digraphs Digraph as a bit-string set 位 串 集 合 template <int max_size> class Digraph { int count; //number of vertices, at most max_size Set<max_size> neighbors[max_size]; ; //neighbor[v] 表 示 与 顶 点 v 邻 接 的 所 有 顶 点 的 集 合 Digraph as an adjacency table ( 邻 接 表 格 ) template <int max_size> class Digraph { int count; //number of vertices, at most max_size bool adjacency[max_size][max_size]; ; Graphs: Representation Graphs: Representation 邻 接 表 adjacency list 用 list 去 表 示 图 的 邻 接 关 系 List-based implementation typedef int Vertex; template <int max_size> // 仍 然 使 用 值 参 声 明 模 板 类 class Digraph { int count; //number of vertices, at most max_size List <Vertex> neighbors[max_size]; // 替 换 了 Set ; 7

8 Graphs: Representation Graphs: Representation Linked Implementation of Digraphs class Edge; //forward declaration( 向 前 声 明 ) class Vertex { // 定 义 顶 点 结 构 Edge *first_edge; // start of the adjacency list Vertex *next_vertex; // next vertex on the linked list ; class Edge { // 定 义 边 结 构 Vertex *end_point; // vertex to which the edge points Edge *next_edge; // next edge on the adjacency list ; class Digraph { // 定 义 图 Vertex *first_vertex; // header for the list of vertices ; Graphs: Representation 图 的 遍 历 graph traversal Graph Traversal ( 图 的 遍 历 ) basis of graph operations there is no start node, how to visit? 任 两 点 可 能 相 邻, 故 访 问 某 点 后 可 能 顺 回 路 又 回 到 点, in order to avoid repeat visiting, we need to mark vertices which are already visited Visited[ n-] boolean array, initial value are all false there two common methods: 7.3. depth first traversal (dfs traversal) similar to the preorder traversal of tree 类 似 树 的 前 序 遍 历 basic idea 设 G 初 态 是 所 有 顶 点 均 未 曾 访 问, v V(G) 为 初 始 出 发 点 ( 源 点 ), 则 深 度 优 先 遍 历 可 定 义 为 : 首 先 访 问 出 发 点 v, 将 其 标 记 为 已 访 问 ; 然 后 依 次 从 v 出 发 搜 索 v 的 每 个 邻 接 点 w, 若 w 未 曾 访 问 过, 则 以 w 为 出 发 点 继 续 深 度 优 先 遍 历, 直 至 图 中 所 有 和 v 有 路 径 相 通 的 顶 点 均 已 被 访 问 为 止 ; 若 此 时 图 中 仍 有 未 访 问 过 的 顶 点, 则 另 选 一 尚 未 访 问 过 的 顶 点 作 为 新 源 点 重 复 上 述 过 程, 直 至 图 中 所 有 顶 点 均 已 访 问 为 止 dfs 深 度 优 先 遍 历 and bfs 广 度 优 先 遍 历 7 8 8

9 7.3. depth first traversal (dfs traversal) characteristic: 遍 历 定 义 是 递 归 的, 特 点 是 尽 可 能 先 对 纵 深 方 向 搜 索, 故 称 为 深 度 优 先 搜 索 (dfs), 搜 索 过 程 : X V V V 3 已 访 问 过 回 溯 : 碰 壁 回 头 ( 典 型 的 回 溯 法 ) 7.3. depth first traversal (dfs traversal) 设 x 是 当 前 访 问 顶 点 : 若 v,v,v 3 均 未 被 访 问 过, 则 以 v 为 出 发 点 向 纵 深 搜 索, 不 能 前 进 后 回 溯 到 x; 继 续 从 v,v 3 出 发, 当 v,v 3 为 出 发 点 搜 索 完 成 后 回 溯 至 x, 因 为 x 的 所 有 邻 接 点 均 已 访 问 过, 故 继 续 回 溯 至 x 之 前 被 访 问 的 顶 点 ; 若 v,v,v 3 均 已 访 问 过, 表 示 一 定 是 从 x 之 前 被 访 问 的 顶 点 出 发 的 搜 索 曾 到 达 过 v,v,v 3, 故 访 问 x 之 后 返 回 ( 回 溯 ) 至 x 之 前 的 顶 点 depth first traversal (dfs traversal) algorithm implementation 算 法 实 现 typedef enum {FALSE, TRUE Boolean; Boolean Visited[MaxVertexNum]; // 布 尔 数 组 全 局 量 void DFSTraverse(ALGraph *G){ // 以 邻 接 表 表 示 图 for (i=; i<g->n; i++) Visited[i] = FALSE; // 初 始 化 for (i=; i<g->n; i++) if (!Visited[i]) //v i 未 访 问 过 DFS( G, i ); // 以 v i 为 源 点 开 始 dfs 搜 索 // 图 连 通 仅 有 次 外 部 调 用 5 void DFS (ALGraph *G, int i){ // 以 v i 为 出 发 点 对 G 进 行 dfs EdgeNode *p; printf ( %c, G->adjlist[i].vertex); // 访 问 顶 点 v i Visited[i]=TRUE; // 标 记 v i 已 访 问 过 p=g->adjlist[i].firstedge; // 取 v i 边 表 的 头 指 针 while (p){ // 依 次 搜 索 v i 的 邻 接 点 v j if (!Visited[p->adjvex]) // 若 v j 未 访 问 过,j=p->adjvex DFS(G,p->adjvex); // 以 v j 为 出 发 点 向 纵 深 搜 索 p=p->next; // 若 v j 已 访 问 过, 或 从 v j 出 发 的 dfs 完 成, 则 // 找 v i 的 下 一 邻 接 点 思 考 : 以 邻 接 矩 阵 为 存 储 结 构 自 己 写 出 dfs depth first traversal (dfs traversal) depth first traversal sequence (dfs sequence) 深 度 优 先 遍 历 序 列 vertex visiting sequence in traversal process the dfs sequence of G is not unique, but the sequence obtained is unique when the starting point is given and the storage structure is given 当 初 始 源 点 给 定, 存 储 结 构 确 定 后 得 到 的 序 列 唯 一 53 v3 v6 v v v v v5 v7 V 源 点 v 3 dfs() dfs() dfs() dfs(5) 5 dfs() 8 6 dfs(7) dfs(6) 回 溯 ( 法 ) 7 dfs(3) dfs 序 列 : v,v,v,v 5,v,v 6,v 3,v 7 ( 假 设 邻 接 表 的 边 表 递 增 有 序 )... 9

10 7.3. depth first traversal (dfs traversal) time 对 G 中 每 个 顶 点 恰 做 一 次 访 问 ( 外 部 + 内 部 调 用 dfs), 共 做 n 次 访 问 当 访 问 顶 点 v i 时, 时 间 主 要 花 费 在 搜 索 v i 的 邻 接 点 上 total: adjacency list: 〇 (n+e), 各 个 边 表 结 点 均 搜 索 到 adjacency matrix: 〇 (n ), 各 个 元 素 均 检 索 到 55 Depth-First Algorithm template <int max_size> void Digraph<max_size> :: depth_first(void (*visit)(vertex &)) const /* Post: The function *visit has been performed at each vertex of the Digraph in depth-first order. Uses: Method traverse to produce the recursive depth-first order. */ { bool visited[max_size]; Vertex v; for (all v in G) visited[v] = false; for (all v in G) if (!visited[v]) traverse(v, visited, visit); Depth-First Algorithm The recursion is performed in an auxiliary function traverse. template <int max_size> void Digraph<max_size> :: traverse(vertex &v, bool visited[], void (*visit)(vertex &)) const /* Pre: v is a vertex of the digraph. Post: The depth-first traversal, using function *visit, has been completed for v and for all vertices that can be reached from v. Uses: traverse recursively. */ { Vertex w; visited[v] = true; (*visit)(v); for (all w adjacent to v) if (!visited[w]) traverse(w, visited, visit); 例 V V V3 V V5 V6 V8 V7 深 度 遍 历 :V V V V8 V5 V6 V3 V7 例 V V V3 V V5 V6 V7 V8 深 度 遍 历 :V V V V8 V5 V3 V6 V7 c 访 问 标 志 : 访 问 次 序 : a b d e f h k g a b c 3d e 5f 6g 7h 8k F T F T F T F T F T F T F T F T FT a c h d k f e b g

11 7.3. breadth first traversal (bfs) similar to the level traversal ( 层 次 遍 历 )of tree basic idea 选 一 顶 点 v 为 源 点 访 问 之 characteristic 尽 可 能 先 对 横 向 搜 索, 故 称 之 为 breadth first traversal (bfs) 依 次 访 问 v 的 所 有 邻 接 点 w,w w t 3 然 后 依 次 访 问 w i ( i t) 的 所 有 未 曾 访 问 过 的 邻 接 点 依 次 类 推, 直 至 图 中 所 有 和 源 v 有 路 径 连 通 的 顶 点 均 已 访 问 过 为 止, 此 时, 若 G 是 连 通 图, 则 遍 历 完 成 ; 否 则 选 G 的 另 一 未 访 问 过 的 顶 点 做 新 源 点 继 续 上 述 搜 索 过 程, 直 至 G 中 所 有 顶 点 均 已 访 问 过 为 止 6 bfs 非 递 归, 用 队 列 作 为 中 间 数 据 结 构 先 访 问 的 顶 点 其 邻 接 点 亦 被 先 访 问 (FIFO) dfs 递 归 回 溯, 用 栈 保 存 访 问 过 的 顶 点 后 访 问 的 顶 点 其 邻 接 点 被 先 访 问 (LIFO) 7.3. breadth first traversal 设 x 和 y 是 两 个 相 继 访 问 的 顶 点, 其 邻 接 点 分 别 记 为 x,,x s 和 y,,y t x 在 y 之 前 访 问, 故 x,,x s 中 未 访 问 顶 点 亦 先 于 y,,y t 中 未 访 顶 点 被 访 问 到 可 用 FIFO 队 列 保 存 已 访 问 过 的 顶 点 顶 点 入 队 时 对 其 访 问 保 存 尚 未 访 问 过 的 顶 点 顶 点 出 队 时 对 其 访 问 7.3. breadth first traversal algorithm 遍 历 算 法 类 似 于 DFSTraverse void BFS(ALGraph *G, int k){ // 以 v k 为 源 InitQueue(&Q); // 队 列 Q 初 始 化 printf( %c, G->adjlist[k].vertex); // 访 问 源 v k Visited[k]=TRUE; EnQueue(&Q, k); // 相 当 于 v k 入 队 第 一 种 方 法 较 好, 下 面 用 此 方 法 实 现 算 法 breadth first traversal while (!QueueEmpty(&Q) ){ i=dequeue(&q); //v i 出 队 p=g->adjlist[i].firstedge; // 取 v i 边 表 头 指 针 while(p){ // 依 次 搜 索 v i 的 邻 接 点 v j if(!visited[p->adjvex] ){ //v j 未 访 问 过, 设 p->adjvex=j printf( %c,g->adjlist[p->adjvex].vertex); // 访 问 v j Visited[p->adjvex]=TRUE; EnQueue(&Q, p->adjvex); //v j 入 队 //endif p=p->next; // 在 下 一 边 表 结 点 中 找 v i 下 一 个 邻 接 点 //endwhile //endwhile breadth first traversal bfs queue v v v 3 v v v 6 v 5 v 7 v 6 v 7 v v v v 5 time 每 个 顶 点 入 队 一 次, 每 个 边 表 结 点 搜 索 一 次 时 间 与 dfs 相 同 66 v v 3

12 Breadth-First Algorithm template <int max_size> void Digraph<max_size> :: breadth_first(void (*visit)(vertex &)) const /* Post: The function *visit has been performed at each vertex of the Digraph in breadth-first order. Uses: Methods of class Queue. */ { Queue q; bool visited[max_size]; Vertex v, w, x; for (all v in G) visited[v] = false; for (all v in G) if (!visited[v]) { q.append(v); while (!q.empty( )){ q.retrieve(w); if (!visited[w]) { visited[w] = true; (*visit)(w); for (all x adjacent to w) q.append(x); //endif q.serve( ); //endwhile 无 向 图 的 实 例 : 为 了 说 明 问 题, 邻 接 结 点 的 访 问 次 序 以 序 号 为 准 序 号 小 的 先 访 问 如 : 结 点 的 邻 接 结 点 有 三 个, 则 先 访 问 结 点, 再 访 问 结 点 例 V V V3 V V5 V6 V7 V8 广 度 遍 历 :V V V3 V V5 V6 V7 V 例 V V V5 V6 V V V8 V7 图 的 广 度 优 先 的 访 问 次 序 : 广 度 遍 历 :V V V3 V V5 V6 V7 V

13 Graph Traversal Kruse 教 材 对 于 图 遍 历 的 叙 述 Depth-first traversal( 深 度 优 先 遍 历 ) of a graph is roughly analogous to preorder traversal of an ordered tree. Suppose that the traversal has just visited a vertex v, and let w ;w w k be the vertices adjacent to v. Then we shall next visit w and keep w w k waiting. After visiting w, we traverse all the vertices to which it is adjacent before returning to traverse w ; ;w k. Breadth-first traversal( 广 度 或 宽 度 优 先 遍 历 ) of a graph is roughly analogous to level-by-level traversal( 层 序 遍 历 ) of an ordered tree. If the traversal has just visited a vertex v, then it next visits all the vertices adjacent to v, putting the vertices adjacent to these in a waiting list to be traversed after all vertices adjacent to v have been visited. 7. connectivity ( 连 通 性 ) problem of graph 7.. connected component ( 连 通 分 量 ) and spanning tree ( 生 成 树 ) of undirected graph. find connected component 每 外 部 调 用 一 次 dfs 或 bfs, 可 求 一 连 通 分 量 的 顶 点 集. spanning tree and spanning forest spanning tree 生 成 树 连 通 图 G 的 极 小 连 通 子 图, 但 包 含 G 的 所 有 顶 点 ( 支 撑 树 ), 不 唯 一 n 个 顶 点 的 连 通 图 的 生 成 树 一 定 有 n- 条 边 connected component ( 连 通 分 量 ) and spanning tree ( 生 成 树 ) of undirected graph spanning forest: 各 连 通 分 量 的 生 成 树 集 合 find spanning tree and spanning forest: (employ dfs and bfs algorithm) 设 G 是 无 向 图, v V(G) 做 出 发 点 若 图 连 通, 则 做 一 次 dfs 或 bfs, 必 将 G 中 n 个 顶 点 都 访 问 到, 且 只 做 一 次 访 问 两 种 搜 索 方 法 中, 从 v i 搜 索 到 v j 时, 须 经 过 边 (v i, v j ), 故 只 需 添 加 输 出 边 的 操 作 即 可 : connected component ( 连 通 分 量 ) and spanning tree ( 生 成 树 ) of undirected graph 在 dfs 和 bfs 中, 均 在 while(p){ if(!visited[p->adjvex]){ 加 入 打 印 : (i, p->adjvex) //dfs 须 在 递 归 调 用 前 加 入 若 G 连 通 则 求 出 的 为 生 成 树, 否 则 为 生 成 森 林 若 G 为 有 向 图, 仅 当 源 点 为 有 根 图 的 根 时, 才 能 求 得 生 成 树, 否 则 为 生 成 森 林 最 小 生 成 树 (Minimum Spanning Tree) 生 成 树 概 念 (P59) 最 小 生 成 树 : 定 义 略 (P73) 设 G 是 连 通 图,G 的 生 成 树 不 唯 一 MST: 权 最 小 的 生 成 树, 树 的 权 是 各 边 上 的 权 值 之 和 应 用 n 个 城 市 之 间 的 通 信 网, 可 构 建 n(n-)/ 条 线 路 n 个 城 市 连 通 至 少 要 n- 条 线 路,G 的 生 成 树 是 个 可 行 的 方 案 最 小 生 成 树 是 最 经 济 的 可 行 方 案 Minimal Spanning Trees DEFINITION: A minimal spanning tree of a connected network is a spanning tree such that the sum of the weights of its edges is as small as possible. 77 3

14 MST 性 质 - 大 多 数 算 法 都 利 用 了 此 性 质 设 G=(V, E) 是 一 连 通 图,U 是 V 的 真 子 集, 若 (u, v) 是 所 有 连 接 U 和 V-U 的 边 中 权 最 小 的 边 ( 轻 边 ), 则 一 定 存 在 G 的 一 棵 最 小 生 成 树 包 括 此 边 Pf: 设 G 的 任 何 一 棵 最 小 生 成 树 均 不 包 括 (u, v); u u T U v v V-U u u U T v v V-U 79 u u T U v v V-U T 是 G 的 棵 MST, 轻 边 (u, v) T T 连 通 且 包 含 所 有 顶 点 必 有 一 路 径 P 连 接 u 和 v, 且 P 上 必 有 一 紫 边 连 接 红 点 集 和 白 点 集, 不 妨 设 其 为 (u, v ) 将 轻 边 加 入 T 上, 和 P 形 成 回 路 ; 删 (u, v ) 消 除 圈 后 形 成 树 T w(u, v) w(u, v ) w(t )=w(t)+w(u, v)-w(u, v ) w(t) T 亦 是 G 的 MST, 包 含 轻 边, 推 出 矛 盾, 故 假 设 不 成 立 8 u u U T v v V-U construct MST 就 是 找 轻 边 扩 充 到 当 前 生 成 的 树 T=(U, TE) 中 U- 红 点 集 红 边 ( 连 接 红 点 ) 集, 构 成 T V-U- 白 点 集 白 边 ( 连 接 白 点 ) 集 紫 边 集 - 连 接 红 点 和 白 点 的 边 轻 边 - 权 最 轻 的 紫 边, 或 最 短 紫 边 ( 若 权 为 长 度 ): (u,v ) u 5 v 5 u 3 v u 3 5 v 3 U V-U 8 Prim algorithm characteristic 当 前 形 成 的 集 合 T=(U, TE) 始 终 是 一 棵 树 T 中 的 顶 点 和 边 均 为 红 色 5 u v 5 u 3 basic idea (greedy algorithm) u 3 5 v 3 设 V(G)={,,,n- U V-U 算 法 的 每 一 步 均 是 在 连 接 红 白 点 集 的 紫 边 中 选 一 轻 边 扩 充 到 T( 贪 心 ),T 从 任 意 一 点 r 开 始 (r 为 根 ), 直 至 U=V 为 止 MST 性 质 保 证 了 贪 心 选 择 策 略 的 正 确 性 8 v Prim algorithm 如 何 找 轻 边? 可 能 的 紫 边 集 设 红 点 集 U =k, 白 点 集 V-U =n-k, 则 可 能 的 紫 边 数 为 :k(n-k) 在 此 紫 边 集 中 选 择 轻 边 效 率 太 低 构 造 候 选 轻 边 集 构 造 较 小 的 紫 边 集, 但 保 证 轻 边 在 其 中 因 为, v 白 点 集, 从 v 到 各 红 点 的 紫 边 中, 只 有 最 短 的 那 一 条 才 可 能 是 轻 边, 所 以 只 须 保 留 所 有 n-k 个 白 点 所 关 联 的 最 短 紫 边 作 为 轻 边 候 选 集 即 可 ( 如 v 3 ) 显 然, 轻 边 是 该 候 选 集 中 权 最 轻 的 边 u 5 v 5 u 3 v u 3 5 v 3 U V-U 83 Prim algorithm 如 何 维 护 候 选 轻 边 集? 当 把 轻 边 (u,v) 扩 充 至 T 中 时, u 5 v 5 u 3 v u 3 5 v 3 U V-U v 由 白 点 变 为 红 点, 紫 边 (u,v) 变 为 红 边 (u, v); 对 每 个 剩 余 白 点 j, 边 (v,j) 由 白 变 紫, 此 新 紫 边 的 长 度 可 能 小 于 白 点 j 原 来 所 关 联 的 最 短 紫 边 须 调 整 候 选 轻 边 集, 用 更 短 的 新 紫 边 (v,j) 取 代 原 来 关 联 于 j 的 最 短 紫 边 8

15 Prim algorithm algorithm outline Prim algorithm example PrimMST(G,T,r){ // 求 以 r 为 根 的 MST InitCandidateSet( ); // 初 始 化, 置 初 始 的 候 选 轻 边 集, 置 T=({r, φ) for (k=; k<n-; k++){ // 求 T 的 n- 条 树 边 (u,v)=selectlightedge( ); // 选 轻 边, 可 能 不 唯 一 TE=TE {(u,v); // 将 (u, v) 涂 红 加 入 树 中, 白 点 v 加 入 红 点 集 ModifyCandidateSet( ); // 根 据 新 红 点 v 调 整 候 选 轻 边 集 算 法 终 止 时 U=V, T=(V, TE) Prim algorithm storage structure #define Infinity INT_MAX // 表 示 最 大 整 数 #define n typedef int AdjMatrix[n][n]; // 邻 接 矩 阵 typedef struct{ // 树 边 int fromvex, tovex; // 起 点 终 点 int len; // 边 长 度, 权 值 MST[n-]; 设 邻 接 矩 阵 初 值 : 不 存 在 的 边 其 权 值 为 Infinity 87 Prim algorithm 算 法 求 精 -initialization 将 根 r 涂 红 加 入 红 点 集 U,TE=φ 对 每 个 白 点 i ( i n-, i r), i 所 关 联 的 最 短 紫 边 (r, i) 的 长 度 为 G[r][i], 这 n- 条 最 短 紫 边 构 成 了 初 始 的 候 选 轻 边 集 因 为 树 边 为 空, 故 将 T[..n-] 全 部 用 来 存 放 候 选 轻 边 集 void InitCandidateSet (AdjMatrix G, MST T, int r) { int i, k=; for (i=; i<n; i++) // 依 次 形 成 白 点 i 初 始 的 最 短 紫 边 存 放 在 T[k] 中 if (i!=r){ T[k].fromvex=r; // 紫 边 起 点 为 红 点 T[k].tovex=i; // 紫 边 终 点 为 白 点 T[k++].len=G[r][i]; // 紫 边 长 度, 权 值 88 ; Prim algorithm 算 法 求 精 - 选 轻 边 在 当 前 候 选 轻 边 集 T[k..n-] 中, 选 长 度 最 短 的 紫 边 (Note: T[..k-] 是 红 边 集,T 也 是 树, 为 什 么 针 对 白 点 构 造 候 选 集 更 好?) int SelectLightSet (MST T, int k){ int i, minpos, min=infinity; for (i=k; i<n-; i++) // 遍 历 候 选 集 找 轻 边 if(t[i].len<min){ min=t[i].len; // 紫 边 起 点 为 红 点 minpos=i; // 记 录 当 前 最 短 紫 边 的 位 置 if (min==infinity) error( G 不 连 通 ); return minpos; // 轻 边 为 T[minpos] ; 89 Prim algorithm 算 法 求 精 - 调 整 候 选 轻 边 集 设 轻 边 (u,v) 涂 红 后 加 入 到 树 边 中,T[k..n-] 是 待 调 整 的 候 选 轻 边 集, 则 须 根 据 新 红 点 v 调 整 T[k..n-] void ModifyCandidateSet ( AdjMatrix G, MST T, int k, int v) { int i, d; //v 是 新 红 点 for (i=k; i<n-; i++) { // 遍 历 候 选 集 d=g[v][t[i].tovex]; //T[i] 的 终 点 是 白 点,d 是 新 紫 边 的 长 度 if(d<t[i].len) {//d 小 于 白 点 T[i].tovex 原 关 联 最 短 紫 边 长 度 T[i].len=d; T[i].fromvex=v; // 新 紫 边 取 代 T[i].tovex 原 来 的 最 短 紫 边 u 5 v 5 u 3 v ; u 3 U 5 v 3 V-U 9 5

16 Prim algorithm 算 法 求 精 -final algorithm void PrimMST(AdjMatrix G, MST T, int r) { int k,m,v; InitCandidateSet(G, T, r); // 初 始 候 选 集 T[..n-] for (k=; k<n-; k++) { // 求 n- 条 树 边 中 的 k th 条 m=selectlightedge(t,k); // 在 T[k..n-] 选 轻 边 T[m] T[m] T[k]; // 轻 边 和 紫 边 T[k] 交 换, 将 其 扩 充 至 树 中 v=t[k].tovex; // 交 换 后 红 边 集 为 T[..k],v 是 新 红 点 ModifyCandidateSet(G,T,k+,v); //T[k+..n-] 是 新 候 选 集, 根 据 新 红 点 v 调 整 候 选 轻 边 集 9 Prim algorithm time analysis initialization:o(n) 在 k 循 环 中 : Select 中 循 环 次 数 为 n-k- // 在 T[k..n-] 选 轻 边 T[m] Modify 中 循 环 次 数 为 n-k- //T[k+..n-] 是 新 候 选 集, 根 据 新 红 点 v 调 整 候 选 轻 边 集 因 此 : 时 间 为 O(n ), 与 边 无 关, 适 合 稠 密 图 9 implementation of Prim s Algorithm template <class Weight, int graph_size> class Network: public Digraph<Weight, graph_size> { public: Network( ); void read( ); //overridden method to enter a Network void make_empty(int size = ); void add_edge(vertex v, Vertex w, Weight x); void minimal_spanning(vertex source, Network<Weight, graph_size> &tree) const; ; implementation of Prim s Algorithm template <class Weight, int graph_size> void Network < Weight, graph_size > :: minimal_spanning(vertex source,network<weight, graph_size> &tree) const /* Post: The Network tree contains a minimal spanning tree for the connected component( 连 通 分 量 )of the original Network that contains vertex source. */ { tree.make_empty(count); bool component[graph_size]; // Vertices in set X Weight distance[graph_size]; // Distances of vertices adjacent to X implementation of Prim s Algorithm Vertex neighbor[graph_size]; // Nearest neighbor in set X Vertex w; for (w = ; w < count; w++) { component[w] = false; distance[w] = adjacency[source][w]; neighbor[w] = source; component[source] = true; // source alone is in the set X. for (int i = ; i < count; i++) { Vertex v; //Add one vertex v to X on each pass. Weight min = infinity; for (w = ; w < count; w++) if (!component[w]) if (distance[w] < min) {v = w; min = distance[w]; if (min < infinity) { component[v] = true; tree. add_edge (v, neighbor[v], distance[v]); for (w = ; w < count; w++) if (!component[w]) if (adjacency[v][w] < distance[w]) { distance[w] = adjacency[v][w]; neighbor[w] = v; else break; // finished a component in disconnected graph 6

17 Kruskal algorithm characteristic: 当 前 形 成 的 集 合 T 除 最 终 结 果 外, 始 终 是 森 林, 无 环 algorithm: KruskalMST(G){ T=(V, φ);// 包 含 n 个 顶 点, 不 含 边 的 森 林 ; 依 权 的 增 序 对 E(G) 中 边 排 序, 设 结 果 在 E[..e-]; for (i=; i<e; i++) { 取 E 中 第 i 条 边 (u,v); if (u 和 v 分 属 森 林 T 中 两 棵 不 同 的 树 )then T=T {(u,v); // 否 则 产 生 回 路, 放 弃 此 边 if (T 已 是 一 棵 树 )then return T; //endfor 97 Kruskal algorithm ( 续 ) 例 子 : 略 时 间 : 对 边 排 序 O(elge) for 循 环 中 : 检 测 每 条 边 的 两 个 顶 点 是 否 在 同 一 连 通 分 量 ( 树 ) 上 只 要 采 用 合 适 的 数 据 结 构, 检 测 时 间 为 O(lge) 因 此, 此 时 间 亦 为 O(elge) 总 计 : O(elge) 结 论 : 时 间 性 能 主 要 取 决 于 边 数, 适 合 稀 疏 图 topological sort 拓 扑 排 序 有 向 无 环 图 DAG (Directed Acyclic Graph) 的 应 用 Acyclic: 非 循 环 Kruse P579 related concept set and relationship cartesian product ( 笛 卡 尔 积 ): 设 A B 是 两 个 集 合, 所 有 序 偶 (x,y) 构 成 的 集 合 (x A, y B), 称 为 A,B 的 笛 卡 儿 积, 记 为 A B binary relation ( 二 元 关 系 ): 集 合 A B 的 一 个 子 集 R, 称 为 集 合 A 与 B 上 的 一 个 二 元 关 系, 简 称 关 系 若 B=A, 则 R 称 为 A 上 的 一 个 二 元 关 系,R 刻 画 了 集 合 A 中 两 个 元 素 之 间 的 关 系 若 (x,y) R, 则 称 x 和 y 有 关 系 R, 亦 可 记 为 xry, 否 则 x 和 y 没 有 关 系 R, 记 为 xr y 集 合 A 上 的 关 系 R 是 reflexive ( 自 反 的 ) ( 反 身 的 ), 若 对 x A, 都 有 xrx 集 合 A 上 的 关 系 R 是 symmetric ( 对 称 的 ), 若 xry, 则 yrx 其 中,x,y A 集 合 A 上 的 关 系 R 是 antisymmetric ( 反 对 称 的 ), 若 xry,yrx, 则 必 有 x=y. 其 中 x,y A 集 合 A 上 的 关 系 R 是 transitive ( 传 递 的 ), 若 xry,yrz, 则 xrz 其 中 x,y,z A 例 子 : 数 之 间 的 equality ( 相 等 ) 关 系, 具 有 自 反 性, 对 称 性, 传 递 性, 反 对 称 性 ; 数 之 间 的 less than ( 小 于 ) 关 系, 具 有 传 递 性, 反 对 称 性 ; 数 之 间 的 less than or equal to ( 小 于 等 于 ) 关 系, 具 有 自 反 性, 传 递 性, 反 对 称 性 ; 7

18 related concept partial order ( 部 分 序 ) 设 R 是 集 合 A 上 的 一 个 关 系, 若 R 具 有 reflexivity ( 自 反 性 ), antisymmetry ( 反 对 称 性 ) 和 transitivity ( 传 递 性 ), 则 称 R 是 A 上 的 partial order relation ( 偏 序 关 系 ),A 是 partially ordered set ( 偏 序 集 ) ( 对 于 R) 偏 序 关 系 R 一 般 记 为, 若 将 关 系 看 作 是 比 较, 则 偏 序 关 系 是 指 集 合 中 仅 有 部 分 元 素 是 可 以 比 较 的 total order (linear order, 线 性 序 ) 设 R 是 集 合 A 上 的 一 个 偏 序 关 系, 若 对 x,y A, 必 有 xry 或 yrx, 则 称 R 是 A 上 的 全 序 关 系,A 是 全 序 集 ( 对 于 R) 数 集 合 上 的 大 小 关 系 是 全 序 关 系 全 序 关 系 是 指 集 合 中 全 体 成 员 之 间 均 可 比 较 3 related concept topological sort 将 一 个 dag 图 G=(V,E) 中 的 所 有 顶 点 排 成 一 个 线 性 序 列, 使 得 对 G 中 任 意 一 对 顶 点 u 和 v, 若 <u,v> E, 则 在 线 性 序 列 中 u 在 v 之 前 这 种 给 顶 点 定 序 的 操 作 称 为 拓 扑 排 序 拓 扑 ( 有 序 ) 序 列 : 上 述 顶 点 的 线 性 序 列 称 为 拓 扑 序 列 唯 一 吗? No! 几 何 意 义 : 将 G 中 顶 点 按 拓 扑 序 列 的 次 序 排 成 一 行, 则 G 中 所 有 的 有 向 边 的 指 向 均 为 从 左 到 右 例 子 : v v v 3 v v v 3 v v related concept topological sort 拓 扑 排 序 成 功 的 充 要 条 件 : 无 环 example: v v 3 v v v 3 v v v application background: 有 向 图 G 可 表 示 事 件 之 间 的 先 后 关 系, 顶 点 表 示 事 件, 边 表 示 事 件 之 间 的 依 赖 关 系 : <u,v> E(G) 表 示 u 先 于 v 发 生,u 完 成 后 才 能 开 始 v 若 G 表 示 施 工 图 生 产 流 程 图 学 习 计 划 安 排, 则 在 只 能 串 行 工 作 时, 拓 扑 序 列 是 一 种 可 行 的 方 案 或 计 划 5 求 拓 扑 序 列? () 无 前 驱 的 顶 点 优 先 (Kahn 算 法 ) algorithm thought: 输 出 当 前 入 度 为 的 顶 点 NonPreFirstTopSort(G){ while( G 中 有 入 度 为 的 顶 点 ) do { 从 G 中 选 个 入 度 为 的 顶 点 v 输 出 之 ; 从 G 中 删 v 及 其 出 边, 出 边 终 点 的 入 度 减 ; if ( 输 出 的 顶 点 数 < V(G) ) then Error ( G 有 环, 排 序 失 败 ); 6 求 拓 扑 序 列? () 无 前 驱 的 顶 点 优 先 例 子 : 输 出 v, v, v 3, v, v 5 v v v 3 v v 3 v 5 v v 5 Step3: 删 v 3 Step: 删 v 或 v 不 妨 设 删 v v v 5 v v 3 v v 5 Step: 删 v Step: 删 v v 5 Step5: 删 v 5 7 求 拓 扑 序 列? algorithm implementation 增 加 一 局 部 向 量 indegree[..n] 保 存 各 顶 点 的 当 前 入 度 或 者 在 邻 接 表 的 顶 点 表 中 增 加 入 度 域 用 栈 ( 或 队 列 ) 来 保 存 所 有 入 度 为 的 顶 点, 以 免 每 次 选 入 度 为 的 顶 点 时 扫 描 整 个 indegree 向 量 void NonPreFirstTopSort(ALGraph G){ // 以 下 v i 简 称 为 i int indegree[maxvertexnum],i,j,count=; SeqStack S; EdgeNode *p; for( i=; i<g.n; i++ ) indegree[i]=; for( i=; i<g.n; i++ ) // 对 每 个 顶 点 i for( p=g.adjlist[i].firstedge; p; p=p->next) // 扫 描 i 的 出 边 表 indegree[p->adjvex]++; // 将 <i,j> 的 终 点 j 入 度 加,j=p->adjvex InitStack(&S); 8 for (i=; i<g.n; i++) if (!indegree[i] ) Push(&S,i);// 入 度 为 的 顶 点 入 栈 8

19 求 拓 扑 序 列? while(!stackempty(&s) ){// 栈 非 空 时, 图 中 仍 有 入 度 为 的 顶 点 i=pop(&s); // 删 除 无 前 驱 的 顶 点 i printf( %c\t,g.adjlist[i].vertex); // 输 出 顶 点 i count++; // 输 出 顶 点 计 数 for (p=g.adjlist[i].firstedge; p; p=p->next){ // 扫 描 顶 点 i 的 出 边 表 j=p->adjvex; //j 是 <i,j> 的 终 点 indegree[ j ]--; //j 的 入 度 减, 相 当 于 删 出 边 <i,j> if (! indegree[ j ] ) Push(&S, j); //j 的 入 度 为 则 进 栈 if ( count<g.n ) printf( \ng is not a DAG\n ); time: 初 始 化 O(n+e) 排 序 成 功 时 最 大 : 每 个 顶 点 入 出 栈 各 次, 每 个 边 表 节 点 被 检 查 次 O(n+e) 求 拓 扑 序 列? () 无 后 继 的 顶 点 优 先 algorithm thought: 输 出 当 前 出 度 为 的 顶 点 NonSuccFirstTopSort(G){ // 应 选 G 的 逆 邻 接 表 while( G 中 有 出 度 为 的 顶 点 ) do { 从 G 中 选 个 出 度 为 的 顶 点 v 输 出 之 ; 从 G 中 删 v 及 其 入 边, 入 边 起 点 的 出 度 减 ; if ( 输 出 的 顶 点 数 < V(G) ) then Error ( G 有 环, 排 序 失 败 ); output result: 逆 拓 扑 序 列 algorithm implementation: 略 求 拓 扑 序 列? (3) 利 用 dfs 遍 历 算 法 principle: 因 为 当 从 某 顶 点 v 出 发 的 dfs 搜 索 完 成 时,v 的 所 有 后 继 ( 因 为 无 环 ) 必 定 均 已 访 问 过 ( 想 象 他 们 均 已 被 删 除 ), 此 时 v 相 当 于 是 无 后 继 的 顶 点, 所 以 可 在 dfs 算 法 返 回 前 输 出 顶 点 v, 即 可 得 到 DAG 的 逆 拓 扑 序 列 algorithm: DFSTopSort(G,i,T){ // 在 DFSTraverse 中 调 用 此 算 法,T 是 栈 visited[i]=true; // 访 问 i for ( 所 有 i 的 邻 接 点 j)// 即 < i, j> E(G) if (!visited[ j ] ) DFSTopSort(G,j,T); Push(&T, i)// 从 i 出 发 的 搜 索 已 完 成, 输 出 i characteristic: 与 NonSuccFirstTopSort 算 法 类 似 ; 若 G 有 环, 则 不 能 正 常 工 作 reverseorder (dfs 拓 扑 序 列 ): typedef int Vertex; template <int graph_size> class Digraph { public: Digraph( ); void read( ); void write( ); // methods to do a topological sort void depth_sort(list<vertex> &topological_order); void breadth_sort(list<vertex> &topological_order); private: int count; List <Vertex> neighbors[graph_size]; void recursive_depth_sort(vertex v, bool visited[]); List<Vertex> &topological_order); ; Depth-First Algorithm template <int graph_size> void Digraph<graph_size> ::depth_sort(list<vertex> &topological_order) /* Post: The vertices of the Digraph are placed into List topological_order with a depth-first traversal of those vertices that do not belong to a cycle. Uses: Methods of class List, and function recursive_depth_sort to perform depth-first traversal. */ 9

20 { bool visited[graph_size]; Vertex v; for (v = ; v < count; v++) visited[v] = false; Topological_order.clear( ); for (v = ; v < count; v++) if (!visited[v]) //Add v and its successors into topological order. recursive_depth_sort(v, visited, topological_order); template <int graph_size> void Digraph<graph_size> :: recursive_depth_sort(vertex v, bool *visited, List<Vertex> &topological_order) /* Pre: Vertex v of the Digraph does not belong to the partially completed List topological_order. Post: All the successors of v and finally v itself are added to topological order with a depth-first search. Uses: Methods of class List and the function recursive_depth_sort. */ { visited[v] = true; int degree = neighbors[v].size( ); for (int i = ; i < degree; i++) { Vertex w; //A (neighboring) successor of v neighbors[v].retrieve(i, w); if (!visited[w]) // Order the successors of w. recursive_depth_sort(w, visited, topological_order); topological_order.insert(, v); // Put v into topological_order. Breadth-First Algorithm template <int graph_size> void Digraph<graph_size> :: breadth_sort(list<vertex> &topological_order) /* Post: The vertices of the Digraph are arranged into the List topological_order which is found with a breadth-first traversal of those vertices that do not belong to a cycle. Uses: Methods of classes Queue and List. */ { topological_order.clear( ); Vertex v, w; int predecessor_count[graph_size]; for (v = ; v < count; v++) predecessor_count[v] = ; for (v = ; v < count; v++) for (int i = ; i < neighbors[v].size( ); i++) { neighbors[v].retrieve(i, w); // Loop over all edges v-w. predecessor_count[w]++; Queue ready_to_process; for (v = ; v < count; v++) if (predecessor_count[v] == ) ready_to_process.append(v); while (!ready_to_process.empty( )) { ready_to_process.retrieve(v); topological_order.insert(topological_order.size( ), v); for (int j = ; j < neighbors[v].size( ); j++) { neighbors[v].retrieve(j, w); // Traverse successors of v. predecessor_count[w]--; if (predecessor_count[w] == ) ready_to_process.append(w); ready_to_process.serve( );

21 7.6 the shortest path (Kruse P583) Application Background:traffic advisory, navigation 约 定 有 向 图 设 V={,,,n-, 边 上 的 权 值 非 负 ( 长 度 ) 分 类 ( 依 照 源 点 终 点 ) 单 源 最 短 路 径 : 个 源 点 到 其 余 所 有 顶 点 的 最 短 路 径 单 目 标 最 短 路 径 : 将 各 边 反 向, 即 为 问 题 3 单 点 对 间 最 短 路 径 : 可 用 来 解, 但 二 者 渐 近 时 间 相 同 所 有 点 对 间 最 短 路 径 : 亦 可 用 来 解, 即 每 个 顶 点 作 为 7.6. single source shortest path problem observe 源 点 调 用 例 子 : 当 求 到 的 最 短 路 径 时, 则 该 路 径 <,3,> 上 顶 点,3 的 最 短 路 源 点 中 间 顶 点 终 点 长 度 , 6 上 表 是 按 路 径 长 度 递 增 序 产 生 的 从 源 点 到 其 余 顶 点 的 最 短 路 径 到 的 路 径 :<,>, <,3,>, <,,,>, <,3,,> 长 度 :, 9, 7, 6 规 律 : 当 按 长 度 增 序 生 成 从 源 s 到 其 它 顶 点 的 最 短 路 径 时, 则 当 前 正 在 生 成 的 最 短 路 径 上 除 终 点 外, 其 余 顶 点 的 最 短 路 径 均 已 生 成 径 在 此 前 已 生 成 7.6. single source shortest path problem convention( 约 定 ) 从 源 s 到 终 点 v 的 最 短 路 径 简 称 为 v 的 最 短 路 径,SP(v) s 到 v 的 最 短 路 径 长 度 简 称 为 v 的 最 短 距 离,SD(v) 红 点 集 S: 最 短 距 离 已 确 定 的 顶 点 集 合 白 点 集 V-S: 最 短 距 离 尚 未 确 定 的 顶 点 集 合 算 法 思 想 - Dijkstra(97 图 灵 奖 得 主 ) 基 于 上 述 观 察 initialization: 仅 已 知 源 s 的 最 短 距 离 SD(s)=, 故 红 点 集 S={s; enlarge the red points set : 算 法 的 每 一 步 均 是 在 当 前 白 点 集 中 选 一 最 短 距 离 最 小 的 白 点 来 扩 充 红 点 集, 以 保 证 算 法 是 按 长 度 增 序 来 产 生 各 顶 点 的 最 短 路 径 ; end: 当 前 白 点 集 空 或 仅 剩 下 最 短 距 离 为 的 白 点 为 止 注 : 若 s 到 某 白 点 的 路 径 不 存 在, 可 假 设 该 白 点 的 最 短 路 径 是 一 条 长 度 为 的 虚 拟 路 径 single source shortest path problem how to enlarge the red points set? 白 点 k 的 最 短 路 径 上 除 终 点 外, 其 余 顶 点 的 最 短 路 径 均 已 生 成, 故 它 们 均 为 红 点 设 置 向 量 D[..n-], 对 每 一 个 白 点 v V-S, 用 D[v] 记 录 从 源 点 s 到 达 v, 且 除 v 外 中 间 不 经 过 任 何 白 点 的 最 短 路 径 长 度 初 始 时 每 个 白 点 v 的 D[v] 值 是 边 <s,v> 上 的 权 Note: 从 s 到 v 的 中 间 不 经 过 其 他 白 点 的 路 径 可 能 不 止 条, 但 只 需 将 其 中 最 短 的 那 条 的 长 度 记 录 在 D[v] 中 D[v]=SD[v]? 即 D[v] 是 v 最 终 的 最 短 距 离 吗? 不 一 定, 因 为 s 到 v 可 能 存 在 包 含 其 它 白 点 作 为 中 间 点 的 更 短 路 径 D[v] 只 是 v 当 前 估 计 的 最 短 距 离 ( 简 称 估 计 距 离 ), 即 :D[v] SD[v] 如 何 在 当 前 白 点 集 中 选 一 最 短 距 离 最 小 的 白 点 k 来 扩 充 红 点 集? 7.6. single source shortest path problem how to enlarge the red points set? Th.7.6. 若 k 是 白 点 集 中 估 计 距 离 最 小 的 顶 点, 则 k 的 估 计 距 离 就 是 最 短 距 离 即 : 若 D[k]=min{ D[i]: i V-S, 则 D[k]=SD[k] Pf (proof by contradiction, 反 证 法 ) 设 D[k] 不 是 k 的 最 短 距 离, 则 必 存 在 一 条 路 径 P:s p k, 其 长 度 Length(P)<D[k] ( 式 ) 由 D[k] 定 义 知,P 至 少 包 含 个 白 点 作 为 中 间 点, 不 妨 设 x 是 P 上 第 个 白 点, 则 P 可 分 解 为 : s p p x, x k 其 中 P 中 仅 有 x 为 白 点, 由 D[x] 定 义 知 length[p] D[x], 又 因 权 为 非 负, 故 length[p], 所 以 length(p)=length(p)+length(p) D[x] ( 式 ) 由 式, 得 :D[k]>length(P) D[x], 这 与 k 是 当 前 白 点 集 中 估 计 距 离 最 小 的 顶 点 矛 盾! 定 理 保 证 了 k 加 入 红 点 集 的 正 确 性 single source shortest path problem 如 何 调 整 白 点 集 中 白 点 的 估 计 距 离? 由 于 新 红 点 k 可 能 导 致 剩 余 白 点 的 估 计 距 离 变 小, 使 之 离 源 点 更 近, 故 需 调 整 设 j V-S, 若 D[j] 由 于 k 加 入 红 点 集 而 变 小, 则 新 路 径 P 必 是 p p s k j, 且 P 中 只 有 红 点,P 必 是 边 <k,j>, 即 : Length(p)= D[k] + w<k,j>. 证 明 : 略 adjustment method 若 length(p)<d[j], 则 用 length(p) 来 修 正 D[j] 6

22 7.6. single source shortest path problem example 最 短 距 离 : 红 色 估 计 距 离 : 白 色 依 次 求 出 的 最 短 距 离 为 : ) D[]= ) D[]=, 调 整 顶 点 3) D[3]=3, 调 整 顶 点, ) D[]=5, 调 整 顶 点 5) D[]= single source shortest path problem how to construct the optimal solution 因 为 D 向 量 只 记 录 了 最 优 解 的 值, 但 不 能 得 到 最 优 解 因 此, 要 记 录 最 优 解 则 须 引 入 附 加 信 息 因 为 最 优 解 是 最 短 路 径 树, 故 只 需 增 加 一 个 向 量 P[..n-] 用 P[i] 记 录 顶 点 的 双 亲, 由 双 亲 的 唯 一 性 知, 顶 点 i 的 最 短 路 径 可 从 P[i] 反 复 上 溯 至 根 ( 源 点 ) 即 可 求 得 最 优 解 algorithm implementation if <i,j> 不 是 边 G[i][j]= w(<i,j>) otherwise shortest path tree ( 最 短 路 径 树 ): 各 顶 点 的 最 短 路 径 ( 实 线 ) 总 是 一 棵 以 源 8 点 为 根 的 树, 称 之 为 最 短 路 径 树 7.6. single source shortest path problem void Dijkstra ( AdjMatrix G, Distance D, Path P, int s ){ // s n-, 若 <i,j> 不 是 边, 则 G[i][j]=Infinity Boolean S[n];//S 是 红 点 集 S[i] 为 真 表 示 i 为 红 点, 否 则 为 白 点 for ( i=; i<n; i++) { // 初 始 化 S[i]=FALSE; D[i]=G[s][i]; // 置 初 始 的 估 计 距 离 if ( D[i]<Infinity ) P[i]=s; //s 是 i 的 前 驱 ( 双 亲 ) else P[i]=-; // i 无 前 驱, 注 意 P[s] 亦 无 前 驱 S[s]=TRUE; D[s]=;// 红 点 集 仅 有 源 点 s 9 for ( i=; i<n-; i++) { // 向 红 点 集 S 扩 充 n- 个 红 点 min=infinity; for ( j=; j<n; j++ ) // 选 估 计 距 离 最 小 的 白 点 k( 离 s 最 近 ) if (!S[ j ]&&D[ j ]<min ) { min=d[ j ]; k=j; if (min==infinity) return; // 白 点 集 为 空 或 只 剩 下 无 最 短 路 径 的 点 S[k]=TRUE; // k 加 入 红 点 集 for ( j=; j<n; j++ ){ // 调 整 剩 余 白 点 的 估 计 距 离 if (!S[ j ]&&D[ j ]>D[k]+G[k][ j ] ) { D[ j ] = D[k]+G[k][ j ]; // 修 改 白 点 j 的 估 计 距 离, 使 之 离 s 更 近 P[ j ] = k; // k 是 j 的 前 驱 //endfor 3 algorithm execution process 源 点 s=3 循 环 i 红 点 集 S k D[] D[] D[] D[3] D[] P[] P[] P[] P[3] P[] 初 始 化 { {3, {3,, 同 上 - 白 点 集 {, 中 所 有 点 的 估 计 距 离 为, 退 出 循 环 time: 时 间 O(n ) constructive solution constructive solution output path and its length void PrintPath(Path P,Distance D){ // 路 径 是 逆 向 的 int i,pre; for ( i=; i<n; i++ ) { // 依 次 打 印 点 i 的 最 短 路 径 及 长 度 printf( \nd:%d, P:%d, D[i], i); // 输 出 终 点 i pre=p[i]; // 找 终 点 i 的 前 驱 while ( pre!= - ) { printf(, %d, pre ); pre=p[pre]; // 上 溯 找 前 驱 3

23 7.6. 所 有 点 对 间 的 最 短 路 径 问 题 solution one 以 每 一 顶 点 为 源 点, 调 用 Dijkstra 算 法, 时 间 O(n 3 ) solution two Floyd (978 年 图 灵 奖 得 主 ) 算 法 更 简 洁, 但 是 时 间 仍 为 O(n 3 ) assumption: 加 权 邻 接 矩 阵 C(n n) if i=j C[i][j]= if <i,j> 不 是 边 w(<i,j>) otherwise thought: i,j V, 若 <i,j> E, 则 从 i 到 j 有 一 条 路 径, 长 度 为 C[i][j] 但 它 不 一 定 是 最 短 路 径, 因 为 可 能 存 在 一 条 从 i 到 j 中 间 包 含 其 他 顶 点 的 更 短 路 径 因 此, 必 须 依 次 考 虑 能 否 在 i 和 j 之 间 加 入 顶 点,,n-, 而 得 到 更 短 的 路 径 所 有 点 对 间 的 最 短 路 径 问 题 the basic steps of Floyd algorithm 定 义 n n 的 方 阵 序 列 D -, D, D n-, initialization: D - =C D - [i][j]= 边 <i,j> 的 长 度, 表 示 初 始 的 从 i 到 j 的 最 短 路 径 长 度, 即 它 是 从 i 到 j 的 中 间 不 经 过 其 他 中 间 点 的 最 短 路 径 iteration: 设 D k- 已 求 出, 如 何 得 到 D k ( k n-)? D k- [i][j] 表 示 从 i 到 j 的 中 间 点 不 大 于 k- 的 最 短 路 径 p:i j, 考 虑 将 顶 点 k 加 入 路 径 p 得 到 顶 点 序 列 q:i k j, 若 q 不 是 路 径 或 q 是 长 度 大 于 p 长 度 的 路 径, 则 当 前 的 最 短 路 径 仍 是 上 一 步 结 果 :D k [i][j]= D k- [i][j]; 否 则 用 q 取 代 p 作 为 从 i 到 j 的 最 短 路 径 因 为 q 的 两 条 子 路 径 i k 和 k j 皆 是 中 间 点 不 大 于 k- 的 最 短 路 径, 所 以 从 i 到 j 中 间 点 不 大 于 k 的 最 短 路 径 长 度 为 : D k [i][j]=min{ D k- [i][j], D k- [i][k] +D k- [k][j] 矩 阵 序 列 D 3 -, D, D n- 可 在 同 个 矩 阵 上 迭 代 求 得, 为 什 么? 7.6. 所 有 点 对 间 的 最 短 路 径 问 题 the basic steps of Floyd algorithm solution matrix ( 解 矩 阵 ): Path[n][n]: 记 录 路 径 构 造 在 第 k 次 迭 代 中,P[i][j] 记 录 从 i 到 j 的 中 间 点 序 号 不 大 于 k 的 最 短 路 径 上 顶 点 i 的 后 继 顶 点 当 算 法 结 束 时, 可 由 Path[i][j] 得 到 从 i 到 j 的 最 短 路 径, 其 方 法 是 从 顶 点 i 开 始 反 复 找 其 后 继, 直 至 找 到 顶 点 j 或 确 认 i 到 j 没 有 路 径 为 止 所 有 点 对 间 的 最 短 路 径 问 题 algorithm implementation of Floyd void Floyd( AdjMatrix D, AdjMatrix C, int Path[n][n] ) { for ( i=; i<n; i++ ) for ( j=; j<n; j++ ) { // 初 始 化 D[ i][ j]=c[ i][ j]; if ( C[ i][ j]=infinity ) Path[i][j]=-; else Path[ i][ j]=j; //j 是 i 的 后 继 //endfor for ( k=;k<n;k++ ) // 将 k 扩 充 到 从 i 到 j 的 最 短 路 径 上 for ( i=;i<n;i++ ) for ( j=;j<n;j++ ) if ( D[ i][ k]+d[ k][ j]<d[ i][ j] ) { D[ i][ j]=d[ i][ k]+d[ k][ j]; // 修 改 路 径 长 度 Path[ i][ j]=path[ i] [ k]; // 修 改 路 径 所 有 点 对 间 的 最 短 路 径 问 题 algorithm implementation of Floyd void PrintPath( AdjMatrix D, int Path[n][n] ){ // 不 妨 设 D 是 整 型 矩 阵 for ( i=; i<n; i++ ) for ( j=; j<n; j++ ) { printf( %d, D[ i][ j] ); //i 到 j 的 最 短 路 径 长 度 next=path[i][j];//next 为 起 点 i 的 后 继 if (next == -) //i 无 后 继 表 示 i 到 j 无 路 径 printf( %d to %d no path.\n, i, j ); else { printf( %d, i ); // 输 出 起 点 while ( next!= j ){ printf( ->%d, next ); // 输 出 后 继 顶 点 next=path[next][j]; // 继 续 找 后 继 顶 点 //endwhile printf( %->%d, j ); // 输 出 终 点 //endif //endfor 37 3