精梳版5-图论算法1.ppt

Prim示例： V2 V0 V3 V5 V4 V1 V2 V0 V3 V5 V4 V1 1 U={v0} U={v0,v2} U={v0,v2,v5} U={v0,v2,v5,v3} U={v0,v2,v5,v3,v1} U={v0,v2,v5,v3,v1,v4} V3 V4 V1 4 1 V0 V2 V5 V4 V1 2 1 4 V0 V2 V5 V3 V4 1 4 2 5 V2 V0 V5 V1 V3 3 5 1 2 4 V2 V1 V0 V5 V3 V4 Kruskal思想： —最小生成树篇 1.将边按边树由小到大排序。 2.每次加最小边 不构成回路。 3.加进了n-1条边就得到了最小生成树 //Kruskal算法并不保证每步生成的结果是连通的（中间结果可能不是树）。 Kruskal程序基本结构： 优先队列+并查集 Kruscal 示例： 实例的执行过程 1 2 4 3 5 6 6 1 6 5 5 5 6 3 4 2 1、初始连通分量：{1},{2},{3},{4},{5},{6} 2、反复执行添加、放弃动作。条件：边数不等于 n-1时 边 动作 连通分量 (1,3) 添加 {1,3},{4},{5},{6},{2} (4,6) 添加 {1,3},{4, 6},{2},{5} (2,5) 添加 {1,3},{4, 6},{2,5} (3,6) 添加 {1,3,4, 6},{2,5} (1,4) 放弃 因构成回路 (3,4) 放弃 因构成回路 (2,3) 添加 {1,3,4,5,6,2} 1 2 4 3 5 6 1 5 3 4 2 5 5 算法实现要点: 用并查集的相关操作：实现集合的并；判断新边的两端点是否处于同一集合，来确定是否构成回路。 最短路径 (Shortest Path): 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 边上权值非负情形的单源最短路径问题 — Dijkstra算法 边上权值为任意值的单源最短路径问题 — Bellman-Ford算法 所有顶点之间的最短路径 — Floyd算法 Dijkstra思想： —最短路径篇 初始化： S ← { v0 };dist[j] ← Edge[0][j], j = 1, 2, …, n-1; 1、求出最短路径的长度： dist[k] ← min{ dist[i] }, i ? V- S ; S ← S U { k }; 2、 修改： dist[i] ←min{ dist[i], dist[k] + Edge[k][i] }, for i?V- S ; 3、 判断： 若S = V, 则算法结束，否则转1。 引入一个辅助数组dist。dist[i]表示当前从源点v0到终点vi 的最短路径的长度。时间复杂度:O(V2) Dijkstra程序基本结构： void disktra(int v)//原点是v { bool s[maxn]; register int i,j,k; for(i=1;i=n;i++){ dist[i] = c[v][i]; s[i] = 0; // i不在集合S中 if(dist[i]==manint)//v to i没有边 prev[i] = 0; else prev[i] = v; } s[v] = 1; dist[v] = 0; for(i=1;in;i++){ int temp = manint, u = v; for(j=1;j=n;j++) if(!s[j]dist[j]dist[j]temp){ u = j; temp = dist[j]; } s[u] = 1; for(j=1;j=n;j++) if(!s[j]c[u][j]manint){ int newdist = dist[u] + c[u][j]; if(newdist dist[j]){ dist[j] = newdist; prev[j] = u; } } } } 结点从1开始计，maxn为最大结点数,