prim算法
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
中文名 普里姆算法 外文名 Prim Algorithm 别 称 最小生成树算法 提出者 沃伊捷赫·亚尔尼克（Vojtěch Jarník） 提出时间 1930年 应用学科 计算机，数据结构，数学（图论） 适用领域范围 应用图论知识的实际问题 算 法 贪心
目录
1 算法描述
2 时间复杂度
3 图例描述
4 代码
▪ PASCAL代码
▪ c代码
▪ C++代码
5 时间复杂度
算法描述编辑
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边
b.将v加入集合Vnew中，将
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
* 邻接矩阵存储 - Prim最小生成树算法 */ Vertex FindMinDist( MGraph Graph, WeightType dist[] ) { /* 返回未被收录顶点中dist最小者 */ Vertex MinV, V; WeightType MinDist = INFINITY; for (V=0; V<Graph->Nv; V++) { if ( dist[V]!=0 && dist[V]<MinDist) { /* 若V未被收录，且dist[V]更小 */ MinDist = dist[V]; /* 更新最小距离 */ MinV = V; /* 更新对应顶点 */ } } if (MinDist < INFINITY) /* 若找到最小dist */ return MinV; /* 返回对应的顶点下标 */ else return ERROR; /* 若这样的顶点不存在，返回-1作为标记 */ } int Prim( MGraph Graph, LGraph MST ) { /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */ WeightType dist[MaxVertexNum], TotalWeight; Vertex parent[MaxVertexNum], V, W; int VCount; Edge E; /* 初始化。默认初始点下标是0 */ for (V=0; V<Graph->Nv; V++) { /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */ dist[V] = Graph->G[0][V]; parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ } TotalWeight = 0; /* 初始化权重和 */ VCount = 0; /* 初始化收录的顶点数 */ /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */ MST = CreateGraph(Graph->Nv); E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */ /* 将初始点0收录进MST */ dist[0] = 0; VCount ++; parent[0] = -1; /* 当前树根是0 */ while (1) { V = FindMinDist( Graph, dist ); /* V = 未被收录顶点中dist最小者 */ if ( V==ERROR ) /* 若这样的V不存在 */ break; /* 算法结束 */ /* 将V及相应的边<parent[V], V>收录进MST */ E->V1 = parent[V]; E->V2 = V; E->Weight = dist[V]; InsertEdge( MST, E ); TotalWeight += dist[V]; dist[V] = 0; VCount++; for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */ if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) { /* 若W是V的邻接点并且未被收录 */ if ( Graph->G[V][W] < dist[W] ) { /* 若收录V使得dist[W]变小 */ dist[W] = Graph->G[V][W]; /* 更新dist[W] */ parent[W] = V; /* 更新树 */ } } } /* while结束*/ if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */ TotalWeight = ERROR; return TotalWeight; /* 算法执行完毕，返回最小权重和或错误标记 */ } |
kruskal算法
基本思想编辑
先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。 [1]
步骤编辑
新建图G，G中拥有原图中相同的节点，但没有边；
将原图中所有的边按权值从小到大排序；
从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中；
重复3，直至图G中所有的节点都在同一个连通分量中。
证明编辑
这样的步骤保证了选取的每条边都是桥，因此图G构成一个树。
为什么这一定是最小生成树呢？关键还是步骤3中对边的选取。算法中总共选取了n-1条边，每条边在选取的当时，都是连接两个不同的连通分量的权值最小的边
要证明这条边一定属于最小生成树，可以用反证法：如果这条边不在最小生成树中，它连接的两个连通分量最终还是要连起来的，通过其他的连法，那么另一种连法与这条边一定构成了环，而环中一定有一条权值大于这条边的边，用这条边将其替换掉，图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
/* 邻接表存储 - Kruskal最小生成树算法 */ /*-------------------- 顶点并查集定义 --------------------*/ typedef Vertex ElementType; /* 默认元素可以用非负整数表示 */ typedef Vertex SetName; /* 默认用根结点的下标作为集合名称 */ typedef ElementType SetType[MaxVertexNum]; /* 假设集合元素下标从0开始 */ void InitializeVSet( SetType S, int N ) { /* 初始化并查集 */ ElementType X; for ( X=0; X<N; X++ ) S[X] = -1; } void Union( SetType S, SetName Root1, SetName Root2 ) { /* 这里默认Root1和Root2是不同集合的根结点 */ /* 保证小集合并入大集合 */ if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */ S[Root2] += S[Root1]; /* 集合1并入集合2 */ S[Root1] = Root2; } else { /* 如果集合1比较大 */ S[Root1] += S[Root2]; /* 集合2并入集合1 */ S[Root2] = Root1; } } SetName Find( SetType S, ElementType X ) { /* 默认集合元素全部初始化为-1 */ if ( S[X] < 0 ) /* 找到集合的根 */ return X; else return S[X] = Find( S, S[X] ); /* 路径压缩 */ } bool CheckCycle( SetType VSet, Vertex V1, Vertex V2 ) { /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */ Vertex Root1, Root2; Root1 = Find( VSet, V1 ); /* 得到V1所属的连通集名称 */ Root2 = Find( VSet, V2 ); /* 得到V2所属的连通集名称 */ if( Root1==Root2 ) /* 若V1和V2已经连通，则该边不能要 */ return false; else { /* 否则该边可以被收集，同时将V1和V2并入同一连通集 */ Union( VSet, Root1, Root2 ); return true; } } /*-------------------- 并查集定义结束 --------------------*/ /*-------------------- 边的最小堆定义 --------------------*/ void PercDown( Edge ESet, int p, int N ) { /* 改编代码4.24的PercDown( MaxHeap H, int p ) */ /* 将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆 */ int Parent, Child; struct ENode X; X = ESet[p]; /* 取出根结点存放的值 */ for( Parent=p; (Parent*2+1)<N; Parent=Child ) { Child = Parent * 2 + 1; if( (Child!=N-1) && (ESet[Child].Weight>ESet[Child+1].Weight) ) Child++; /* Child指向左右子结点的较小者 */ if( X.Weight <= ESet[Child].Weight ) break; /* 找到了合适位置 */ else /* 下滤X */ ESet[Parent] = ESet[Child]; } ESet[Parent] = X; } void InitializeESet( LGraph Graph, Edge ESet ) { /* 将图的边存入数组ESet，并且初始化为最小堆 */ Vertex V; PtrToAdjVNode W; int ECount; /* 将图的边存入数组ESet */ ECount = 0; for ( V=0; V<Graph->Nv; V++ ) for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) if ( V < W->AdjV ) { /* 避免重复录入无向图的边，只收V1<V2的边 */ ESet[ECount].V1 = V; ESet[ECount].V2 = W->AdjV; ESet[ECount++].Weight = W->Weight; } /* 初始化为最小堆 */ for ( ECount=Graph->Ne/2; ECount>=0; ECount-- ) PercDown( ESet, ECount, Graph->Ne ); } int GetEdge( Edge ESet, int CurrentSize ) { /* 给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆 */ /* 将最小边与当前堆的最后一个位置的边交换 */ Swap( &ESet[0], &ESet[CurrentSize-1]); /* 将剩下的边继续调整成最小堆 */ PercDown( ESet, 0, CurrentSize-1 ); return CurrentSize-1; /* 返回最小边所在位置 */ } /*-------------------- 最小堆定义结束 --------------------*/ int Kruskal( LGraph Graph, LGraph MST ) { /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */ WeightType TotalWeight; int ECount, NextEdge; SetType VSet; /* 顶点数组 */ Edge ESet; /* 边数组 */ InitializeVSet( VSet, Graph->Nv ); /* 初始化顶点并查集 */ ESet = (Edge)malloc( sizeof(struct ENode)*Graph->Ne ); InitializeESet( Graph, ESet ); /* 初始化边的最小堆 */ /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */ MST = CreateGraph(Graph->Nv); TotalWeight = 0; /* 初始化权重和 */ ECount = 0; /* 初始化收录的边数 */ NextEdge = Graph->Ne; /* 原始边集的规模 */ while ( ECount < Graph->Nv-1 ) { /* 当收集的边不足以构成树时 */ NextEdge = GetEdge( ESet, NextEdge ); /* 从边集中得到最小边的位置 */ if (NextEdge < 0) /* 边集已空 */ break; /* 如果该边的加入不构成回路，即两端结点不属于同一连通集 */ if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==true ) { /* 将该边插入MST */ InsertEdge( MST, ESet+NextEdge ); TotalWeight += ESet[NextEdge].Weight; /* 累计权重 */ ECount++; /* 生成树中边数加1 */ } } if ( ECount < Graph->Nv-1 ) TotalWeight = -1; /* 设置错误标记，表示生成树不存在 */ return TotalWeight; } |
