数据结构课件C++版第八章图幻灯片.ppt

步骤 (v, u) E T 6 (2, 3) ② ① ④ ⑤ ③ 6 6 5 6 ⑥ 边数=n-1=5 代价=(1+2+3+4+5)=15 ② ① ④ ⑤ ③ ⑥ 1 2 3 4 5 普里姆算法（Prim）时间复杂度O(n2),，只与图中顶点个数有关，适用于顶点不多而边稠密的图 克鲁斯卡尔算法（Kruskal）时间复杂度O(elog2e ),只与边数有关，适用于稀疏图 8.6 最短路径 算法步骤： 1. 用cost 初始化dist；置S={V0}； 2. 选择Vj,使得：dist[j]=Min{dist[i]|Vi∈V-S} Vj 就是当前求得的从V0出发的最短路径的终点，并将Vj并入S； 3. 对V-S上的所有顶点Vk，修改： dist[k]=Min{dist[j]+cost[j, k], dist[k]} 4. 重复2，3， n-1次。 在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题 一、某个源点到其余各顶点的最短路径算法 迪杰特拉（Dijkstra） 算法： 8.6 最短路径 例子 0 5 10 50 30 100 60 10 20 cost 0 1 2 3 4 5 10 5 50 20 30 100 10 60 0 1 2 3 4 5 终点 从v0 到各终点的 dist 值和最短路径 v1 v2 v4 v3 v5 vj 60(v0,v4,v3,v5) v5 50(v0,v4,v3) 90(v0,v4,v5) v3 10(v0,v2) 30(v0,v4) 100(v0,v5) v2 ∞ 60(v0,v2,v3) v4 30(v0,v4) 100(v0,v5) 8.6 最短路径 二、每一对顶点之间的最短路径 两种方法： 每次以一个顶点为源点，重复调用Dijkstra算法n次； 弗洛伊德算法(Floyed) 1.弗洛伊德算法思想：以A(0) [i,j]=cost[i,j] 递推出： A(k)[i,j]=Min{A(k-1)[i,j], A(k-1)[i,k]+ A(k-1) [k,j]},1≤k≤n 其中， A[k][i,j] 表示从 vi到vj 的中间顶点的序号不大于k 的最短路径长度。最后得到的A[n][i,j]就是从vi 到vj 的最短路径长度。 8.6 最短路径 2.例子 4 11 6 2 3 6 4 3 11 2 A B C 1 2 3 A(0) A(1) A(2) A(3) A 4 11 6 6 2 5 3 7 1 2 3 1 2 3 1 2 3 1 2 3 ∞ ∞ ∞ 3 7 4 6 2 A D B C 1 A 2 D 3 B 4 C 1 2 3 4 4 ^ 3 ^ 1 ^ 1 ^ 有向图 1 A 2 D ^ 3 B 4 C 2 3 ^ 1 ^ 4 ^ 邻接表 逆邻接表 与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧尾的各个弧头顶点 特点： 1. n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2. 第i条链表上的结点数，为Vi的出度（求顶点的出度易，求入度难） 插入顶点－InsertVertex() template class T void GraphT::InsertVertex(const T vertex) { Vertices[numVertices].data = vertex;numVertices++; } E D C B A 0 1 2 3 4 1 ^ 2 2 ^ 3 0 3 1 ^ 4 ^ 4 ^ 2 插入边－InsertEdge() void AdjTWGraph::InsertEdge(const int v1,const int v2,int weight) { if(v1 0|| v1 numVertices || v2 0|| v2 numVertices) { cerr 参数v1或v2越界出错 endl;