#include#include#define M 20#define MAX 20
typedef 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("请输入边数和顶点数:"); 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("\n请输入有边的2个顶点"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求 请重新输入:"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("\n请输入%d与%d之间的权值:", 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); } } } 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[n] = m; 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;}
