+--

1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色问题 6、八皇后问题 7、原四则表达式求值 8、k阶斐波那契序列 9、遍历二叉树 10、编写DFS算法的非递归

/*克鲁斯卡尔(kruskal)算法构造最小生成树*/

//输入格式：
//input the number of the vertex:6节点数
//input the number of the ArcCell:6弧数
//input the ArcCell:<like this:0 2 36>输入弧信息，前两个整数为弧的两个顶点的序号，
//                                    它必须为从0到节点数减1的值，总共有输入弧数条弧
//                                    第三个数为权值
//0 1 2
//0 2 3
//2 1 6
//4 3 8
//3 5 10
//1 5 7


#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define infinity 30000
#define MAX 20
#define null 0

int s[MAX];     //节点归入记录

typedef struct ArcCell{          //邻接矩阵
  int adj;
}AecCell,AdjMatrix[MAX][MAX];

typedef struct Mgraph{      //顶点
  char vex[MAX];
  AdjMatrix arcs;
  int vexnum,arcnum;
}Mgraph;

typedef struct record{          //记录 
  int v1,v2,val;
  struct record*next;
}record,*rec;

record* head=(record *)malloc(MAX*sizeof(record));

int Create(Mgraph&G)     //建图
{
   int i,j,value,n=0;
   int v1,v2,a,b; 
   record *r1,*r2;
   int LocateVex(Mgraph G,char name);
   
   
   
   printf("input the number of the vertex:");
   scanf("%d",&G.vexnum);
   printf("input the number of the ArcCell:");
   scanf("%d",&G.arcnum);
   
   for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
       G.arcs[i][j].adj=infinity;

   printf("input the ArcCell:\n");
   
   for(j=0;j<G.arcnum;j++)
   {  
	  scanf("%d %d %d",&a,&b,&value);
	  v1=a-1;v2=b-1;
      G.arcs[v1][v2].adj=G.arcs[v2][v1].adj=value;
      r1=(record *)malloc(MAX*sizeof(record));
      r1->v1=v1;
      r1->v2=v2;
      r1->val=value;
      if(head->next==null)
	  {
        head->next=r1;
        r1->next=null;
      }  
      else
	  { 
        r2= head;
        while(r2->next!=null)
		{
          if(r2->next->val>value)break;
          r2=r2->next;
        }
        if(r2->next!=null)
		{
          r1->next=r2->next;
          r2->next=r1;
        }
        else
		{
          r2->next=r1;
          r1->next=null;
        }  
      }               
   }
   return 1;
}
 
void kruskal(Mgraph G,record* r)//克鲁斯卡尔(kruskal)算法构造最小生成树
{                                            //adjvex[]记录最小生成树邻接点，lowcost[]记录弧的权值
  int i,v,v1,v2,val,fth=1;
  record*r2,*r3;
  for(v=0;v<G.vexnum;v++)//初始化
    s[v]=v;
  r2=head->next;
  while(r2!=null&&fth)
  {
    v1=r2->v1;
    v2=r2->v2;
    val=r2->val;
    r3=r2->next;
    if(s[v1]!=s[v2]){
      r2->next=r->next;
      r->next=r2;
      for(i=0;i<G.vexnum;i++)
       if(s[i]==s[v2])
        s[i]=s[v1];
    }
    fth=0;
    for(i=1;i<G.vexnum;i++)
     if(s[0]!=s[i]){
      fth=1;
      break;
     } 
    r2=r3;    
  } 
}


int main(int argc, char *argv[])
{
  int i,j;
  Mgraph G;
  int adjvex[MAX];
  int lowcost[MAX];
  record*r=(record *)malloc(MAX*sizeof(record));
  head->next=null;
  Create(G);
  record*r2=head->next;
  printf("The ArcCell is:\n");
  kruskal(G,r);
  for(r=r->next;r!=null;r=r->next)
     printf("v%d -- v%d cost=%d;\n",r->v1+1,r->v2+1,r->val);        
  system("PAUSE");	
  return 0;
}



//vexunm=6,arcnum=10
/*
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/