普里姆算法c
把main函数改成：
main(){
GraphMatrix graph = {
"abcd",
{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},
};
Edge mst[Max];
int i,j;
prim(graph,mst);
for(j=0;j<Max;j++)
{
printf("%c\t",mst[j].stop_vex);
printf("%c\t",mst[j].start_vex);
printf("%d\n",mst[j].weight);
}
}
还有GraphMatrix结构体里的vexs数组最好定义为vexs[VN+1]给字符串末尾的‘\0'留地方。
2. 普里姆算法是什么
普里姆(Prim)算法，和克鲁斯卡尔算法一样，是用来求加权连通图的最小生成树的算法。
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。
该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
基本思想：
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。
从所有uЄU，vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。
3. 用c语言描述prim算法求最小生成树.... 求高人指点啊，给出完整的代码，那个邻接矩阵是要要一次全部输入的
#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=102;
const int inf=1<<30;
int map[maxn][maxn];
int dis[maxn];
bool flag[maxn];
int a,b,c,n,m,ans;
void init()
{
memset(map,-1,sizeof(map));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]==-1 || c< map[a][b])
{
map[a][b]=map[b][a]=c;
}
}
}
void prim()
{
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
ans=0;
for(int j=1;j<=n;j++)
{
int now,value=inf;
for(int i=1;i<=n;i++)
{
if(flag[i]==false && dis[i]<value)
{
value=dis[i];
now=i;
}
}
if(value==inf)
{
cout << "-1" <<endl;
return;
}
flag[now]=true;
ans+=dis[now];
for(int i=1;i<=n;i++)
{
if(!flag[i] && map[now][i]!=-1 && dis[i]>map[now][i])
dis[i]=map[now][i];
}
}
cout << ans <<endl;
}
int main()
{
//'freopen("in.txt","r",stdin);
while(cin >> n >> m)
{
init();
prim();
}
return 0;
}
测试数据：
Sample Input
3 3
1 2 1
1 3 1
2 3 3
Sample Output
2
既然问到了prim算法相信你能看懂测试数据是什么意思~
4. 普里姆算法
你要先明白prim算法的原理，明白原理后看下面的程序要点：
1.程序实现的时候将点分成两部分，加入集合的和没有加入集合的；
2.每次从没有加入集合中找点；
3.对所有没有加入到集合中的点中，找一个边权最小的；
4.将边权最小的点加入集合中，并且修改和加入点相连的没有加入的点的权，重复第2步，知道所有的点都加入到集合中；
5. 关于PRIM算法求最小生成树的问题（c语言版）
/*
邻接矩阵存储图
测试数据
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 <stdio.h>
#include <limits.h>
#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;
}
要求出所有的最小生成树。。貌似有点麻烦。。