/****************************** 结构体部分 ****************************/
typedef struct ArcNode
{
int adjvex;//该弧指向的顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
InfoType *info;//该弧相关信息指针
}ArcNode;
typedef struct VNode
{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一条依附于该顶点的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;//弧的顶点数和弧数
int kind;//弧的类型
}ALGraph;
typedef int VRType;
typedef struct
{
int begin,end;
VRType cost;
}EDGE;
/****************************** 函数操作部分 ****************************/
void Swapn(EDGE *edges,int i,int j) //交换
{
int temp;
temp=edges.begin;
edges.begin=edges[j].begin;
edges[j].begin=temp;
temp=edges.end;
edges.end=edges[j].end;
edges[j].end=temp;
temp=edges.cost;
edges.cost=edges[ j].cost;
edges[j].cost=temp;
}
void Sort(EDGE *edges,ALGraph G)
{
int i,j;
for(i=1;i=G.vexnum;i)
for(j=i;j=G.vexnum;j)
if(edges.costedges[j].cost)
Swapn(edges,i,j);
}
int Find(int *parents,int f)
{
if(parents[f]0)
f=parents[f];
return (f);
}
void MiniSpanTree_Kruskal(ALGraph G)
{
int i,v1,v2,value,bnf,edf;
int parents[MAX_VERTEX_NUM];
EDGE edges[MAX_VERTEX_NUM];
printf(\"请输入顶点和边的数量：\\n\");
scanf(\"%d%d\",
for(i=1;i=G.arcnum;i)
{
printf(\"请输入第%d条边的两个顶点和权值：\\n\",i);
scanf(\"%d%d%d\",
edges.begin=v1;
edges.end=v2;
edges.cost=value;
}
Sort(edges,G);
for(i=1;i=G.vexnum;i)
parents=0;
printf(\"\\n结果是：\\n\");
for(i=1;i=G.vexnum;i)
{
bnf=Find(parents,edges.begin);
edf=Find(parents,edges.end);
if(bnf!=edf)
{
parents[bnf]=edf;
printf(\"Arc(%d,%d):%d\\n\",edges.begin,edges.end,edges.cost);
}
}
}
/****************************** 主函数部分 ****************************/
void main()
{
ALGraph G;
MiniSpanTree_Kruskal(G);
|
