关于PRIM算法求最小生成树的问题c语言版

[怎样生成最小的DirectFB]本文介绍了怎样生成一个最小（或接近最小）的DirectFB，以及相关的测试用例的安装和测试，对编译中的参数MMX，SSE，SDL，VNC的概念给出了较为详细的介绍实验平台： FC5（Fedora Core5） Direct...+阅读

邻接矩阵存储图

测试数据

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

#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算法求出图的最小生成树给出生成过程

解：Floyd算法的Matlab程序如下：

clear;clc;

n=5; a=zeros(n);

a(1,2)=1;a(1,3)=12;a(1,4)=6;a(1,5)=10;

a(2,3)=8;a(2,4)=9;

a(3,5)=2;

a(4,5)=4;

a=a+a';M=max(max(a))*n^2; %M为充分大的正实数

a=a+((a==0)-eye(n))*M;

path=zeros(n);

for k=1:n

for i=1:n

for j=1:n

ifa(i,j)>a(i,k)+a(k,j)

a(i,j)=a(i,k)+a(k,j);

path(i,j)=k;

end

a, path

Matlab输出结果：

a =

0 1 9 6 10

1 0 8 7 10

9 8 0 6 2

6 7 6 0 4

10 10 2 4 0

path =

0 0 2 0 0

0 0 0 1 3

2 0 0 5 0

0 1 5 0 0

0 3 0 0 0

根据Prim算法求图示的最小代价生成树

#include using namespace std; #define MAX_VERTEX_NUM 10 //最大顶点个数 #define INFINITY 1000 //定义最大值为1000 typedef char VerType；//定点向量 typedef int VRType；//定点之间的关系（即权值） typedef struct { VerType vexs[MAX_VERTEX_NUM]； //顶点向量 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]； //邻接矩阵 int vexnum,arcnum； //图的当前顶点数和弧数 }mgraph, * MGraph; typedef struct { VerType adjvex; VRType lowcost; }closedge[MAX_VERTEX_NUM]；//记录从顶点集U到V-U的代价最小的边的辅助数组定义 //初始化图 void init_mgraph(MGraph &g) { g=(MGraph)malloc(sizeof(mgraph)); g->vexnum=0; g->arcnum=0; for(int i=0;i g->vexs[i]=0; for(i=0;i for(int j=0;j g->arcs[i][j]=INFINITY; } void add_vexs(MGraph &g) //增加顶点 { cout cin>>g->vexnum; cout for(int i=0;ivexnum;i++) { cin>>g->vexs[i]; } } void add_arcs(MGraph &g) //增加边 { cout cin>>g->arcnum; VerType ch1,ch2; int weight; int row,col; for(int i=0;iarcnum;i++) { cin>>ch1>>ch2>>weight; for(int j=0;jvexnum;j++) { if(g->vexs[j]==ch1) { row=j; } if(g->vexs[j]==ch2) { col=j; } } g->arcs[row][col]=weight； //有向带权图只需把1改为weight g->arcs[col][row]=weight; } } void creat_mgraph(MGraph &g) //创建图 { add_vexs(g)； //增加顶点 add_arcs(g)； //增加边 } void print_mgraph(MGraph &g) //打印图 { for(int i=0;ivexnum;i++) coutvexs[i] cout for(i=0;ivexnum;i++) { coutvexs[i]; for(int j=0;jvexnum;j++) { coutarcs[i][j] } cout } } //返回顶点v在顶点向量中的位置 int LocateVex(MGraph &g, VerType v) { int i; for(i = 0; v != g->vexs[i] & i vexnum; i++) ; if(i >= g->vexnum) return -1; return i； } //求出T的下一个节点，第k节点 int minimun(MGraph &g, closedge closedge) { int min=INFINITY,k=0,i; for(i=0;ivexnum;i++) { if(closedge[i].lowcost != 0 & closedge[i].lowcost { min = closedge[i].lowcost; k = i; } } return k； } //普里姆算法 void MiniSpanTree_Prim(MGraph &g, VerType u) //普里姆算法从顶点u出发构造G的最小生成树T，输出T的各条边。

{ closedge closedge; int i,j; int k=LocateVex(g,u); for(j=0;jvexnum;j++) //辅助数组初始化 { if(j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=g->arcs[k][j]; } } closedge[k].lowcost = 0； //初始，U={u} for(i=1;ivexnum;i++) //选择其余g.vexnum-1个顶点 { k=minimun(g,closedge)； //求出T的下一个节点，第k节点 coutvexs[k] closedge[k].lowcost=0； //第k顶点并入U集 for(j=0;jvexnum;j++) { if(g->arcs[k][j] { closedge[j].adjvex = g->vexs[k]; closedge[j].lowcost = g->arcs[k][j]; } } } }//MiniSpanTree_Prim int main() { MGraph G; init_mgraph(G)； //初始化图 creat_mgraph(G)； //创建图 print_mgraph(G)； //打印图 MiniSpanTree_Prim(G,G->vexs[0])； //最小生成树 return 0; }

无权无向图只给出节点个数怎么用Prim算法求最小生成树

Prim算法的主要运行时间花在过程②的选边中。看起来复杂度是O(VE)=O(V^3)不是么，效率也太低了吧……

为了比较快速地选边，我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离。在某一状态下，lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值，closest[i]表示在S中且与i相连的点中与i之间距离最小的点。显然，lowcost[i]=w(i,closest[i])。需要注意的是两个数组记录的都是边而不是路径。若i没有边直接连向S，则lowcost[i]=∞。另外，若i已在S中，则lowcost[i]=0。

设出发点为x。初始时对于任意k∈V,closest[k]=x,lowcost[k]=w(k,x)【w(i,j)表示i、j间的距离。初始化时，若两点间没有边则w(i,j)赋为一个足够大的整数（如maxint），并且所有点到自身的距离赋为0，即w(i,i)=0】

每一次找出lowcost中不为0的最小值lowcost[i]，然后把i加入S（即lowcost[i]:=0），然后对于图中所有点k，若w(k,i)以上操作重复|V|-1次结束。由于每次加入S的点i都在当时取到了符合流程②的边min{lowcost}，而lowcost[i]=w(i,closest[i])，所以此时的最小生成树的各边就是（i,closest[i]）,i∈V且not (i=x)【需要注意的是出发点x的closest[x]还是x，所以应忽略，实际取到x-1条边】。把i从1取到|V|，便得到最小生成树T的每条边。程序： for(k= 1;k <= n; k++){ //x为S中的第一个点，x任选一个都可 lowcost[k] = w[x][k]; //lowcost表示k点到前集合的最小值，是k与前集合中的closet[k]间的距离 closest[k] = x； } //初始化 for(i = 2; i <= n; i++){ //除去x，还要加入n – 1个点 temp = maxint; for(j = 1; j <= n; j++) if(lowcost[j] < temp & lowcost[j] != 0) { temp = lowcost[j]; k = j； } //找出S外距S最近的点k lowcost[k] = 0； //将k加入生成树 for(j = 1; j <= n; j++) if(w[k][j] < lowcost[j]){ lowcost[j] = w[k][j]; closest[j] = k； } //由新加入S中的k点使某些点到S的距离缩短，所以更新各点的lowcost和closest，即再次初始化 } for(i = 1; i <= n; i++) if(i != closest[i]){ printf(“%d %d”, i, closest[i])； } //输出最小生成树的各边不难看出，以上算法包含一个二重循环，算法复杂度为O(V^2)，与图的稠密度无关

以下为关联文档：

C语言随机数序列编程：用C语言程序编写。生成随机数序列//希望您你有帮助！ #include <stdio.h> #include <time.h> int main() { int a[15] = {0}; int count = 0; srand(time(NULL)); while ( 1 ) { int r = rand()%15 + 1; if (+...

C随机序列生成问题#define _max 50 #define _size 50 bool cs_empty(std::map<int,int>& r){ for(int i=0;i<_size;i++)if(r[i]!=0)return false; return true; } void fun(){ std::map<int,i...

Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程Prim算法复杂度：O(n2)，与边无关，适合求边稠密的网的最小生成树。算法思想：假设N={V,{E}}是连通网，TE是N上最小生成树中边的集合。算法从U={u0},TE ={}开始，重复执行下述操作：在所...

利用Prim普里姆算法构造最小生成树程序算法同样是解决最小生成树的问题。其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个...

无权无向图只给出节点个数怎么用Prim算法求最小生成树Prim算法的主要运行时间花在过程②的选边中。看起来复杂度是O(VE)=O(V^3)不是么，效率也太低了吧…… 为了比较快速地选边，我们用两个数组lowcost、closest动态地维护每一个点...

利用kruska prim算法求解图的最小生成树并比较算法的效率adjmatrix GA 邻接矩阵GA struct edgeset { int fromvex；起始点 int endvex；终点 int weight；权值 } void prim(adjmatrix GA,edgeset CT,int n) { int i,j,k,min,t,m,w; fo...

求教由二叉树的前序遍历序列建立二叉树的非递归算法#include /*如发现bug请给我留言*/ #include #include #define LEN sizeof(struct node) struct node { char data; struct node *lchild,*rchild; }; struct node *build()...

请教高手C数据结构回溯算法解迷宫问题//迷宫用栈做的 #include ＂stdio.h＂ #include ＂stdlib.h＂ #define INITSIZE 100 #define STACKINCRESMENT 10 #define WALL 9999 struct stack { int *base; int *top; int size...

求一自动生成二维数组的算法 c编写这个我可以帮你做，也用不了多长时间，能不能加qq:865218315，还有些细节问题想弄好了： #include <stdio.h> #include <stdlib.h> #include <time.h> void Labyrinth(int step[][2...