用prim算法构建最小生成树适合顶点数据较少而边较多的图(稠密图)
prim算法生成连通图的最小生成树模板伪代码:
G为图,一般为全局变量,数组d为顶点与集合s的最短距离 Prim(G, d[]){ 初始化; for (循环n次){ u = 使d[u]最小的还未访问的顶点的标号; 记u 已被访问; for(从u出发到达的所有顶点v){ if (v未被访问&&以u为中介点使得v与集合S的嘴短距离d[v]更优){ 将G[u][v]赋值给v与结合S的最短距离d[v]; } } } }
邻接矩阵版:
1 //邻接矩阵版 2 const int MAXV = 1000; //最大顶点数 3 const int INF = 1000000; //设INF为一个很大的数 4 5 int n,m, G[MAXV][MAXV]; //n为顶点数,G为图 6 int d[MAXV]; //顶点与集合S的最短距离 7 bool vis[MAXV] = { false }; 8 9 //默认0号为初始点,函数返回最小生成树的边权之和 10 int prim(){ 11 //初始化 12 fill(d, d + MAXV, INF); 13 d[0] = 0; 14 int ans = 0; //存放最小生成树的边权之和 15 //遍历所有的顶点,每次遍历访问一个顶点 16 for (int i = 0; i < n; i++){ 17 //找出当前还未访问但是距离集合S最近的顶点 18 int u = -1, MIN = INF; 19 for (int j = 0; j < n; j++){ 20 if (vis[j] == false && d[j] < MIN){ 21 u = j; 22 MIN = d[j]; 23 } 24 } 25 26 //如果找不到这样的顶点 27 if (u == -1) return -1; 28 29 //标记这个顶点为已访问 30 vis[u] = true; 31 ans += d[u]; 32 33 //遍历这个顶点的邻接点,如果没有访问且距离集合S更近,更新d[u] 34 for (int j = 0; j < n; j++){ 35 if (vis[j] == false && G[u][j] != INF && G[u][j] < d[j]){ 36 d[j] = G[u][j]; 37 } 38 } 39 } 40 41 return ans; 42 }
邻接表模板:
1 const int MAXV = 1010; 2 const int INF = 1000000; 3 4 struct Node{ 5 int v, dis; //v为边的目标顶点,dis为权 8 }; 9 10 vector<Node> Adj[MAXV]; 11 int n, m; 12 int d[MAXV]; 13 bool vis[MAXV] = { false }; 14 15 int prim(){ 16 fill(d, d + MAXV, INF); 17 d[0] = 0; 18 int ans = 0; 19 20 for (int i = 0; i < n; i++){ 21 int u = -1, MIN = INF; 22 for (int j = 0; j < n; j++){ 23 if (vis[j] == false && d[j] < MIN){ 24 u = j; 25 MIN = d[j]; 26 } 27 } 28 29 if (u == -1) return -1; 30 vis[u] = true; 31 ans += d[u]; 32 for (int j = 0; j < Adj[u].size(); j++){ 33 int v = Adj[u][j].v; 34 if (vis[v] == false && Adj[u][j].dis < d[v]){ 35 d[v] = Adj[u][j].dis; 36 } 37 } 38 } 39 return ans; 40 }