Ⅰ 急！數據結構最小生成樹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（普里姆）演算法 構造最小生成樹 程序
演算法同樣是解決最小生成樹的問題。
其演算法為：在這n個點中的相通的邊進行排序，然後不斷地將邊添加到集合中（體現了貪心的演算法特點），在並入集合之前，必須檢查一下這兩點是不是在一個集合當中，這就用到了並查集的知識。直到邊的集合達到了n-1個。
與prim演算法的不同：prim演算法為單源不斷尋找連接的最短邊，向外擴展，即單樹形成森林。而Kruskal演算法則是不斷尋找最短邊然後不斷將集合合並，即多樹形成森林。
復雜度的不同：prim演算法的復雜度是O(n^2),其中n為點的個數。Kruskal演算法的復雜度是O(e*loge)，其中e為邊的個數。兩者各有優劣，在不同的情況下選擇不同的演算法。
Prim演算法用於求無向圖的最小生成樹
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
Prim演算法實現：
（1）集合：設置一個數組set(i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}
Ⅲ 用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調整候選輕邊集
}
}
Ⅳ c++求最小生成樹prim演算法,我搗鼓2天了,真心不會改了,求指導感激不盡啊
你的代碼太亂，給你這個，添加了注釋，容易看懂：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
usingnamespacestd;
#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];//節點數組
AdjMatrixarcs;//鄰接矩陣
intvexnum,arcnum;//圖的當前節點數和弧數
}MGraph;
typedefstructPnode//用於普利姆演算法
{
charadjvex;//節點
doublelowcost;//權值
}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點集U到V-U的代價最小的邊的輔助數組定義
typedefstructKnode//用於克魯斯卡爾演算法中存儲一條邊及其對應的2個節點
{
charch1;//節點1
charch2;//節點2
doublevalue;//權值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevalue&dgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構造無向加權圖的鄰接矩陣
{
inti,j,k;
cout<<"請輸入圖中節點個數和邊/弧的條數：";
cin>>G.vexnum>>G.arcnum;
cout<<"請輸入節點：";
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)//初始化數組
{
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
}
cout<<"請輸入一條邊依附的定點及邊的權值："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1);
j=LocateVex(G,dgevalue[k].ch2);
G.arcs[i][j].adj=dgevalue[k].value;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)//確定節點ch在圖G.vexs中的位置
{
inta;
for(inti=0;i<G.vexnum;i++)
{
if(G.vexs[i]==ch)
a=i;
}
returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆演算法求最小生成樹
{
inti,j,k;
Closedgeclosedge;
k=LocateVex(G,u);
//將該頂點到其他所有的頂點權值賦值給closedge
for(j=0;j<G.vexnum;j++)
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
//找到權值最小的頂點，記錄到k
k=Minimum(G,closedge);
cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
//清零，方便尋找下一個頂點
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
{
//依次比較上個頂點和當前頂點與剩餘頂點的權值，將小的賦值給closedge
if(G.arcs[k][j].adj<closedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中權值最小的邊，並返回其頂點在vexs中的位置
{
inti,j;
doublek=1000;
for(i=0;i<G.vexnum;i++)
{
if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidmain()
{
inti,j;
MGraphG;
charu;
Dgevaluedgevalue;
CreateUDG(G,dgevalue);
cout<<"圖的鄰接矩陣為："<<endl;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
cout<<G.arcs[i][j].adj<<"";
cout<<endl;
}
cout<<"=============普利姆演算法=============== ";
cout<<"請輸入起始點：";
cin>>u;
cout<<"構成最小代價生成樹的邊集為： ";
MiniSpanTree_PRIM(G,u);
}
Ⅳ 用prim演算法求最小生成樹: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'留地方。
Ⅵ 求數據結構(C語言)prim演算法求最小生成樹
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調整候選輕邊集
}
}
Ⅶ 對任意的網和起點,用PRIM演算法的基本思想求解出所有的最小生成樹(C語言編寫)
prim基本思想就是貪心，每次加最短的邊
既然要求所有的
那就判斷如果有兩條或更多條都是最小，那就分支出多種情況。
Ⅷ 關於Prim演算法求最小生成樹的問題
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調整候選輕邊集 } }
Ⅸ 怎樣用prim演算法求全部最小生成樹
//prim演算法
#include<iostream>
using namespace std;
#define MAXVEX 10
#define MAX 65000
typedef char VexType;
typedef float AdjType;
struct GraphMatrix
{
VexType vexs[MAXVEX]; //頂點信息
AdjType arcs[MAXVEX][MAXVEX]; //邊信息
int n; //圖的頂點個數
};
struct Edge
{
int start_vex; //邊的起點
int stop_vex; //邊的終點
AdjType weight; //邊的權
};
void edgeCopy(Edge *to,Edge *from)
{
to->start_vex=from->start_vex;
to->stop_vex=from->stop_vex;
to->weight=from->weight;
}
void prim(GraphMatrix *pgraph,Edge *mst)
{
int i,j;
int vx,vy;
int min;
AdjType weight,minweight;
Edge edge;
for(i=0;i<pgraph->n-1;++i)
{
mst[i].start_vex=0;
mst[i].stop_vex=i+1;
mst[i].weight=pgraph->arcs[0][i+1];
}
for(i=0;i<pgraph->n-1;++i)
{
minweight=MAX;
min=i;
for(j=i;j<pgraph->n-1;++j)
if(mst[j].weight<minweight)
{
minweight=mst[j].weight;
min=j;
}
edgeCopy(&edge,&mst[min]);
edgeCopy(&mst[min],&mst[i]);
edgeCopy(&mst[i],&edge);
vx=mst[i].stop_vex;
for(j=i+1;j<pgraph->n-1;++j)
{
vy=mst[j].stop_vex;
weight=pgraph->arcs[vx][vy];
if(weight<mst[j].weight)
{
mst[j].weight=weight;
mst[j].start_vex=vx;
}
}
}
}