//無(wú)向圖
//默認(rèn)從V0開始
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
const int INF=999;//最大值怎么取啊反砌？
//這里是這個(gè)代碼里面設(shè)置的無(wú)窮大
const int Maxsize=10;
int visited[Maxsize];
struct Edge//這個(gè)結(jié)構(gòu)體用于記錄最短邊的相關(guān)信息
{
? ? int adjvex;//候選最短邊的鄰接點(diǎn)
? ? int lowcost;//候選最短邊的權(quán)值
}shortEdge[Maxsize];//記錄最短邊的數(shù)組
class MGraph
{
? ? public:
? ? MGraph(int a[],int n,int e);//n個(gè)頂點(diǎn)赢织，e條邊
? ? ~MGraph() {}
? ? int Prim(MGraph G);//普利姆算法
? ? private:
? ? int vertex[Maxsize];//存放圖中頂點(diǎn)的數(shù)組
? ? int arc[Maxsize][Maxsize];//存放圖中邊的數(shù)組
? ? int vertexNum,arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù)
};
MGraph::MGraph(int a[],int n,int e)//構(gòu)造函數(shù)
{
? ? vertexNum=n;
? ? arcNum=e;
? ? int weight;
? ? for(int i=0;i<vertexNum;i++)
? ? {
? ? ? ? ? vertex[i]=a[i];//頂點(diǎn)信息錄入
? ? }
? ? for(int i=0;i<vertexNum;i++)
? ? {
? ? ? ? ? for(int j=0;j<vertexNum;j++)//將各條邊進(jìn)行初始化
? ? ? ? ? {
? ? ? ? ? ? ? if(i==j)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? arc[i][j]=0;//一個(gè)點(diǎn)
? ? ? ? ? ? ? }
? ? ? ? ? ? ? else arc[i][j]=INF;//不相鄰設(shè)置為無(wú)窮大
? ? ? ? ? }
? ? }
? ? cout<<"請(qǐng)分別輸入無(wú)向圖的邊對(duì)應(yīng)的點(diǎn)及其權(quán)值"<<endl;
? ? for(int k=0;k<arcNum;k++)
? ? {//依據(jù)設(shè)置的邊數(shù)，將其頂點(diǎn)錄入缀磕，在這里設(shè)置為無(wú)向圖
? ? ? ? ? int i,j;
? ? ? ? ? cin>>i>>j; //輸入該邊依附的兩個(gè)頂點(diǎn)的編號(hào)
? ? ? ? ? cin>>weight;//錄入權(quán)值
? ? ? ? ? arc[i][j]=weight;
? ? ? ? ? arc[j][i]=weight;
? ? }
? ? cout<<"以下輸出鄰接矩陣:"<<endl;
? ? for(int i=0;i<vertexNum;i++)//輸出鄰接矩陣啊
? ? {
? ? ? ? ? for(int j=0;j<vertexNum;j++)
? ? ? ? ? {
? ? ? ? ? ? ? if(arc[i][j]==INF)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cout<<"∞\t";
? ? ? ? ? ? ? }
? ? ? ? ? ? ? else
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? cout<<arc[i][j]<<'\t';
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? cout<<endl;
? ? }
}
//k=MinEdk=MinEdge(shortEdge,G.vertexNum);//調(diào)用函數(shù)找最短邊的鄰接點(diǎn)編號(hào)
int MinEdge(struct Edge shortEdge[],int n)//記錄最短邊的數(shù)組,圖的頂點(diǎn)數(shù)
{
? ? //int min=INF,minbd=0;
? ? int minarcver=0;
? ? int min=INF;
? ? for(int i=0;i<n;i++)
? ? {
? ? ? ? ? //if((shortEdge[i].lowcost<min)&&(shortEdge[i].lowcost!=0))
? ? ? ? ? if((shortEdge[i].lowcost<min)&&(shortEdge[i].lowcost!=0))//有邊且。劣光。袜蚕。
? ? ? ? ? {
? ? ? ? ? ? ? minarcver=i;//記錄候選最短邊的頂點(diǎn)編號(hào)
? ? ? ? ? ? ? min=shortEdge[i].lowcost;//記錄這一輪的最短邊
? ? ? ? ? }
? ? }
? ? return minarcver;//返回該頂點(diǎn)編號(hào)
}
int MGraph::Prim(MGraph G)//默認(rèn)從v0開始
{
? ? int k=0,j=0;
? ? int sum=0;
? ? //原來(lái)是默認(rèn)這個(gè)最小生成樹的其實(shí)點(diǎn)從第一個(gè)頂點(diǎn)開始
? ? //以下初始化輔助數(shù)組shortEdge
? ? for(int i=1;i<G.vertexNum;i++)
? ? {
? ? ? ? ? shortEdge[i].lowcost=G.arc[0][i];
? ? ? ? ? shortEdge[i].adjvex=0;//此時(shí)的鄰接點(diǎn)是v0
? ? }
? ? shortEdge[0].lowcost=0;//將頂點(diǎn)0加入集合U
? ? for(int i=1;i<G.vertexNum;i++)//遍歷v0之外的所有頂點(diǎn)
? ? {
? ? ? ? ? k=MinEdge(shortEdge,G.vertexNum);//調(diào)用函數(shù)找最短邊的鄰接點(diǎn)編號(hào)
? ? ? ? ? cout<<"找到的權(quán)值小的邊及其所對(duì)應(yīng)的權(quán)值:";
? ? ? ? ? cout<<"V"<<shortEdge[k].adjvex<<"->V"<<k<<"="<<shortEdge[k].lowcost<<endl;
? ? ? ? ? sum+=shortEdge[k].lowcost;//累積最小權(quán)值
? ? ? ? ? shortEdge[k].lowcost=0;//將頂點(diǎn)k加入集合U中
? ? ? ? ? for(j=1;j<G.vertexNum;j++)//調(diào)整數(shù)組shortEdge[n]
? ? ? ? ? {
? ? ? ? ? ? ? if(G.arc[k][j]<shortEdge[j].lowcost)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? shortEdge[j].lowcost=G.arc[k][j];
? ? ? ? ? ? ? ? ? ? shortEdge[j].adjvex=k;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? }
? ? return sum;
}
int main()
{
? ? int n,e;
? ? int a[Maxsize];
? ? cout<<"請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):"<<endl;
? ? cin>>n>>e;//n個(gè)頂點(diǎn)，e條邊
? ? cout<<"請(qǐng)依次輸入各個(gè)頂點(diǎn)信息:"<<endl;
? ? for(int i=0;i<n;i++)
? ? {
? ? ? ? ? cin>>a[i];
? ? ? ? ? //visited[i]=0;//
? ? }
? ? MGraph MG(a,n,e);//構(gòu)造函數(shù)
? ? cout<<"最小生成樹權(quán)值總和為："<<MG.Prim(MG)<<endl;
? ? return 0;
}
//測(cè)試樣例
//6 9
//0 1 34
//0 2 46
//0 5 19
//1 4 12
//4 5 26
//2 5 25
//2 3 17
//3 5 25
//3 4 38
//
//結(jié)果99
