文档介绍：西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China ACM/ICPC 程序设计简单算法计算机学院张淑平西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 图论-算法图的遍历 BFS( 广搜) DFS( 深搜)最小生成树 Prim Kruskal 最短路径 Bellman-Ford Dijkstra Floyd-Warshall ? BFS 练****DFS 练****Prim 练****Kruskal 练****Bellman-Ford 练****Dijkstra 练****Floyd-Warshall 练****西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 图的遍历?遍历要访问到图中的每一个顶点。? BFS (Breadth-First Search) ? DFS (Depth-First Search) 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China BFS 思想—遍历篇? v 0出发,在访问了 v 0之后,搜索 v 0 的(所有未被访问的)邻接顶点 …? ,广搜图中其它顶点, 直至图中所有已被访问的顶点的邻接顶点都被访问到。? ,则再选择其中之一作为 v0 重复上述过程。直到图中所有顶点均被访问到。// 搜索过程没有回溯,是一种牺牲空间换取时间的方法。时间复杂度: O(V+E) 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China BFS 程序基本结构定义一个队列;起始点加入队列; while( 队列不空){ 取出队头结点;若它是所求的目标状态,跳出循环; 否则,从它扩展出子结点,全都添加到队尾; }若循环中找到目标,输出结果;否则输出无解; 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China BFS 示例: 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China DFS 思想—遍历篇? G中每个顶点标记为未被访问,选取一个顶点 v作为搜索起点,标记其为已访问? v的每个未被访问过的邻接顶点,直到从v出发所有可达的顶点都已被访问过。? ,则再选择其中之一作为 v重复上述过程。直到图中所有顶点均被访问到。 // 时间复杂度: O(V+E) 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China DFS 程序基本结构 void DFS(int step) { for(i=0; i<Max_Elements; i++) { if( 子结点符合条件){新子结点入栈; if( 是目标结点)输出 else DFS(step+1); 子结点出栈}}} 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China DFS 示例西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小生成树( Minimum Spanning Tree ) ? G(V,E) 是无向连通赋权图, G’(V,E ’)是包含 G中所有顶点的树,且树中各边权总和最小,则 G’是最小生成树(可能不唯一) ?容易想到,用贪心策略。 Prim Kruskal