- 算法设计与分析
- 家
- 算法基础知识
- DAA - 简介
- DAA - 算法分析
- DAA-分析方法
- 渐近符号和先验分析
- 时间复杂度
- 马斯特定理
- DAA - 空间复杂性
- 分而治之
- DAA-分而治之
- DAA - 最大最小问题
- DAA-归并排序
- DAA-二分查找
- 施特拉森矩阵乘法
- 唐叶算法
- 河内塔
- 贪心算法
- DAA-贪婪法
- 旅行商问题
- Prim 的最小生成树
- 克鲁斯卡尔的最小生成树
- Dijkstra 的最短路径算法
- 地图着色算法
- DAA-分数背包
- DAA - 带截止日期的作业排序
- DAA - 最佳合并模式
- 动态规划
- DAA-动态规划
- 矩阵链乘法
- 弗洛伊德·沃歇尔算法
- DAA - 0-1 背包
- 最长公共子序列
- 旅行商问题| 动态规划
- 随机算法
- 随机算法
- 随机快速排序
- 卡格的最低削减
- 费舍尔-耶茨洗牌
- 近似算法
- 近似算法
- 顶点覆盖问题
- 设置封面问题
- 旅行推销员近似算法
- 排序技巧
- DAA-快速排序
- DAA-冒泡排序
- DAA——插入排序
- DAA-选择排序
- DAA——希尔排序
- DAA-堆排序
- DAA——桶排序
- DAA——计数排序
- DAA - 基数排序
- 搜索技巧
- 搜索技术介绍
- DAA - 线性搜索
- DAA-二分查找
- DAA - 插值搜索
- DAA - 跳转搜索
- DAA - 指数搜索
- DAA - 斐波那契搜索
- DAA - 子列表搜索
- DAA-哈希表
- 图论
- DAA-最短路径
- DAA - 多级图
- 最优成本二叉搜索树
- 堆算法
- DAA-二叉堆
- DAA-插入法
- DAA-Heapify 方法
- DAA-提取方法
- 复杂性理论
- 确定性计算与非确定性计算
- DAA-最大派系
- DAA - 顶点覆盖
- DAA - P 级和 NP 级
- DAA-库克定理
- NP 硬课程和 NP 完全课程
- DAA - 爬山算法
- DAA 有用资源
- DAA - 快速指南
- DAA - 有用的资源
- DAA - 讨论
Prim 的最小生成树
Prim 的最小生成树算法是查找图的最小生成树的有效方法之一。最小生成树是一个子图,它将主图中存在的所有顶点与最少可能的边和最小成本(分配给每个边的权重之和)连接起来。
该算法与任何最短路径算法类似,从设置为根的顶点开始,通过确定成本最低的相邻边遍历图中的所有顶点。
普里姆算法
为了执行 prim 算法,算法采用的输入是图 G {V, E},其中 V 是顶点集,E 是边集,以及源顶点 S。图 G 的最小生成树作为输出获得。
算法
声明一个数组Visited [] 来存储访问过的顶点,首先将任意根(例如 S)添加到访问过的数组中。
检查最后访问的顶点的相邻顶点是否存在于访问的[]数组中。
如果顶点不在visited []数组中,则比较边的成本,并将成本最小的边添加到输出生成树中。
具有最小成本边的相邻未访问顶点被添加到visited []数组中,并且最小成本边被添加到最小生成树输出中。
对图中所有未访问的顶点重复步骤 2 和 4,以获得给定图的完整最小生成树输出。
计算获得的最小生成树的成本。
例子
对于下面给出的以 S 作为任意根的图,使用 prim 方法(贪婪方法)查找最小生成树。
解决方案
步骤1
创建一个访问数组来存储所有访问过的顶点。
V = { }
任意根被称为 S,因此在连接到 S 的所有边中,我们需要找到成本最小的边。
S → B = 8 V = {S, B}
第2步
由于 B 是最后访问的,因此检查连接到顶点 B 的成本最低的边。
B → A = 9 B → C = 16 B → E = 14
因此,B → A 是添加到生成树的边。
V = {S, B, A}
步骤3
由于 A 是最后访问的,因此检查连接到顶点 A 的成本最低的边。
A → C = 22 A → B = 9 A → E = 11
但 A → B 已经在生成树中,检查下一个成本最低的边。因此,A→E被添加到生成树中。
V = {S, B, A, E}
步骤4
由于 E 是最后访问的,因此检查连接到顶点 E 的成本最低的边。
E → C = 18 E → D = 3
因此,E→D被添加到生成树中。
V = {S, B, A, E, D}
步骤5
由于 D 是最后访问的,因此检查连接到顶点 D 的最低成本边。
D → C = 15 E → D = 3
因此,D→C被添加到生成树中。
V = {S, B, A, E, D, C}
以最小成本=46得到最小生成树
例子
最终程序实现了 Prim 的最小生成树问题,该问题将成本邻接矩阵作为输入,并打印生成树作为输出以及最小成本。
#include<stdio.h> #include<stdlib.h> #define inf 99999 #define MAX 10 int G[MAX][MAX] = { {0, 19, 8}, {21, 0, 13}, {15, 18, 0} }; int S[MAX][MAX], n; int prims(); int main(){ int i, j, cost; n = 3; cost=prims(); printf("\nSpanning tree:"); for(i=0; i<n; i++) { printf("\n"); for(j=0; j<n; j++) printf("%d\t",S[i][j]); } printf("\nMinimum cost = %d", cost); return 0; } int prims(){ int C[MAX][MAX]; int u, v, min_dist, dist[MAX], from[MAX]; int visited[MAX],ne,i,min_cost,j; //create cost[][] matrix,spanning[][] for(i=0; i<n; i++) for(j=0; j<n; j++) { if(G[i][j]==0) C[i][j]=inf; else C[i][j]=G[i][j]; S[i][j]=0; } //initialise visited[],distance[] and from[] dist[0]=0; visited[0]=1; for(i=1; i<n; i++) { dist[i] = C[0][i]; from[i] = 0; visited[i] = 0; } min_cost = 0; //cost of spanning tree ne = n-1; //no. of edges to be added while(ne > 0) { //find the vertex at minimum distance from the tree min_dist = inf; for(i=1; i<n; i++) if(visited[i] == 0 && dist[i] < min_dist) { v = i; min_dist = dist[i]; } u = from[v]; //insert the edge in spanning tree S[u][v] = dist[v]; S[v][u] = dist[v]; ne--; visited[v]=1; //updated the distance[] array for(i=1; i<n; i++) if(visited[i] == 0 && C[i][v] < dist[i]) { dist[i] = C[i][v]; from[i] = v; } min_cost = min_cost + C[u][v]; } return(min_cost); }
输出
Spanning tree: 0 0 8 0 0 13 8 13 0 Minimum cost = 26
#include<iostream> #define inf 999999 #define MAX 10 using namespace std; int G[MAX][MAX] = { {0, 19, 8}, {21, 0, 13}, {15, 18, 0} }; int S[MAX][MAX], n; int prims(); int main(){ int i, j, cost; n = 3; cost=prims(); cout <<"Spanning tree:"; for(i=0; i<n; i++) { cout << endl; for(j=0; j<n; j++) cout << S[i][j] << " "; } cout << "\nMinimum cost = " << cost; return 0; } int prims(){ int C[MAX][MAX]; int u, v, min_dist, dist[MAX], from[MAX]; int visited[MAX],ne,i,min_cost,j; //create cost matrix and spanning tree for(i=0; i<n; i++) for(j=0; j<n; j++) { if(G[i][j]==0) C[i][j]=inf; else C[i][j]=G[i][j]; S[i][j]=0; } //initialise visited[],distance[] and from[] dist[0]=0; visited[0]=1; for(i=1; i<n; i++) { dist[i] = C[0][i]; from[i] = 0; visited[i] = 0; } min_cost = 0; //cost of spanning tree ne = n-1; //no. of edges to be added while(ne > 0) { //find the vertex at minimum distance from the tree min_dist = inf; for(i=1; i<n; i++) if(visited[i] == 0 && dist[i] < min_dist) { v = i; min_dist = dist[i]; } u = from[v]; //insert the edge in spanning tree S[u][v] = dist[v]; S[v][u] = dist[v]; ne--; visited[v]=1; //updated the distance[] array for(i=1; i<n; i++) if(visited[i] == 0 && C[i][v] < dist[i]) { dist[i] = C[i][v]; from[i] = v; } min_cost = min_cost + C[u][v]; } return(min_cost); }
输出
Spanning tree: 0 0 8 0 0 13 8 13 0 Minimum cost = 26
public class prims { static int inf = 999999; static int MAX = 10; static int G[][] = { {0, 19, 8}, {21, 0, 13}, {15, 18, 0} }; static int S[][] = new int[MAX][MAX]; static int n; public static void main(String args[]) { int i, j, cost; n = 3; cost=prims(); System.out.println("Spanning tree: "); for(i=0; i<n; i++) { System.out.println(); for(j=0; j<n; j++) System.out.print(S[i][j] + " "); } System.out.println("\nMinimum cost = " + cost); } static int prims() { int C[][] = new int[MAX][MAX]; int u, v = 0, min_dist; int dist[] = new int[MAX]; int from[] = new int[MAX]; int visited[] = new int[MAX]; int ne,i,min_cost,j; //create cost matrix and spanning tree for(i=0; i<n; i++) for(j=0; j<n; j++) { if(G[i][j]==0) C[i][j]=inf; else C[i][j]=G[i][j]; S[i][j]=0; } //initialise visited[],distance[] and from[] dist[0]=0; visited[0]=1; for(i=1; i<n; i++) { dist[i] = C[0][i]; from[i] = 0; visited[i] = 0; } min_cost = 0; //cost of spanning tree ne = n-1; //no. of edges to be added while(ne > 0) { //find the vertex at minimum distance from the tree min_dist = inf; for(i=1; i<n; i++) if(visited[i] == 0 && dist[i] < min_dist) { v = i; min_dist = dist[i]; } u = from[v]; //insert the edge in spanning tree S[u][v] = dist[v]; S[v][u] = dist[v]; ne--; visited[v]=1; //updated the distance[] array for(i=1; i<n; i++) if(visited[i] == 0 && C[i][v] < dist[i]) { dist[i] = C[i][v]; from[i] = v; } min_cost = min_cost + C[u][v]; } return(min_cost); } }
输出
Spanning tree: 0 0 8 0 0 13 8 13 0 Minimum cost = 26
inf = 999999 MAX = 10 G = [ [0, 19, 8], [21, 0, 13], [15, 18, 0] ] S = [[0 for _ in range(MAX)] for _ in range(MAX)] n = 3 def main(): global n cost = prims() print("Spanning tree: ") for i in range(n): print() for j in range(n): print(S[i][j], end=" ") print("\nMinimum cost =", cost) def prims(): global n C = [[0 for _ in range(MAX)] for _ in range(MAX)] u, v = 0, 0 min_dist = 0 dist = [0 for _ in range(MAX)] from_ = [0 for _ in range(MAX)] visited = [0 for _ in range(MAX)] ne = 0 min_cost = 0 i = 0 j = 0 for i in range(n): for j in range(n): if G[i][j] == 0: C[i][j] = inf else: C[i][j] = G[i][j] S[i][j] = 0 dist[0] = 0 visited[0] = 1 for i in range(1, n): dist[i] = C[0][i] from_[i] = 0 visited[i] = 0 min_cost = 0 ne = n - 1 while ne > 0: min_dist = inf for i in range(1, n): if visited[i] == 0 and dist[i] < min_dist: v = i min_dist = dist[i] u = from_[v] S[u][v] = dist[v] S[v][u] = dist[v] ne -= 1 visited[v] = 1 for i in range(n): if visited[i] == 0 and C[i][v] < dist[i]: dist[i] = C[i][v] from_[i] = v min_cost += C[u][v] return min_cost #calling the main() method main()
输出
Spanning tree: 0 0 8 0 0 13 8 13 0 Minimum cost = 26