图的最小生成树算法(Prim和Kruskal)

图的邻接矩阵表示法可参考： >

<1,6>边长度未知，这里看成无穷大。

历次循环中，选择两端点分别在U，V中的边中长度最小者，

具体如下：

1 将1加入U中，其余点加入V中。

2 选择边<1,7>，将7加入U中，从V中除去该点。

3 选择边<7,6>，将6加入U中，从V中除去该点。

4 选择边<1,2>，将2加入U中，从V中除去该点。

5 选择边<2,3>，将3加入U中，从V中除去该点。

6 选择边<2,4>，将4加入U中，从V中除去该点。

7 选择边<2,5>，将5加入U中，从V中除去该点。

结束。由上述六条边组成的树为求得的最小生成树。

>

最近忙着考试，没时间做图形界面来动态演示部分啦，先给你一个基本的Prim程序吧，希望有所帮助。

/

PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree)

输入：图g； // 有向图或者无向图

输出：(1)最小生成树长sum；

(2)最小生成树prev。

结构: 图g用邻接矩阵表示，最短边长dist用数组表示。

算法：Prim算法

复杂度：O(|V|^2)

/

#include <iostream>

#include <vector>

#include <list>

#include <iterator>

#include <algorithm>

#include <numeric>

#include <functional>

#include <climits>

using namespace std;

int n; // n : 顶点个数

vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)

vector<bool> known; // known : 各点是否已经选取

vector<int> dist; // dist : 已选取点集到未选取点的最小边长

vector<int> prev; // prev : 最小生成树中各点的前一顶点

int s; // s : 起点(start)

int sum; // sum : 最小生成树长

bool Prim() // 贪心算法(Greedy Algorithm)

{

knownassign(n, false);

distassign(n, INT_MAX);

prevresize(n); // 初始化known、dist、prev。

dist[s] = 0; // 初始化起点到自身的路径长为0。

int i;

for (i = 0; i < n; ++i)

{

int min = INT_MAX, v;

for (int i = 0; i < n; ++i)

if (!known[i] && min > dist[i])

min = dist[i], v = i; // 寻找未知的最短路径长的顶点v，

if (min == INT_MAX) break; // 如果找不到，退出；

known[v] = true; // 如果找到，将顶点v设为已知，

sum += dist[v]; // 调整最小生成树长

for (int w = 0; w < n; ++w) // 遍历所有v指向的顶点w，

if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])

dist[w] = g[v][w], prev[w] = v; / 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。 /

}

return i == n; // 如果选取顶点个数为n，成功。

}

int main()

{

n = 7;

gassign(n, vector<int>(n, INT_MAX));

g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;

g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;

g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;

g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;

g[4][6] = g[6][4] = 6;

g[5][6] = g[6][5] = 1;

s = 0; // 起点任选

sum = 0;

if (Prim())

{

cout << sum << endl;

for (int i = 1; i < n; ++i)

if(i != s) cout << prev[i] << "->" << i << endl;

}

else

{

cout << "Some vertex cann't be reached" << endl;

}

system("pause");

return 0;

}

/

邻接矩阵存储图

测试数据

6 10

1 2 6

1 3 1

1 4 5

2 3 5

2 5 3

3 4 5

3 5 6

3 6 4

4 6 2

5 6 6

/

#include <stdioh>

#include <limitsh>

#define N 100

int p[N], key[N], tb[N][N];

void prim(int v, int n)

{

int i, j;

int min;

for (i = 1; i <= n; i++)

{

p[i] = v;

key[i] = tb[v][i];

}

key[v] = 0;

for (i = 2; i <= n; i++)

{

min = INT_MAX;

for (j = 1; j <= n; j++)

if (key[j] > 0 && key[j] < min)

{

v = j;

min = key[j];

}

printf("%d%d ", p[v], v);

key[v] = 0;

for (j = 1; j <= n; j++)

if (tb[v][j] < key[j])

p[j] = v, key[j] = tb[v][j];

}

}

int main()

{

int n, m;

int i, j;

int u, v, w;

while (scanf("%d%d", &n, &m))

{

for(i = 1; i <= n; i++)

{

for (j = 1; j <= n; j++)

tb[i][j] = INT_MAX;

}

while (m--)

{

scanf("%d%d%d", &u, &v, &w);

tb[u][v] = tb[v][u] = w;

}

prim(1, n);

printf("\n");

}

return 0;

}

要求出所有的最小生成树。。貌似有点麻烦。。

以上就是关于图的最小生成树算法(Prim和Kruskal)全部的内容，包括:图的最小生成树算法(Prim和Kruskal)、用prim算法的思想，用C语言编写出最小生成树的方法的代码、利用普里姆算法求解最小生成树，写出步骤或画图表示过程。等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！