Question

求编程高手指教！一道有关数据结构的编程题，最好用c语言编。

图G有30个顶点，为v[1] … v[99]，其中边i→j的权值用随机整数产生，随机数分布区间为[1,100]，请利用Kruscal算法产生最小生成树G1,在屏幕上输出： （1）各条边的权值w[i][j] （2）G1中所有的边u[a][b]及总权重屏幕上输出可以用截图来表示。

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
#define MAXNUM_VERTEX 30 //最多有 30个顶点
#define MAXNUM_EDGE 31
typedef struct
{
int v,w;
int weight;
}Edge;
typedef struct
{
int vertex[MAXNUM_VERTEX];
Edge edge[MAXNUM_EDGE];
int num_vertex,num_edge;
}Graph;
Graph graph; //声明为全局变量
bool search_vertex(int ver)
{
for(int i=0; i<graph.num_vertex; i++)
if( ver == graph.vertex[i] )
return 1;
printf("the vertex %d you input is not existed! \n",ver);
return 0;
}
void create_graph()
{
//输入顶点信息
printf("input the number of vertex in the graph\n");
scanf(" %d",&graph.num_vertex);
printf("input the vertex of graph,like 1,2\n");
for(int i=0; i<graph.num_vertex; i++)
scanf(" %d",&graph.vertex[i]);
//输入边信息
printf("input the number of edge in the graph\n");
scanf(" %d",&graph.num_edge);
printf("intput the edge of graph and the weight of line,like 1-2 5\n");
for(int j=0; j<graph.num_edge; j++)
{
p1:int a,c,d;
char b;
scanf(" %d %c %d %d",&a,&b,&c,&d);
if( search_vertex(a) && search_vertex(c) )
{
graph.edge[j].v=a;
graph.edge[j].w=c;
graph.edge[j].weight=d;
}
else
goto p1;
}
}
void sort_by_weight()
{
for(int i=1; i<graph.num_edge; i++)
{
Edge temp=graph.edge[i];
for(int j=i-1; j>=0 && graph.edge[j].weight>temp.weight; j--)
graph.edge[j+1]=graph.edge[j];
graph.edge[j+1]=temp;
}
}
/*不相交集处理函数*/
inline void makeset(vector<int> & array)
{
for(int i=0; i<array.size(); i++)
array[i]=i;
}
int findset(vector<int> & parent,int i)
{
if(i != parent[i])
i=parent[i];
return i;
}
inline void merge(vector<int> & parent,int i,int j)
{
parent[i]=j;
}
/*不相交集处理函数*/
void kruskal()
{
int num_ver=graph.num_vertex;
int count=0;
vector<int> parent_ver;
parent_ver.resize(num_ver);
/*核心部分是用不相交集合成树*/
makeset(parent_ver);
printf("the edge of min tree as follow: \n");
for( int i=0; i<num_ver && count<num_ver-1; i++ ) //count表示合并（merge）的次数num_ver-1次
{
int m=graph.edge[i].v;
int n=graph.edge[i].w;
int w=graph.edge[i].weight;
if( findset(parent_ver,m) != findset(parent_ver,n)) //当属于不同的集合时，则将该边添加进树中
{
printf("(%d %d) %d\n",m,n,w);
merge(parent_ver,m,n);
count++;
}
}
}
void print_edge()
{
printf("the graph you input as follow: \n");
for(int i=0; i<graph.num_edge; i++)
printf("%d-%d the weight is: %d\n",graph.edge[i].v,graph.edge[i].w,graph.edge[i].weight);
}
void main()
{
create_graph();
sort_by_weight();
print_edge();
kruskal();
}

追问

这里面有第二问么？
可不可以有其他的方法~~~
满意的追加~~财富不是事~

Answer 2

v[1] … v[99]只有30个顶点。。。。。