prim演算法代碼
❶ prim演算法matlab
%Prims Algorithm
%coded by Vikramaditya V. Kunr
clc
fid = fopen('testfile1.txt', 'r'); % Input file
%Input file should be in the form of a text file.
%5 %order of matrix
%0 2 3 4 0
%2 0 1 2 5
%3 1 0 1 2
%4 2 1 0 2
%0 5 2 2 0
l = fscanf(fid, '%g %g', [1 1]) % Input matrix size from line 1
h = fscanf(fid, '%g %g', [l l]) % Input the matrix
a=h'
fclose(fid);
fid = fopen('Result.txt','wt'); % Output file
fprintf(fid,'Original matrix\n\n'); % Printing the original matrix in the output file
for i=1:l
for k=1:l
fprintf(fid,'%6d',a(i,k));
end
fprintf(fid,' \n');
end
for i=1:l
for j=1:l
if a(i,j)==0
a(i,j)=inf;
end
end
end
k=1:l
listV(k)=0;
listV(1)=1;
e=1;
while (e<l)
min=inf;
for i=1:l
if listV(i)==1
for j=1:l
if listV(j)==0
if min>a(i,j)
min=a(i,j);
b=a(i,j);
s=i;
d=j;
end
end
end
end
end
listV(d)=1;
distance(e)=b;
source(e)=s;
destination(e)=d;
e=e+1;
end
fprintf(fid,'\n\nDistance modified matrix\n\n');
for i=1:l
for k=1:l
if i==k
fprintf(fid,'%6d',0);
else
fprintf(fid,'%6d',a(i,k));
end
end
fprintf(fid,' \n');
end
fprintf(fid,'\n The nodes and shortest distances are \n');
fprintf(fid,'\nFORMAT: Distance(Source, destination) \n');
for g=1:e-1
fprintf(fid,'%d(%d,%d)\n',distance(g),source(g),destination(g));
end
status = fclose(fid);
clear
❷ Prim演算法c語言表示，求源程序。。。。。。。。。
我原來自己寫的模板
//樸素prim演算法
//復雜度 O(n^2)
//flag[SIZE] 頂點標記
//mindis[SIZE] 當前最短距離
//dis[SIZE][SIZE] 任意兩點間距離 鄰接矩陣表示
int prim()
{
memset(flag,false,sizeof(bool)*(n+1));
flag[0] = true;
for(int i=1;i<n;i++)
mindis[i] = dis[0][i];
int ans = 0;
for(int i=1;i<n;i++)
{
int min = 10000;
int pos;
for(int j=1;j<n;j++)
{
if(!flag[j] && min > mindis[j])
{
min = mindis[j];
pos = j;
}
}
ans+=min;
flag[pos] = true;
for(int j=1;j<n;j++)
{
if(!flag[j] && mindis[j] > dis[pos][j])
mindis[j] = dis[pos][j];
}
}
return ans;
}
❸ prime演算法建立最小生成樹的代碼
這個我也不會,
❹ Prim演算法的實現過程
貪心過程.
首先,把圖中的點分成兩種,已連通和未連通的,我把它們分別稱為"黑"和"白"點.
一開始時,圖中全是白點,沒有黑點.演算法的第一步,隨機選出一個白點,染成黑色.
然後開始一個重復的過程:
從當前圖的邊中尋找這樣的一些邊:它的其中一個端點是黑點,而另一個端點是一個白點. 我們可以把這類邊稱為"可擴展邊". 然後演算法需要從所有的可擴展邊之中選出權值最小的一條.把這條可擴展邊加入生成樹之中,且把這條邊的白色端點染成黑色.
重復這個過程,直到全部的節點都為黑色.
演算法可以優化的地方是,在選擇權值最小的可行邊時可以使用堆.
❺ Python中prim演算法或kruscal演算法的實現
kruskal:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXE 100 //MAXE為最大的邊數
struct edges
{
int bv,tv,w; //邊集類型,存儲一條邊的起始頂點bv、終止頂點tv和權w
}edges;
typedef struct edges edgeset[MAXE];
//尋找v所在的連通集
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0)
i=set[i];
return i;
}
void kruskal(edgeset ge,int n,int e)
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0;
i=1; //i表示待獲取的生成樹中的邊數,初值為1
j=1; //j表示ge中的下標,初值為1
while(j<n&&i<=e)//按邊權遞增順序,逐邊檢查該邊是否應加入到生成樹中
{
v1=seeks(set,ge[i].bv); //確定頂點v所在的連通集
v2=seeks(set,ge[i].tv);
cout<<ge[i].bv<<":"<<v1<<", "<<ge[i].tv<<":"<<v2<<endl;
if(v1!=v2) //當v1,v2不在同一頂點集合,確定該邊應當選入生成樹
{
cout<<"("<<ge[i].bv<<", "<<ge[i].tv<<") "<<ge[i].w<<endl;
set[v1]=v2;
j++;
}
i++;
}
}
int main()
{
edgeset ee;
int n,e; //n是圖的結點數,e是圖的邊數
n=6;
e=3;
for(int i=1;i<=e;i++)
{
scanf_s("%d",&ee[i].bv);
scanf_s("%d",&ee[i].tv);
scanf_s("%d",&ee[i].w);
}
//ee表示的邊集圖是按權值從小到大排列的
printf("最小生成樹邊集及它的權值: \n");
kruskal(ee,n,e);
system("pause");
return 0;
}
prim:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define N 3
void prim(int c[N][N])
{
//lowcost 為頂點間的最小距離，closest為最小距離上的鄰接頂點
//lowcost[i]:與頂點i連通的最小邊的權值
//closest[i]:與頂點i連通的鄰接頂點
int lowcost[N],closest[N];
int i,j,k,min;
//lowcost,closest初始化
for(i=0;i<N;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
closest[0]=-1;
//尋找U 和 V 之間連接的最短距離的鄰接點
for(i=0;i<N;i++)
{
min=32767;
k=0;
//尋找U 和 V 之間連接的最短距離的鄰接點
for(j=0;j<N;j++)
{
if((lowcost[j]<min)&&(closest[j]!=-1))
{
min=lowcost[j];
k=j;
}
}
//輸出新的鄰接頂點，並修改lowcost值
if(k)
{
cout<<"("<<closest[k]<<", "<<k<<") "<<lowcost[k]<<endl;
closest[k]=-1;
for(j=1;j<N;j++)
{
if(closest[j]!=-1)// huo if(!(closest[j]==-1))
{
//修改lowcost值
lowcost[j]=c[k][j];
//修改鄰接頂點
closest[j]=k;
}
}
}
}
}
int main()
{
int i,j,a[3][3];
cout<<"請輸入二維數組："<<endl;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
cin>>a[i][j];
cout<<"最小樹的結構為："<<endl;
prim(a);
int q;
cin>>q;
return 0;
}
❻ 急！數據結構最小生成樹prim演算法C語言實現
Kruskal演算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化輔助數組
k=1; //k表示當前構造最小生成樹的第幾條邊,初值為1
j=0; //E中邊的下標,初值為0
while (k<n) //生成的邊數小於n時循環
{
m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點
sn1=vset[m1];sn2=vset[m2]; //分別得到兩個頂點所屬的集合編號
if (sn1!=sn2) //兩頂點屬於不同的集合,該邊是最小生成樹的一條邊
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成邊數增1
for (i=0;i<n;i++) //兩個集合統一編號
if (vset[i]==sn2) //集合編號為sn2的改為sn1
vset[i]=sn1;
}
j++; //掃描下一條邊
}
}
Prim演算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //給lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1個頂點
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 邊(%d,%d)權為:%d/n",closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<n;j++) //修改數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
❼ 數據結構（prim演算法）
開始時將v1加入U後，更新ee中的值應該是0 6 1 2 無窮 無窮；
將v3加入U後，更新ee中的值應該是0 5 0 2 6 4；
怎麼會出現你說的0 6 0 5 無窮無窮的情況呢？
for(j = 0;j < G.vexnum;j++)中不是有條件判斷么，要在k到j的距離小於ee[j]的value值時才會更新ee[j]啊。
❽ 請問誰有Prim演算法代碼 ,Kruskal演算法代碼 ,Dijkstra演算法代碼
我不是計算機系的
但是剛才幫你在CSDN上搜索了下,看到一個BLOG點擊很高,內容很全
給你貼上,祝你成功:
用Prim演算法求無向圖的最小生成樹
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445156.aspx
Kruskal演算法代碼分析
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445147.aspx
Dijkstra演算法代碼分析
http://blog.csdn.net/ctu_85/archive/2006/11/17/1393130.aspx
銀行家演算法代碼分析
http://blog.csdn.net/ctu_85/archive/2006/09/09/1198551.aspx
❾ 求dijkstra、prim演算法的C語言可執行代碼！
http://ke..com/view/7839.html?fromTaglist
❿ 用prim演算法的思想，用C語言編寫出最小生成樹的方法的代碼
PrimMST(G，T，r){
//求圖G的以r為根的MST，結果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：設置初始的輕邊候選集，並置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1條樹邊
(u，v)=SelectLiShtEdge(…)；//選取輕邊(u，v)；
T←T∪{(u，v)}；//擴充T，即(u，v)塗紅加入TE，藍點v並人紅點集U
ModifyCandidateSet(…)；
//根據新紅點v調整候選輕邊集
}
}