kruskal.c

约瑟夫环问题

 /*========[最小生成树kruskal算法]========*/
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
 int begin;
 int end;
 int weight;
}edge;

typedef struct
{
 int adj;
 int weight;
}AdjMatrix[30][30];

typedef struct
{
 AdjMatrix arc;
 int vexnum, arcnum;
}MGraph;

void CreatGraph(MGraph *G)/* 构建图 */
{
 int i, j,n, m,t;
 
 printf("***===最小生成树kruskal算法===***\n");
 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++)/* 输入边和权值  */
 {
   loop: printf("\n请输入有边的2个顶点");
   scanf("%d %d",&n,&m);

  while(n < 0 || n > G->vexnum || m < 0 || m> G->vexnum||n==m)
  {
   printf("输入的数字不符合要求 请重新输入:");
    goto loop;
  }
   if (n>m){t=n;n=m;m=t;}

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


}
 void Jiaohuan(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 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)
      {
       Jiaohuan(edges, i, j);
      }
    }
 }
    
 }

  void MiniSpanTree(MGraph *G)/* 生成最小生成树  */
{
 int i, j, n, m;
 int k = 1;
    int parent[30];

 edge edges[30];
 
 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最小生成树为:\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("失败了，再见");

 }
    
 CreatGraph(G);
 MiniSpanTree(G);
 }