PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

签遇庾
5 years ago
Views:

数据结构与算法 ( 七 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008.

1 数据结构与算法 ( 七 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 第 7 章图 7.1 图的定义和术语 7.2 图的抽象数据类型 7.3 图的存储结构 7.5 最短路径 7.6 最小生成树 2

3 图的遍历 (graph traversal) 给出一个图 G 和其中任意一个顶点 V 0, 从 V 0 出发系统地访问 G 中所有的顶点, 每个顶点访问而且只访问一次深度优先遍历广度优先遍历拓扑排序 3

4 图遍历的考虑从一个顶点出发, 试探性访问其余顶点, 同时必须考虑到下列情况从一顶点出发, 可能不能到达所有其它的顶点如非连通图 ; 也有可能会陷入死循环如存在回路的图 4

5 解决办法为每个顶点保留一个标志位 (mark bit) 算法开始时, 所有顶点的标志位置零在遍历的过程中, 当某个顶点被访问时, 其标志位就被标记为已访问 5

6 图的遍历算法框架 void graph_traverse(graph& G) { // 对图所有顶点的标志位进行初始化 for(int i=0; i<g.verticesnum(); i++) G.Mark[i] = UNVISITED; // 检查图的所有顶点是否被标记过, 如果未被标记, // 则从该未被标记的顶点开始继续遍历 // do_traverse 函数用深度优先或者广度优先 for(int i=0; i<g.verticesnum(); i++) if(g.mark[i] == UNVISITED) do_traverse(g, i); } 6

7 深度优先遍历 (depth-first search) 深搜 ( 简称 DFS) 类似于树的先根次序遍历, 尽可能先对纵深方向进行搜索选取一个未访问的点 v 0 作为源点访问顶点 v 0 递归地深搜遍历 v 0 邻接到的其他顶点重复上述过程直至从 v 0 有路径可达的顶点都已被访问过再选取其他未访问顶点作为源点做深搜, 直到图的所有顶点都被访问过 7

8 a b d e f c g 深度优先搜索的顺序是 : a b c f d e g 8

9 void DFS(Graph& G, int v) { G.Mark[v] = VISITED; } Visit(G,v); 图的深度优先遍历 (DFS) 算法 // 深度优先搜索的递归实现 // 把标记位设置为 VISITED // 访问顶点 v for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) if (G.Mark[G.ToVertex(e)] == UNVISITED) DFS(G, G.ToVertex(e)); PostVisit(G,v); // 对顶点 v 的后访问 9

10 广度优先遍历广度优先搜索 (breadth-first search, 简称 BFS) 其遍历的过程是 : 从图中的某个顶点 v 0 出发访问并标记了顶点 v 0 之后一层层横向搜索 v 0 的所有邻接点对这些邻接点一层层横向搜索, 直至所有由 v 0 有路径可达的顶点都已被访问过再选取其他未访问顶点作为源点做广搜, 直到所有点都被访问过 10

11 图的广度优先遍历 (BFS) 算法 void BFS(Graph& G, int v) { using std::queue; queue<int> Q; // 使用 STL 中的队列 Visit(G,v); // 访问顶点 v G.Mark[v] = VISITED; Q.push(v); // 标记, 并入队列 while (!Q.empty()) { // 如果队列非空 int u = Q.front (); // 获得队列顶部元素 Q.pop(); // 队列顶部元素出队 for (Edge e = G.FirstEdge(u); G.IsEdge(e); e = G.NextEdge(e)) // 所有未访问邻接点入队 if (G.Mark[G.ToVertex(e)] == UNVISITED){ Visit(G, G.ToVertex(e)); G.Mark[G.ToVertex(e)] = VISITED; Q.push(G.ToVertex(e)); } }} 11

12 图搜索的时间复杂度 DFS 和 BFS 每个顶点访问一次, 对每一条边处理一次 ( 无向图的每条边从两个方向处理 ) 采用邻接表表示时, 有向图总代价为 Θ(n + e), 无向图为 Θ(n + 2e) 采用相邻矩阵表示时, 处理所有的边需要 Θ(n 2 ) 的时间, 所以总代价为 Θ(n + n 2 ) = Θ(n 2 ) 12

13 拓扑排序对于有向无环图 G= (V,E),V 里顶点的线性序列称作一个拓扑序列, 该顶点序列满足 : 若在有向无环图 G 中从顶点 v i 到 v j 有一条路径, 则在序列中顶点 v i 必在顶点 v j 之前拓扑排序 (topological sort) 将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序 13

14 课程代号课程名称先修课程 C1 高等数学 C2 程序设计 C3 离散数学 C1,C2 C4 数据结构 C2,C3 C5 算法分析 C2 C6 编译技术 C4,C5 C7 操作系统 C4,C9 C8 普通物理 C1 C9 计算机原理 C8 14

15 拓扑排序图例学生课程的安排图 c8 c9 c1 c3 c4 c7 c2 c5 c6 15

16 拓扑排序方法任何有向无环图 (DAG), 其顶点都可以排在一个拓扑序列里, 其拓扑排序的方法是 : (1) 从图中选择任意一个入度为 0 的顶点且输出之 (2) 从图中删掉此顶点及其所有的出边, 将其入度减少 1 (3) 回到第 (1) 步继续执行 16

17 用队列实现的图拓扑排序 void TopsortbyQueue(Graph& G) { for (int i = 0; i < G.VerticesNum(); i++) G.Mark[i] = UNVISITED; // 初始化 using std::queue; queue<int> Q; // 使用 STL 中的队列 for (i = 0; i < G.VerticesNum(); i++) // 入度为 0 的顶点入队 if (G.Indegree[i] == 0) Q.push(i); while (!Q.empty()) { // 如果队列非空 int v = Q.front(); Q.pop(); // 获得队列顶部元素, 出队 Visit(G,v); G.Mark[v] = VISITED; // 将标记位设置为 VISITED for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) { G.Indegree[G.ToVertex(e)]--; // 相邻的顶点入度减 1 if (G.Indegree[G.ToVertex(e)] == 0) // 顶点入度减为 0 则入队 Q.push(G.ToVertex(e)); } } for (i = 0; i < G.VerticesNum(); i++) // 判断图中是否有环 if (G.Mark[i] == UNVISITED) { cout<< 此图有环! ; break; } } 17

18 c1 c2 按结点编号深度优先 : C6 C7 C4 C3 C9 C8 C1 C5 C2 c8 c3 c5 c4 c6 c9 c7 置逆, 拓扑序列为 : C2,C5,C1,C8,C9,C3,C4,C7,C6 18

19 深度优先搜索实现的拓扑排序 int *TopsortbyDFS(Graph& G) { for(int i=0; i<g.verticesnum(); i++) G.Mark[i] = UNVISITED; int *result=new int[g.verticesnum()]; int index=0; for(i=0; i<g.verticesnum(); i++) if(g.mark[i] == UNVISITED) Do_topsort(G, i, result, index); for(i=g.verticesnum()-1; i>=0; i--) Visit(G, result[i]); return result; } 19 // 结果是颠倒的 // 初始化 // 对所有顶点 // 递归函数 // 逆序输出

20 拓扑排序递归函数 void Do_topsort(Graph& G, int V, int *result, int& index) { G.Mark[V] = VISITED; for (Edge e = G.FirstEdge(V); G.IsEdge(e); e=g.nextedge(e)) { if (G.Mark[G.ToVertex(e)] == UNVISITED) Do_topsort(G, G.ToVertex(e), result, index); } result[index++]=v; // 相当于后处理 } 20

21 拓扑排序的时间复杂度与图的深度优先搜索方式遍历相同图的每条边处理一次图的每个顶点访问一次采用邻接表表示时, 为 Θ(n + e) 采用相邻矩阵表示时, 为 Θ(n 2 ) 21

22 是否支持有向图无向图有回路的图非连通图权值为负如果不支持则修改方案? 图算法需要考虑的问题 22

23 必须是有向图必须是无环图支持非连通图不用考虑权值回路递归与非递归的拓扑排序非递归的算法, 最后判断 ( 若还有顶点没有输出, 肯定有回路 ) 递归的算法要求判断有无回路 23

24 队列实现的拓扑排序讨论怎么知道图中所有顶点的入度? 是否可以用栈来取代队列? 24

25 深度优先搜索拓扑排序讨论对于起始点是否有要求? 是否可以处理有环的情况? B A C 25

26 数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

Microsoft Word - 专升本练习5：图.doc

Microsoft Word - 专升本练习5：图.doc 第五章图一选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e