通信网络的最小生成树配置，它是使右侧的生成树值并最小化。经常使用Prim和Kruskal算法。看Prim算法：以防万一N={V,{E}}它是在通信网络，TE它是N设置边的最小生成树。从算法U={u0}(uo属于V)。TE={}开始，复运行下述操作：在全部u属于U。v属于V-U的边（u,v）属于E中找到代价最小的一条边（u0,v0）并入集合TE，同一时候v0并入U，直至U=V为止。此时TE中必有n-1条边，T={V,{TE}}为N的最小生成树。

为实现此算法，需另设一个辅助数组closedge,以记录从U到V-U中具有最小权值的边。每次有新的顶点并入U，就要更新一次closedge。

详细代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include "../Header.h"using namespace std;//普里姆算法构造最小生成树const int MAX_VERTEX_NUM=20;  //最大顶点数typedef enum {DG,DN,UDG,UDN} GraphKind ;//(有向图。有向网。无向图，无向网)typedef int VRType;typedef char InfoType;typedef char VertexType;#define INFINITY INT_MAXtypedef struct ArcCell{    VRType adj;  //VRType是顶点关系类型，对于无权图。用1或者0表示顶点相邻与否。对于有权图。则为权值类型    InfoType  info;//该弧相关信息指针    ArcCell(){        adj=0;        info=0;    }}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct MGraph{    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量    AdjMatrix arcs;  //邻接矩阵    int vexnum,arcnum;  //图当前的顶点数和弧数    GraphKind kind;  //图的种类标志}MGraph;//记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef struct minedge{    VertexType adjvex;    VRType lowcost;}minedge,Closedge[MAX_VERTEX_NUM];int minimum(MGraph G,Closedge closedge){    int min=1;    for(int i=1;i
        
         0)            min=i;    }    return min;}int LocateVex(MGraph G,VertexType v1){    for(int i=0;i
         
          >vexnumber>>arcnumber>>info;    G.vexnum=vexnumber;    G.arcnum=arcnumber;    for(int i=0;i
          
           >G.vexs[i]; } for(int i=0;i
           
            >v1>>v2>>weight; i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj=weight; G.arcs[j][i].adj=weight; if(info!=48){//0的ascii码为48 cout<<"please input infomation: "; cin>>infomation; G.arcs[i][j].info=infomation; G.arcs[j][i].info=infomation; } } return OK;}void DisMGraph(MGraph m){ for(int i=0;i
           
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。