最小生成樹課程設計結論

① 最小生成樹——最優通信網 課程設計

你這個開發語言是什麼
平台
或資料庫都怎樣
談
我這樣才好幫你

② 最小生成樹課程設計

給你說說思路吧

在所有的邊中選擇權值最小的一個邊 對其進行如下操作：專
將該邊加入生成樹屬中 如果存在環 則刪除該邊
重復上面的操作 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();
}