图的最小支撑树

发布于 2019-11-14 18:04:52   阅读量 241  点赞 0  

  • 连通性:若无向图的边有权值,则成该无向图为无向网;若无向网中每个顶点都相通,称为连通网

  • 支撑树:连通图G的某一无环连通子图T若能覆盖G中所有顶点,则称T为G的一棵支撑树生成树

  • 最小支撑树:若图G为一带权网络,则每一棵支撑树的成本为其所拥有的各边的权重的总和。在G的所有支撑树中,成本最低的称为最小支撑树


一、普利姆算法

 在图 G=(V,E) 中,顶点集 V 的任一子集 U 及其补集 V-U 都构成 G 的一个割,记作 (U:V-U)。若边uv满足 u\in Uv\not\in U,则称作该割的一条跨越边。跨越边连接 VV 的补集,故可将其形象地看作该割的一座桥。而 Prim算法 基于以下事实:最小支撑树总是会采用联结每一割的最短跨越边。

 先假设G=(V,E)是连通网, TEG上最小生成树中边的集合:

  1. U={u_0},(u_0\in V),TE={ }

  2. 在所有的u\in U,v\in V-U的边(u,v)\in E中找一条代价最小的边(u,v_0)并入集合TE,同时v_0并入U

  3. 重复2,直到U=V


实现:(基于矩阵的无向带权网络)

void minspantree_prim(int v){   //v为生成树的起始点
    int k,j,i;
    int low=10000;
    struct{
        int adj;                //指示是由哪个顶点到该顶点
        int lowcost;            //存储最小权值
    }closedge[MAXVERTEXNUM];    //用数组存储到各顶点的最小路径权值,使用数组下标指示到某顶点

    k=v;                        //先使用v,先求由v到其他各顶点的最短路径

    closedge[v].lowcost=0;
    for(j=0;j<VertexNum;j++){       //初始化,将数组中的元素表示为由k到各顶点的路径权值
        if(j!=k){
            closedge[j].adj=k;
            if(AdjMatrix[k][j]==0)  
                closedge[j].lowcost=10000;
            else
                closedge[j].lowcost=AdjMatrix[k][j];
        }
        }
    for(i=1;i<VertexNum;i++){
        low=10000;
        for(j=0;j<VertexNum;j++){           //找出当前点集数组所有路径的最小权值路径
            if(low>closedge[j].lowcost && closedge[j].lowcost!=0)
            {   
                low=closedge[j].lowcost;    
                k=j;
            }
        cout<<closedge[k].adj<<" "<<k<<" "<<closedge[k].lowcost<<endl;

        closedge[k].lowcost=0;              //使用lowcost=0表示该点已访问过

        for(j=0;j<VertexNum;j++)            //使用上一步骤中找到的顶点来更新点集最短权值路径
        {
            if(closedge[j].lowcost>AdjMatrix[k][j] && AdjMatrix[k][j]!=0 && k!=j)
            {
                closedge[j].adj=k;
                closedge[j].lowcost=AdjMatrix[k][j];
            }
    }

}
}
}

 以上代码的关键为定义结构:

struct Arc{
    int adj;
    int lowcost;
}

 再定义结构数组:

Arc closedge[MAXVERTEXNUM];

 以closedge[i].adj的方式存储由adj指向i的路径权值。



二、克鲁斯卡尔算法

  不断地从图中选取最小权重不会使树含有环的路径,生成搜索树,直到图中所有顶点都在搜索树上。

实现细节: 使用数组标识当前加入搜索树的两个点是否属于同一阵营,若是,则该路径加入搜索树会产生环。

算法实现:

void Krus(){
    int *group=new int[VertexNum];      //使用数组标识阵营信息
    for(int i=0;i<VertexNum;i++){
        group[i]=i;
    }


    int matrix[MAXVERTEXNUM][MAXVERTEXNUM];     //创建临时的矩阵,后续的操作会对矩阵进行修改

    for(int i=0;i<VertexNum;i++){
        for(int j=0;j<VertexNum;j++){
            matrix[i][j]==AdjMatrix[i][j];
        }
    }

    for(int i=0;i<VertexNum-1;i++){
        int from=-1,to=-1;
        shortest(from,to,group);          //找出当前权重最小的边
        cout<<Vertex[from]<<" "<<Vertex[to]<<" "<<AdjMatrix[from][to]<<endl;    //起点 终点 权重
        matrix[from][to]=2*INFINITY;        //将已加入搜索树的路径权值设为无穷大,已防止被再次访问
        matrix[to][from]=2*INFINITY;            

        for(int x=0;x<VertexNum;x++){       //将所有from同阵营的顶点加到与to同阵营
            if(group[x]==group[from] && x!=from)
                group[x]=group[to]; 
        }
        set[from]=set[to];      
    }

}


Last Modified : 2020-09-27 15:49:14