邻接矩阵存储图-Prim 算法、Kruskal 算法、去边法

*********************************************************************************************************
 *
 * 程序完成的功能：输入并建立无向图的邻接矩阵，
 *       用 Prim 算法、Kruskal 算法以及去边法生成该图的最小代价生成树
 *
 * 作者：郭赞    

 *
 * 完成时间：2008年11月15日
 *
 * 程序说明：最大顶点数目初始为 10
 *    可选择自动生成邻接矩阵，也可自己输入
 *    一个顶点和自己之间的权值为 0
 *    没有直接连接的顶点之间的权值为 无穷大，即所能允许的最大值 Max_Num
 *
***********************************************************************************************************

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

#define Max_Size 10      //最大允许的顶点个数
#define Max_Num 65535     //系统允许的最大数
#define Wid 6       //输出数据的宽度
typedef char ElemType;     //顶点的数据类型

*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
边的基本定义，w 为权值             *
typedef struct ArcCell{     
 int w;
} Arc, AdjMatrix[ Max_Size ][ Max_Size ];

*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
对图的定义，vex[]中存储顶点，VexNum、ArcNum为顶点个数和边的条数*
typedef struct {      
 ElemType Vex[ Max_Size ];
 AdjMatrix Arcs;
 int VexNum;
 int ArcNum;
} Graph;

*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
对边集数组的定义，在 prim算法，及去边法 del中使用    *
typedef struct {
 int fromvex;
 int endvex;
 int weight;
} Edge;

************************************************************
各函数的函数头
************************************************************

int CreatUDN ( Graph &G );    //建立邻接矩阵
void AutoCreat ( Graph &G );   //建立默认邻接矩阵
int LocatVex ( Graph G, ElemType V ); //确定顶点在Vex[]中的位置
void OutPut ( Graph G );    //输出邻接矩阵中的各条边
int GetChoice ();      //输入选择
void Prim ( Graph G );     
void Kru ( Graph G );
void Del ( Graph G );     //去边法
int SortEdge ( Graph G, Edge sort[] );
int Findpath ( Edge e[], int len, int from, int end , int mark );
void copy ( Edge hold[], Edge S[], int len);

*******************************************************************************
主函数，实现程序功能
*******************************************************************************

int main()
{
 Graph G;
 int choice = 0;

 if ( !CreatUDN ( G ) ) {
  cout << "创建邻接矩阵失败" <<endl;
  return 1;
 }

 OutPut ( G );
 while( choice != 4) {
  switch ( choice = GetChoice () ) {
   case 1 :  Prim ( G );  break;
   case 2 :  Kru ( G );   break;
   case 3 :  Del ( G );   break;
   case 4 :  break;
   default :
    cout << "错误的选择!!!\a" <<endl;
    break;
  }
 }

 return 0;
}

*******************************************************************************
函数：建立邻接矩阵，成功返回 1  
**调用者：main                 *

int CreatUDN ( Graph &G )
{
 int i = 0, j = 0, k = 0, weight = 0;
 char choice = 'Y';
 ElemType v1, v2;

 cout << "需要为你自动创建邻接矩阵吗 Y/N" << endl;
 cin >> choice;
 fflush ( stdin );
 //自动创建默认邻接矩阵
 if ( choice == 'Y' || choice == 'y') {
  AutoCreat ( G );
  return 1;
 }

 //读入顶点,创建顶点间的权值为默认值
 cout << "请输入顶点个数：" << endl;
 G.VexNum = cin.get()- '0';

 cout << "请输入各顶点数据：" <<endl;
 for ( i = 0; i <= G.VexNum-1; i++ )
  cin >> G.Vex[ i ];
 for ( i = 0; i <= G.VexNum-1; i++ )
  for ( j = 0; j <= G.VexNum-1; j++ )
  {
   if ( i == j )
    G.Arcs[ i ][ j ].w = 0;
   else
    G.Arcs[ i ][ j ].w = Max_Num;
  }

 //创建各条边
 fflush(stdin);
 cout << "请输入边的条数：" << endl;
 G.ArcNum = cin.get()-'0';

 cout << "请输入各边的数据（V1 V2 权值）：" <<endl;
 for ( k = 0; k <= G.ArcNum-1; k++ ) {
  cin >> v1 >> v2 >> weight;
  //定位输入边的两个顶点的位置
  i = LocatVex( G , v1 );
  j = LocatVex( G , v2 );

  //输入的边的顶点数据有错误
  if( i == -1 || j == -1 ) {
   cout << "没有找到所要输入的边" <<endl;
   k--;
  }

  G.Arcs[ i ][ j ].w = weight;
  G.Arcs[ j ][ i ].w = weight;
 }
 
 return 1;
}

* 函数：在顶点数组 V[ ]中寻找所输入的数据 V，
  找到返回所在位置，否则返回 -1
 **调用者：手工创建邻接矩阵 CreatUDN  *

int LocatVex ( Graph G, ElemType V )
{
 int i = 0;
 for ( i = 0; i <= G.VexNum-1; i++ )
  if ( G.Vex[ i ] == V )
   return i;
 return -1;
}

*******************************************************************************
函数：自动建立邻接矩阵
      顶点分别为 a b c .....
   权值自动生成
**调用者：main                 *

void AutoCreat ( Graph &G )
{
 G.VexNum = Max_Size;
 for ( int i = 0; i <= G.VexNum-1; i++) {
  G.Vex[ i ] = 'A' + i;
  G.Arcs[ i ][ i ].w = 0;
 }

 //随机生成各条边之间的权值
 for ( int i = 0; i <= G.VexNum-1; i++)
  for ( int j = i+1; j <= G.VexNum-1; j++) {
   G.Arcs[ j ][ i ].w = G.Arcs[ i ][ j ].w = rand() % 50;
   //两点之间没有直接连接，权值为无穷大
   if ( G.Arcs[ j ][ i ].w == 0)
    G.Arcs[ j ][ i ].w = G.Arcs[ i ][ j ].w = Max_Num;
  }
}

*******************************************************************************
函数：输入选择
**调用者：main                 *

int GetChoice ()
{
 int choice = 0;

 cout << "请选择用何种算法求最小代价生成树：\n1-Prim 算法\n2-Kruskal 算法\n3-去边法\n4-退出" <<endl;
 cin >> choice;
 return choice;
}

*******************************************************************************
函数：输出邻接矩阵,以矩阵的格式输出
**调用者：main                 *

void OutPut ( Graph G )
{
 int i = 0, j = 0;

 cout << "邻接矩阵为：" <<endl;
 cout << setw ( Wid ) << " ";
 for ( i = 0; i <= G.VexNum-1; i++)
  cout << setw( Wid ) << G.Vex[ i ];
 cout <<endl;
 for ( i = 0; i <= G.VexNum-1; i++ ) {
  cout << setw( Wid ) << G.Vex[ i ];
  for ( j = 0; j <= G.VexNum-1; j++ ) {
   if ( G.Arcs[ i ][ j ].w == Max_Num )
    cout << setw( Wid ) << "*" ;
   else
    cout << setw( Wid ) << G.Arcs[ i ][ j ].w ;
  }
  cout << endl;
 }
}

*******************************************************************************
函数：prim算法求最小生成树
**调用者：main                 *

void Prim ( Graph G )
{
 // CT 中在第k个的时候，前 k-1个为已经放入最小树的顶点，后面的为没放入的
 Edge CT[ Max_Size ] ;
 Edge temp;
 int i = 0, j = 0, k = 0, w = 0, t = 0;

 //对应第0次的值，即和第一个顶点间的权值放入CT
 for ( i = 1; i < G.VexNum; i++) {
  CT [ i-1 ].fromvex = 0;
  CT [ i-1 ].endvex = i;
  CT [ i-1 ].weight = G.Arcs[ 0 ][ i ].w;
 }

 for ( k = 1; k < G.VexNum; k++) {
  //找到和已放入最小树的顶点的集合之间的权值最小的边
  int min = Max_Num;
  int m = k-1;
  for ( j = k-1; j < G.VexNum-1; j++)
   if ( CT[ j ].weight < min) {
    min = CT[ j ].weight;
    m = j;
   }

  //把最短边调换到 k-1位置
  temp = CT[ k-1 ];
  CT[ k-1 ] = CT[ m ];
  CT[ m ] = temp;

  //把新加入最小树的顶点值赋给 j
  j = CT [ k -1 ].endvex;

  //为下次求最小的边做准备，使树到数外各顶点之间的权值保持在最小
  for ( i = k; i < G.VexNum-1; i++) {
   t = CT[ i ].endvex;
   w = G.Arcs[ j ][ t ].w;
   //如果新加入的 j到某个顶点的权值小于目前的最小值，
   //将最小值更改为 j 到这个顶点的值，同时更改到这个顶点的树内顶点为 j
   if ( w < CT[ i ].weight) {
    CT[ i ].weight = w;
    CT[ i ].fromvex = j;
   }
  }
 }

 for ( i = 0; i < G.VexNum-1; i++ )
  if ( CT[ i ].weight == Max_Num ) {
   cout << "没有最小生成树" <<endl<<endl;
   return ;
  }

 for ( i = 0; i < G.VexNum-1; i++ ) {
  cout << setw( Wid ) << G.Vex[ CT[ i ].fromvex ]
  << setw( Wid ) << G.Vex [ CT[ i ].endvex ] << setw( Wid ) << CT[ i ].weight <<endl;
 }
}

*******************************************************************************
函数：kruskal算法求最小生成树
**调用者：main                 *

void Kru ( Graph G )
{
 //标记每个顶点所在的集合
 int  mark [ Max_Size ] = { 0 };
 int i = 0, j = 0, k = 0, temp1 = 0, temp2 = 0, sum = 0;
 int min = Max_Num, fromvex = 0, endvex  = 0, t = 0;

 //将所有顶点分属不同集合
 for ( i = 0; i <= G.VexNum-1; i++ )
  mark[ i ] = i;

 for ( t = 1; t <= G.VexNum-1; t++ ) {
  //找到权值最小的那条边，并且首尾顶点不在同一个集合
  min = Max_Num;
  for ( i = 0; i <= G.VexNum-1; i++ )
   for ( j = i+1; j <= G.VexNum-1; j++ )
    if ( mark[ i ] != mark[ j ] && G.Arcs[ i ][ j ].w < min ) {
      min = G.Arcs[ i ][ j ].w;
      fromvex = i;
      endvex = j;
    }

  if ( min != Max_Num ) {
   cout << setw( Wid ) << G.Vex[ fromvex ]
     << setw( Wid ) << G.Vex [ endvex ] << setw( Wid ) << min <<endl;
    sum ++;
  }

  //将首尾顶点所在的两个顶点集合合并为一个集合
  temp1 = mark [ endvex ];
  temp2 = mark [ fromvex ];
  for ( k = 0; k <= G.VexNum-1; k++) {
   if ( mark [ k ] == temp1 )
    mark [ k ] = temp2;
  }
 }
 if ( sum != G.VexNum-1 )
  cout << "没有最小生成树" <<endl<<endl;
}

*******************************************************************************
函数：去边法求最小生成树
**调用者：main                 *

void Del ( Graph G )
{
 Edge S[ Max_Size * Max_Size ], hold[ Max_Size * Max_Size ];
 int i = 0, j = 0, len = 0, temp = 0, sum = 0;

 //将 G 中的有效边放入Sort中，并且将其由大到小排序，返回边的条数
 len = SortEdge( G, S);

 //从最大权值边开始，依次检测能否去掉
 for ( i = 0; i <= len-1; i++ ) {
  temp = S[ i ].weight;
  //去掉这条边
  S[ i ].weight = Max_Num;
  //做一份S的拷贝hold
  copy ( hold, S, len);
  //去掉后图不在连通，回复
  if ( ! Findpath ( hold, len, hold[ i ].fromvex, hold[ i ].endvex, i ) )
   S[ i ].weight = temp;
 }

 for ( i = 0; i<= len-1; i++ )
  if ( S[ i ].weight != Max_Num ) {
   cout << setw( Wid ) << G.Vex[ S[ i ].fromvex ]<< setw( Wid )
   << G.Vex[ S[ i ].endvex ] << setw( Wid ) << S[ i ].weight <<endl;
   sum++;
  }

 if ( sum != G.VexNum-1 )
  cout << "没有最小生成树" <<endl<<endl;
}

*  函数：排序，将 G 中的有效边放入Sort中，
    并且由大到小排序，返回边的条数
 **调用者：去边法 Del    *

int SortEdge ( Graph G, Edge sort[] )
{
 int len = 0, i = 0, j = 0, pass = 0;
 Edge Hold;

 //将图中的有效边放入sort中，并计算出条数
 for ( i = 0; i <= G.VexNum-1; i++ )
  for ( j = i+1; j <= G.VexNum-1; j++ )
   if ( G.Arcs[ i ][ j ].w != Max_Num ) {
    sort[ len ].fromvex = i;
    sort[ len ].endvex = j;
    sort[ len ].weight = G.Arcs[ i ][ j ].w;
    len++;
   }

 //冒泡排序，从大到小
 for ( pass = 0; pass <= len-2; pass++ )
  for ( i = pass+1; i <= len-1; i++ )
   if ( sort[ pass ].weight < sort[ i ].weight ) {
    Hold = sort[ pass ];
    sort[ pass ] = sort[ i ];
    sort[ i ] = Hold;
   }
 return len;
}

*  函数：判断两点间是否有路径，有返回 1
 **调用者：去边法 Del     *

int Findpath ( Edge e[], int len, int from, int end, int mark)
{
 int i = 0, temp = 0;

 //此边已经使用过
 e[ mark ].weight = Max_Num;

 //找到路径
 if ( from == end )
  return 1;

 //依次搜索每条边，找到和此顶点相连接的有效边
 //继续以找到边的另一个顶点为基准搜索
 for ( i = 0; i < len; i++ )
  if ( e[ i ].weight != Max_Num ) {
   if ( e[ i ].fromvex == from )
    if ( Findpath ( e, len, e[ i ].endvex, end, i ))
     return 1;
   if ( e[ i ].endvex == from )
    if ( Findpath ( e, len, e[ i ].fromvex, end, i )) {
     return 1;
    }
  }
 return 0;
}

*  函数：把S拷进 hold
 **调用者：去边法 Del *

void copy ( Edge hold[], Edge S[], int len)
{
 for ( int i = 0; i < len; i++ )
  hold[ i ] = S[ i ];
}