最小生成树课程设计结论

① 最小生成树——最优通信网 课程设计

你这个开发语言是什么
平台
或数据库都怎样
谈
我这样才好帮你

② 最小生成树课程设计

给你说说思路吧

在所有的边中选择权值最小的一个边 对其进行如下操作：专
将该边加入生成树属中 如果存在环 则删除该边
重复上面的操作 n-1 次
即可找到包含n个结点的最小生成树

至于怎么判断是否存在环 可以使用并查集 当然 最简单的方法是为每个边建立一个bool型变量 其包含在生成树里面时 设置为true 否则为false 每次加边之前判断边的头结点和尾结点的bool变量是否都为true就可以

具体怎么实现 还是希望楼主自行CODE
毕竟这个是基本功

③ 最小生成树的实现（避圈法）课程设计怎么弄

#include<stdio.h>
#include<stdlib.h>
#define M 20
#define MAX 20typedef struct
{
int begin; //头顶点
int end; //末顶点
int weight; //权值
}edge;typedef struct
{
int adj;
int weight;//权值
}AdjMatrix[MAX][MAX];typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;//总边 点 的值
}MGraph;
//函数申明
void CreatGraph(MGraph *); //图构建
void sort(edge* ,MGraph *); //权值排序
void MiniSpanTree(MGraph *); //生成最小树
int Find(int *, int );// 尾顶点查找
void Swapn(edge *, int, int);//权值、头顶点、尾顶点交换
void CreatGraph(MGraph *G)//构件图
{
int i, j,n, m;

printf("请输入边数和顶点数:\n");
scanf("%d %d",&G->arcnum,&G->vexnum);

for (i = 1; i <= G->vexnum; i++)//初始化图
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}

for ( i = 1; i <= G->arcnum; i++)//输入边和权值
{
printf("请输入有边的2个顶点\n");
scanf("%d %d",&n,&m);
while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum)
{
printf("输入的数字不符合要求 请重新输入:\n");
scanf("%d%d",&n,&m);
}

G->arc[n][m].adj = G->arc[m][n].adj = 1;
getchar();
printf("请输入%d与%d之间的权值:\n", n, m);
scanf("%d",&G->arc[n][m].weight);
}

printf("邻接矩阵为:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}void sort(edge edges[],MGraph *G)//对权值进行排序
{
int i, j;

for ( i = 1; i < G->arcnum; i++)
{
for ( j = i + 1; j <= G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);//交换i和j 这两条边
}
}
}

printf("权排序之后的为:\n");
for (i = 1; i < G->arcnum; i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}

}void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
{

int temp;

temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;//交换头顶点 temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;//交换尾顶点 temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;//交换权值
}void MiniSpanTree(MGraph *G)//生成最小生成树
{
int i, j, n, m;
int k = 1;
int parent[M];
edge edges[M];

for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}

}
}

sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)//核心部分
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)//判断是否有回路，如果有，舍弃
{
parent[m] = n;
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}int Find(int *parent, int f)//找尾
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}int main(void)//主函数
{
MGraph *G;

G = (MGraph*)malloc(sizeof(MGraph));//为图动态分配存储空间
if (G == NULL)//如果图没有创建，则程序非正常结束
{
printf("memory allcation failed,goodbye");
exit(1);
}

CreatGraph(G);//创建一个图
MiniSpanTree(G);//求最小生成树

system("pause");//系统暂停运行
return 0;

④ C语言 课程设计 最小生成树的详细设计，还有能让人理解的话解释一下这个编程到底在做什么事情

我已经发到你的邮箱

⑤ 跪求最小生成树课程设计

给我邮箱，我发到你邮箱里
我已经发到你邮箱了

⑥ 急求，数据结构课程设计用Kruskal 算法求最小生成树

将城市看成是点，城市之间的距离看成是点之间的权值。
下面是PRIM算法实现的最小生成树代码。，利用邻接矩阵存储边的信息。程序已通过编译了，可以直接运行。
#include <stdio.h>
#include <string.h>
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3
/*顶点字符串的最大长度+1*/
#define MAX_INFO 20
/*相关信息字符串的最大长度+1*/
typedef char VertexType[MAX_NAME];
#define INFINITY 32767
/*用整型最大值代替无穷大*/
#define MAX_VERTEX_NUM 20
/*最大顶点个数*/
typedef enum GraphKind;
/**/
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef struct
{
VRType adj;
/*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/
/*对带全图，则为权值类型*/
InfoType *info;
/*该弧相关信息的指针（可无）*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
/*顶点向量*/
AdjMatrix arcs;
/*邻接矩阵*/
int vexnum,arcnum;
/*图的当前顶点数和弧数*/
GraphKind kind;
/*图的种类标志*/
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /*初始条件：图G存在，u和G中顶点有相同特征*/
/*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1*/
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
int CreateAN(MGraph *G)
{/*采用数组（邻接矩阵）表示法，构造无向网G*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("please input number of acmes and arcs in G,and there is some information in arc,if yes is 1,else is 0:");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("please input the value of %d acmes(<%d character):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)
/*构造顶点向量*/
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)
/*初始化邻接矩阵*/
for(j=0;j<(*G).vexnum;++j)
{(*G).arcs[i][j].adj=INFINITY;
/*网*/
(*G).arcs[i][j].info=NULL;
}
printf("please input %d the first and the second of acr and weigh:\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s %s %d",va,vb,&w);
/*%*c吃掉回车符*/
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;
/*无向*/
if(IncInfo)
{
printf("please input some information about the arc(<%d character): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info;
/*无向*/
}
}
}
(*G).kind=DN;
return 1;
}
typedef struct
{/*记录从顶点集U到V-U的代价最小的边的辅助数组定义*/
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int mininum(minside SZ,MGraph G)
{/*求closedege,lowcost的最小正值*/
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{/*用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
/*辅助数组初始化*/
{
if(j!=k)
{ strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
/*初始U=*/
printf(":\n");
for(i=1;i<G.vexnum;++i)
{/*选择其余G.vexnum-1个顶点*/
k=mininum(closedge,G);
/*求出T的下一个结点：第K顶点*/
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);
/*输出生成树的边*/
closedge[k].lowcost=0;
/*第K顶点并入U集*/
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{/*新顶点并入U集后重新选择最小边*/
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
void main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
}