<图>最小生成树的几个算法。

 
四、去边法： 
 
1、将图中所有边按权值从大到小排序； 
2、去掉权值最大的边，若图不再连通则保留此边，再选取下一权值较大的边去掉； 

3、反复此过程，直到图中只剩下 n-1 条边为止。 

下面的程序是实现Prim、去边法、Kruskal算法的。弄好了久好久，出现了很多Bug，很多地方方法也可能不够简。可能还有很多Bug，但先收手了。

   
                                                             第 四 次 上 机 作 业
        输入无向图的邻接矩阵，使用前面讲过的任意三种方法求该图的最小代价生成树，并分析各自的时间复杂度。 

#include<iostream>
#include<queue>
using namespace std;

/***************************基本上共用的大模块（结构定义，邻接矩阵输入）************************************/

#define MAX_VERTEX_NUM 20

typedef struct   //存放连接矩阵权值的一个结点
{
 int weight;
}Adj,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct  //连接矩阵
{
 AdjMatrix arc;  //存权值的域
 int vexnum;     //节点个数
 int edge;       //边的个数
}MGraph;

typedef struct Node  //用链表表示
{
 int v1;          //v1，v2为边的两个结点
 int v2;
 int weight;
 struct Node *next; //指向下一个结点
}Node;
typedef Node *NODEPTR;

void CreateMGraph(MGraph &M)
{
 /*创建一个邻接矩阵表示有权图*/

 cout<<"请输入结点的个数:";
 cin>>M.vexnum;
 M.edge=0;
 cout<<"请输入该图的邻接矩阵:"<<endl;
 for(int i=1;i<=M.vexnum;i++)
 {
  for(int j=1;j<=M.vexnum;j++)
  {
   cin>>M.arc[i][j].weight;
   if(M.arc[i][j].weight)
    M.edge++;
  }
 }
}

/***********************查找最小生成树的Prim算法**********************************/

struct Closedge
{
 int adjvex;
 int lowcost;
};
struct Closedge closedge[MAX_VERTEX_NUM];//附设一个辅助数组，以记录从V-U具有最小代价的边。
/*寻找closedeg数组里的最小权值（除去0以外的）*/
int minimun(struct Closedge closedge[],MGraph m)
{
 int node=-1,min;
 for(int i=1;i<=m.vexnum;i++)
 {
  if(closedge[i].lowcost!=0)
  {
   min=closedge[i].lowcost;
   node=i;//先找到第一个
   break;
  }
 }
 i++;
 for(;i<=m.vexnum;i++)//再作比较找更小的
 {
  if(closedge[i].lowcost!=0&&closedge[i].lowcost<min)
  {
   min=closedge[i].lowcost;
   node=i;
  }
 }
 return node;//返回的是这个最小权值的在closedge的位置，即为下一个归入的结点
}

void print(struct Closedge closedge[],MGraph m)
{  //用来观察closedge数组的变化的

 for(int i=1;i<=m.vexnum;i++)
 {
  cout<<"v="<<closedge[i].adjvex<<" lowcost="<<closedge[i].lowcost<<endl;
 }
}

/*这个程序中是每一结点都是对应closedge的下标，所以书本的下标和长度有点出入*/
void MiniSpanTree_PRIM(MGraph m,int u)
{
 int total=0;
 cout<<"从第1个结点开始归并:"<<endl;
 for(int j=1;j<=m.vexnum;j++)
 {
  if(m.arc[u][j].weight)
  {
   closedge[j].adjvex=u;
   closedge[j].lowcost=m.arc[u][j].weight;
  }
  else
   closedge[j].lowcost=10000;
 }
 closedge[u].lowcost=0;
 //print(closedge,m);
 for(int i=1;i<=m.vexnum;i++)
 {
  int k=minimun(closedge,m);
  if(k==-1)//当所有的结点都归并后，就没有找到结点。程序结束。
  {
   cout<<"最小生成树的长度为:"<<total<<endl;
   return;
  }
  cout<<"并入的结点是:"<<k<<" 权值为:"<<closedge[k].lowcost<<endl;  //输出生成树的边
  total=total+closedge[k].lowcost;
  closedge[k].lowcost=0;
  for(j=1;j<=m.vexnum;j++)
  {
   if(m.arc[k][j].weight!=0&&m.arc[k][j].weight<closedge[j].lowcost)
   {
    closedge[j].adjvex=k;//新的结点并入后重新查找最小的边
    closedge[j].lowcost=m.arc[k][j].weight;
   }
  }
 // print(closedge,m);
 }
}

/*************************查找最小生成树的--去边法算法**********************************************/

NODEPTR CreateList(MGraph M)
{
 /*把邻接矩阵安从大到小的顺序组成链表，用于去边法使用。*/

 NODEPTR head=NULL,last=NULL,pre,cur;
 for(int i=1;i<=M.vexnum;i++)
 {
  for(int j=i;j<=M.vexnum;j++)//因为是对称矩阵，所以不用遍历整个矩阵。
  {
   if(M.arc[i][j].weight)//当两个节点之间有权值的时候。
   {
    cur=new Node;
    cur->v1=i;
    cur->v2=j;
    cur->weight=M.arc[i][j].weight;
    if(!head)//头结点为空时，直接加入。
    {
     head=cur;
     head->next=NULL;
    }
    else
    {
     pre=head;
     while(pre) //排序插入。
     {
      if(pre->weight<cur->weight)
      {
       if(!last) //插在头结点的位置。
       {
        cur->next=pre;
        head=cur;
       }
       else
       {
        last->next=cur;
        cur->next=pre;
       }
       break;
      }
      last=pre;
      pre=pre->next;
     }
     if(!pre) //插在尾结点的位置。
     {
      last->next=cur;
      cur->next=NULL;
     }
    }
   }
  }
 }
 /*打印出链表，看看是否连接有误。
 cout<<"组成的链表为:"<<endl;
 NODEPTR tmp=head;
 while(tmp)
 {
  cout<<"["<<tmp->v1<<" "<<tmp->v2<<"]"<<"("<<tmp->weight<<")==>";
  tmp=tmp->next;
 }
 cout<<endl;
 */
 return head;
}

/*用了广度优先搜索的思想，判断是否连通，连通返回true*/
bool Connectivity_BFS(MGraph m)
{
 queue<int> q;
 bool visa[MAX_VERTEX_NUM];//之前先初始化为false
 int count=0;
 memset(visa,0,sizeof(visa));
 q.push(1);
 while(!q.empty())
 {
  int v=q.front();
  visa[v]=true;
  q.pop();
  count++;
  for(int i=1;i<=m.vexnum;i++)//把与v连通并且没有被访问过的结点压进队列里面。
  {
   if(m.arc[v][i].weight)
    if(!visa[i])
    {
     q.push(i);
     visa[i]=true;//标志被访问过。
    }
  }
 }
 if(count==m.vexnum)//如果压进栈的结点个数刚好等于总结点的个数，则连通。
  return true;
 return false;
}

void FindPath_DeletEdge(NODEPTR head,MGraph M)
{
 MGraph map;
 for(int i=1;i<=M.vexnum;i++)  //为了保持原来矩阵的完整性，所以把整个图复制再删减边。
 {
  for(int j=1;j<=M.vexnum;j++)
  {
   map.arc[i][j].weight=M.arc[i][j].weight;
  }
 }
 map.edge=M.edge;
 map.vexnum=M.vexnum;

 int count=1;
 cout<<"依次删去的边是:"<<endl;
 while(head)
 {
  map.arc[head->v1][head->v2].weight=0;
  map.arc[head->v2][head->v1].weight=0;
  if(!Connectivity_BFS(map))     //如果删去边之后不连通的话，就要恢复原样。
  {
   map.arc[head->v1][head->v2].weight=head->weight;
   map.arc[head->v2][head->v1].weight=head->weight;
  }
  else
  {
   cout<<"["<<head->v1<<" "<<head->v2<<"]"<<"("<<head->weight<<")"<<endl;
   map.edge--;
  }
  if(map.edge==map.vexnum-1)
   break;
  head=head->next;
 }

 /*输出减边之后的邻接矩阵*/
 cout<<"最小路径的图为:"<<endl;
 int total=0;
 for(i=1;i<=map.vexnum;i++)
 {
  for(int j=1;j<=map.vexnum;j++)
  {
   cout<<map.arc[i][j].weight<<" ";
   total=total+map.arc[i][j].weight;
  }
  cout<<endl;
 }
 cout<<"最小路径的长度是:"<<total/2<<endl;
}

/************************查找最小生成树的Kruskal算法**********************************/

void ReverseList(NODEPTR &head)
{
    /*把之前安升序存放的链表用降序排列，用于kruskal算法（增边）*/

 NODEPTR newhead=NULL;
 newhead=head;
 head=head->next;
 newhead->next=NULL;
 
 while(head)
 {
  NODEPTR temp=head->next;
  head->next=newhead;
  newhead=head;
  head=temp;
 }
 head=newhead;
}

/*为了弄好这个找回路的函数，都快要哭了~~~要弄到的东西一大堆。有向图还比较好弄一点。*/
void Circle_DFS(MGraph m,int v,int pre,int vx,int dep,bool &flag)
{//用pre来记录当前vx的前一个，因为是无向图，所以很容易走回头路。dep记录深度。flag是是否有解，传引用。
  if(dep>1&&vx==v)
  {
   flag=true;
   return;
  }
  else
  {
   for(int i=1;i<=m.vexnum;i++)
   {
    if(m.arc[vx][i].weight&&i!=pre)//i!=pre是以免走回头路。
    {
     Circle_DFS(m,v,vx,i,++dep,flag);
    }
   }
  }
 
 return;
}

/*遍历head链表表示的带权图，创建path链表存放查找的过程中添加的结点和路径。*/
void FindPath_KRUSKAL(NODEPTR head,MGraph M)
{
 MGraph map;
 for(int i=1;i<=M.vexnum;i++)
 {
  for(int j=1;j<=M.vexnum;j++)
  {
   map.arc[i][j].weight=0;
  }
 }
 map.vexnum=M.vexnum;
 map.edge=M.edge;
 cout<<"依次添加的边是:"<<endl;
 int count=0;
 while(head)
 {
  map.arc[head->v1][head->v2].weight=head->weight;
  map.arc[head->v2][head->v1].weight=head->weight;
  count++;
  bool flag=false;
  Circle_DFS(map,head->v1,head->v1,head->v1,1,flag);
  if(flag)//如果添加边之后是有回路的话，则不能添加。
  {
   map.arc[head->v1][head->v2].weight=0;
   map.arc[head->v2][head->v1].weight=0;
   count--;
  }
  else
  {
   cout<<"["<<head->v1<<" "<<head->v2<<"]"<<"("<<head->weight<<")"<<endl;
  }
   
  if(count==map.vexnum-1)//当添加的边数为结点数-1的时候，添加成功。
   break;
  head=head->next;
 }
  
  /*输出减边之后的邻接矩阵*/
 cout<<"最小路径的图为:"<<endl;
 int total=0;
 for(i=1;i<=map.vexnum;i++)
 {
  for(int j=1;j<=map.vexnum;j++)
  {
   cout<<map.arc[i][j].weight<<" ";
   total=total+map.arc[i][j].weight;
  }
  cout<<endl;
 }
 cout<<"最小路径的长度是:"<<total/2<<endl;

}

void Delet(NODEPTR head)
{
 /*释放链表的内存。*/
 NODEPTR tmp;
 while(head)
 {
  tmp=head->next;
  free(head);
  head=tmp;
 }
 head=NULL;
}

int main()
{
 MGraph MAP;
 CreateMGraph(MAP);

 cout<<"\n\n用Prim算法——:"<<endl;
 MiniSpanTree_PRIM(MAP,1);
 cout<<endl<<endl;

 cout<<"用去边法——:"<<endl;
 NODEPTR head;
 head=CreateList(MAP);
 FindPath_DeletEdge(head,MAP);
 cout<<endl<<endl;

 cout<<"用Kruskal算法——:"<<endl;
 ReverseList(head);
 FindPath_KRUSKAL(head,MAP);

 Delet(head);

 return 0;
}