Ch09-图论算法.ppt

图论算法 高文宇 gwyy@163.com §1 定义 图：图（Graph）G V, E 由顶点集V和边集E组成。一条边是一个点对 v, w ，其中v,w∈V。若点对是有序的，则称为弧（有向边），由有向边构成的图称为有向图。 顶点邻接（adjacent） 路径（path），简单路径，环，有向图的圈 无向图的连通，有向图的强连通，完全图 图的表示 邻接矩阵 邻接表 §2 拓扑排序 简单的拓扑排序伪代码 O |V|^2 改进的拓扑排序 O |E|+|V| §3 最短路径算法 单源最短路径问题：给定赋权图G V,E 和一个指定顶点s作为输入，要求找出从s到G中每一个顶点的最短赋权路径。 负权边对最短路径问题的影响？ 负权圈对最短路径问题的影响？ 无权最短路径 广度优先有哪些信誉好的足球投注网站 Dijkstra算法 Dijkstra算法：设源点为s，在每个阶段，算法选择一个顶点v，它在所有未知顶点中具有最小的dv，然后算法声明从s到v的最短路径已知。 Dijkstra算法 具有负权值的边 请给出负权值边影响的例子。 将一个常数?加到每条边上，以消除负权值边，可行吗？ 解决图中存在的负权边 将赋权和无权的算法结合起来。 无圈图 因为无圈图存在拓扑排序序列。因此当一个顶点v被标记为已知后，按照拓扑排序的规则，该顶点不可能存在其它进入的边，所以从s到v的距离dv也不可能再降低。 关键路径问题 所有点对间的最短路径 §4 网络流问题 〖Example〗 Consider the following network of pipes: §5 最小生成树 Prim算法 Prim算法 Kruskal算法 Kruskal算法 §6 深度优先有哪些信誉好的足球投注网站的应用 DFS 双连通性 欧拉回路 使用DFS 强连通分量 §7 NP完全性介绍 再见 再见 2 6 9 8 3 7 1 12 4 10 5 11 Note: The path should be maintained as a linked list. For each adjacency list, maintain a pointer to the last edge scanned. T O |E| + |V| Find a simple cycle in an undirected graph that visits every vertex – Hamilton cycle DFS * void Topsort Graph G int Counter; Vertex V, W; for Counter 0; Counter NumVertex; Counter ++ V FindNewVertexOfDegreeZero ; if V NotAVertex Error “Graph has a cycle” ; break; TopNum[ V ] Counter; /* or output V */ for each W adjacent to V Indegree[ W ] – – ; void Topsort Graph G Queue Q; int Counter 0; Vertex V, W; Q CreateQueue NumVertex ; MakeEmpty Q ; for each vertex V if Indegree[ V ] 0 Enqueue V, Q ; while !IsEmpty Q V Dequeue Q ; TopNum[ V ] ++ Counter; /* assign next */ for each W adjacent to V if – – Indegree[ W ] 0 Enqueue W, Q ; /* end-while */ if Counter ! NumVertex Error “Graph has a cycle” ; DisposeQueue Q ; /* free memory */ v1 v2 v6 v7 v3 v4 v5 2 4 2 1 3 10 2 5 8 4 6 1 v1 v2 v6 v7 v3 v4 v5 2 4 2 1 3 –10 2 5 8 4 6 1 void Unweighted Table T int CurrDist; Vertex V, W; for CurrDist 0; CurrDist NumVertex; CurrDist ++ for each vertex V if