专注细节
努力进步

最小生成树算法

1,最小生成树

首先,要想明白什么是最小生成树,得先知道什么是连通图,连通图的概念是,对无向图,图中任意两点都可有路径达到为连通图;对有向图,任意两节点有路径到达为强连通图。而最小生成树是原图的最小连通子图,包括原图中所有的点,且保持图联通的最小的边。

2,最小生成树的两种算法

构造最小生成树的方法主要有两种:一种是普里姆算法(Prim);一种是克鲁斯卡尔(Kruskal)算法。

    1. Prim算法
    2. /************************************************************************/
      /* Prim函数原理:
      1,初始时,集合U={A},集合V/U={B,C,D,E,F,G},T={},然后寻找U中点与V/U中点相
      连接的最小权值的边,然后将点加入到U中,如该点为B,则U={A,B},V/U={C,D,E,F,G}
      T={(A,B)}
      2,依次直到V/U为NULL*/
      /************************************************************************/

      #ifndef PRIM
      #define PRIM
      #include “prim.h”
      #endif

      // 临时数组lowCost[v]保存了集合U中节点u_i与集合V/U中节点v_j的所有边中当前具有最小权值的边
      void prim(AdjMGraph G, MinSpanTree closeVertex[]){
      ItemType x;
      list temp=G.Vertices;
      int n=G.Vertices.size(),minCost;
      int *lowCost=new int[n];
      // 节点0做为初始时U的点
      for(int i=0;i<n;i++)
      lowCost[i]=G.edge[0][i];
      x=G.Vertices.front();
      G.Vertices.pop_front();
      closeVertex[0].vertex=x;
      lowCost[0]=-1;
      int k;

      for(int i=1;i<n;i++){
      minCost=MaxWeight;
      //寻找U与V/U中,与节点i相连接的边权值最小的点
      for(int j=1;j<n;j++){
      if(lowCost[j]0){
      minCost=lowCost[j];
      k=j;
      }
      }
      //取出第k个元素
      list::iterator index=temp.begin();
      for(int ii=0;ii<k&&index!=temp.end();ii++,index++){

      }
      x=*index;

      //注意这里使用remove,而不是用erase的原因,erase是以position做参数的,每次移除后,position没有动态发生变化,故很容易发生越界错误,而根据list中的内容不会发生越界错误

      G.Vertices.remove(*index);
      closeVertex[i].vertex=x;
      closeVertex[i].weight=minCost;
      lowCost[k]=-1;
      // 更新lowCost为节点k相连的权值集合
      for(int i=1;i<n;i++){
      // 这里判断是否小于lowCost[i]的原因在于之前已经加入U的点与此次点可能有连接,之前我们已经将连接置于-1了,所以要排除这种情况
      // 如按上述实验第一个U中点为A,但是第二个点B与A连接同样有50,但是这里因为是U中点与V/U中点的最小权值,因此这里不能考虑(B,A)
      // 所以要进行一下判断
      if(G.edge[k][i]<lowCost[i])
      lowCost[i]=G.edge[k][i];
      }

      }
      }

      具体code见Prim算法

    3. 克鲁斯卡尔(Kruskal)算法
    4. 克鲁斯卡尔算法的基本原理是,首先初始化最小生成树T=(V,{}),然后按E中边的权值的递增顺序考察图G中边集合E的各条边,若被考察的边的两个节点属于T的两个不同的连通分量(即不形成环),则将此边加入到最小生成树T中,反之则舍去;具体的算法就是如果判断是否属于两个不同的连通分量,这里是重点

      /*******************************************
      最小生成树之克鲁斯卡尔算法
      by Rowandjj
      2014/7/9
      *******************************************/
      #include
      using namespace std;

      #define MAX_VERTEX_NUM 20//最大顶点数

      typedef struct _EDGE_
      {
      int begin;//起始点序号
      int end;//终点序号
      int weight;//权值
      }Edge[MAX_VERTEX_NUM];//边集数组

      typedef struct _GRAPH_
      {
      Edge edge;//边集数组
      int numVertiexs;//顶点数
      int numEdges;//边数
      }Graph;//图存储结构—>边集数组结构

      //——————————————
      void CreateGraph(Graph* g);//构建有权无向图g
      void Display(Graph g);//输出图g的相关信息

      int Find(int *parent,int f);
      void MiniSpanTree_Kruskal(Graph g);//最小生成树之克鲁斯卡尔算法
      //——————————————
      void CreateGraph(Graph* g)
      {
      int i;

      cout<>g->numVertiexs;
      cin>>g->numEdges;

      cout<<“按权值从小到大顺序输入每条边的两个顶点及权值:”<<endl;
      //初始化边集数组
      for(i = 0; i < g->numEdges; i++)
      {
      cin>>g->edge[i].begin;
      cin>>g->edge[i].end;
      cin>>g->edge[i].weight;
      }
      }

      void Display(Graph g)
      {
      cout<<“顶点数:”<<g.numVertiexs< cout<<“打印各边信息:”<<endl;
      for(int i = 0; i < g.numEdges; i++)
      {
      cout<<g.edge[i].begin<“<<g.edge[i].end< 0)
      {
      f = parent[f];
      }
      return f;
      }

      void MiniSpanTree_Kruskal(Graph g)//最小生成树之克鲁斯卡尔算法
      {
      int i;
      int m,n;
      int parent[MAX_VERTEX_NUM];//定义辅助数组,用来判断边与边之间是否存在环路
      //1.初始化辅助数组
      for(i = 0; i < g.numVertiexs; i++)
      {
      parent[i] = 0;
      }

      //2.计算最小生成树
      for(i = 0; i < g.numEdges; i++)
      {
      n = Find(parent,g.edge[i].begin);
      m = Find(parent,g.edge[i].end);
      if(n != m)//如果没有形成c环,那么输出
      {
      parent[n] = m;//表示此顶点已经在生成树集合中

      cout<<g.edge[i].begin<“<<g.edge[i].end<}
      }
      }
      //——————————————
      int main()
      {
      Graph g;
      CreateGraph(&g);
      Display(g);

      cout<<“n最小生成树如下n”<<endl;
      MiniSpanTree_Kruskal(g);
      return 0;
      }

      具体分析见:最小生成树算法之克鲁斯卡尔算法

分享到:更多 ()