首页 > Sentiment > 实验八  图的最小生成树

实验八  图的最小生成树

2008年11月14日 发表评论 阅读评论 548 views

Graph1.h

void InitMatrix(adjmatrix G)
{
int i,j;
for(i=0;i for(j=0;j if(i==j)
G[i][j]=0;
else
G[i][j]=MaxValue;
}

void CreateMatrix(adjmatrix G,int n)
{
char *s=new char[100];
cerr<<"please input the matrix: ";
cin>>s;
istrstream sin(s);
char c1,c2,c3;
int i,j;
WeightType w;
sin>>c1;
do{
sin>>c1>>i>>c2>>j>>c3>>w;
if(i*j<0||i>n-1||j>n-1)
exit(1);
G[i][j]=G[j][i]=w;
sin>>c1;
if(c1=='}')
break;
}while(1);
}

void PrintMatrix(adjmatrix G,int n)
{
int i,j;
cout<<"V={";
for(i=0;i cout< cout< cout<<"E={";
for(i=0;i for(j=0;j if(G[i][j]!=0&&G[i][j]!=MaxValue)
if(i cout<<'('< cout<<'}'<}

void InitArray(edgeset GE)
{
for(int i=0;i GE[i].fromvex=GE[i].endvex=-1;
GE[i].weight=MaxValue;
}
}


Test8.cpp

#include
#include
#include
typedef int VertexType;
typedef int WeightType;
const int MaxVertexNum=20;
const int MaxEdgeNum=20;
typedef int WeightType;
const WeightType MaxValue=9999;
typedef VertexType vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];

struct edge{
int fromvex;
int endvex;
WeightType weight;
};
typedef edge edgeset[MaxEdgeNum];

#include”Graph1.h”

void Prim(adjmatrix G, edgeset CT, int n)
{
int i,j,k,min,t,m,w;
for(i=0;i CT[i].fromvex=0;
CT[i].endvex=i+1;
CT[i].weight=G[0][i+1];
}
for(k=1;k {
min=MaxValue;
m=k-1;
for(j=k-1;j if(CT[j].weight min=CT[j].weight;
m=j;
}
edge temp=CT[k-1];
CT[k-1]=CT[m];
CT[m]=temp;
j=CT[k-1].endvex;
for(i=k;i t=CT[i].endvex;
w=G[j][t];
if(w CT[i].weight=w;
CT[i].fromvex=j;
}
}
}
}
void PrintEdge(edgeset CT, int n)
{
int i;
cout<<"V={";
for(i=0;i cout< cout< cout<<"E={";
i=-1;
while(CT[++i].fromvex!=-1){
cout<<'('< cout<<')'< }
cout<<'}'<}

void main()
{
int i,n;
cout<<"input the points of the graph: ";
cin>>n;
adjmatrix G;
InitMatrix(G);
CreateMatrix(G,n);
PrintMatrix(G,n);
edgeset CT;
InitArray(CT);
Prim(G,CT,n);
cout<<"now printing the minimun spanning tree: "< PrintEdge(CT,n);
}

分类: Sentiment 标签: ,
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :cool: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O