精华内容
下载资源
问答
  • 最小支撑树

    2019-11-13 21:30:12
    支撑树:连通图G的某无环连通子图T若能覆盖G所有顶点,则称T为G的棵支撑树或生成树。 最小支撑树:若图G为带权网络,则每棵支撑树的成本为其所拥有的各边的权重的总和。在G的所有支撑树,成本最低的称为...
    • 连通性:若无向图的边有权值,则成该无向图为无向网;若无向网中每个顶点都相通,称为连通网

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

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

    一、普利姆算法

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

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

    1. U = u 0 , ( u 0 ∈ V ) , T E = { } U={u_0},(u_0\in V),TE=\{\} U=u0,(u0V),TE={}
    2. 在所有的 u ∈ U , v ∈ V − U u\in U,v\in V-U uU,vVU的边 ( u , v ) ∈ E (u,v)\in E (u,v)E中找一条代价最小的边 ( u , v 0 ) (u,v_0) (u,v0)并入集合 T E TE TE,同时 v 0 v_0 v0并入 U U U
    3. 重复2,直到 U = V U=V 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];      
        }
          
    }
    
    展开全文
  • =vs2) //边的两顶点在不同的连通分量上,不形成回路  { cout[i].Head+1; cout[i].Tail+1 "; cout[i].lowcost; for(int j=0;j;j++) { if(Vexset[j]==vs2) Vexset[j]=vs1; //...
    #include <iostream>
    
    #include <algorithm>


    using namespace std;


    const int INF=99;


    const int n=6;  //顶点数


    int G[n][n]={INF,  6,  1,  5,INF,INF,
                   6,INF,  5,INF,  3,INF,
                   1,  5,INF,  5,  6,  4,
                   5,INF,  5,INF,INF,  2,
                 INF,  3,  6,INF,INF,  6,
                 INF,INF,  4,  2,  6,INF,
                };


    struct Edge
    {
    int Head;
    int Tail;
    int lowcost;
    };


    Edge E[n*n];  
    int  Vexset[n];


    inline bool cmp(const Edge &e1,const Edge &e2)
    {
        return e1.lowcost < e2.lowcost;
    }


    int init()
    {
        int e=0;
        for(int i=0;i<n;i++)
        {
            Vexset[i]=i;
    for(int j=i+1;j<n;j++)  //矩阵上三角 
            {
                if(G[i][j]<INF)
                {
    E[e].Head   =i;
                    E[e].Tail   =j;
                    E[e].lowcost=G[i][j];
                    e++;
                }
            }  
        }
        sort(E,E+e,cmp);
    return e;    
    }


    void kruskal()
    {
    int e=init();
    for(int i=0;i<e;i++)  //遍历边 
    {
    int vs1=Vexset[E[i].Head];
    int vs2=Vexset[E[i].Tail];

    if(vs1!=vs2)      //边的两个顶点在不同的连通分量上,不形成回路 
    {
       cout<<"v"<<E[i].Head+1<<" ";
    cout<<"v"<<E[i].Tail+1<<"   ";
    cout<<E[i].lowcost<<endl;

       for(int j=0;j<n;j++)
    {
           if(Vexset[j]==vs2) Vexset[j]=vs1;  //合并vs1和vs2连同分量 
    }
    }
    }
    }


    int main()
    {
    kruskal();
        
        return 0;
    }
    展开全文
  • 最小支撑树:对于一个带权网络G,若G的某一无环连通子图能覆盖G所有的顶点,且其各边的权重总和最低,则称此树为G的最小支撑树。 事实上,在实际生活的网络架构设计,VLSI布线设计等诸多问...

    上篇博客介绍到优先级搜索是个通用的框架,其可以把广度优先搜索和深度优先搜索都包含在内,只需改变优先级的更新策略即可把PFS应用到一个具体的问题中,这里介绍PFS的一个典型的应用--图的最小支撑树生成问题。

    最小支撑树:对于一个带权网络G,若G的某一无环连通子图能覆盖G中所有的顶点,且其各边的权重总和最低,则称此树为图G的最小支撑树。

    事实上,在实际生活中的网络架构设计,VLSI布线设计等诸多问题都可以转换为最小支撑树问题,在这些问题中,边的权重往往等效于可量化的成本,因此作为此类优化问题的基本模型,最小支撑树的价值不言而喻。

    Prim算法的理论依据:最小支撑树总是会采用联接每一割的最短跨越边。

    策略:基本思想是把图G整个分为很多割,首先任选一个顶点A作为初始的子树,然后A及其顶点补集即形成一割,这时更新和A有关连边的所有顶点的优先级为关连边的权重,在这次迭代中遍历所有顶点,选择最小的作为新的点,加入遍历树并形成一个新的割(顶点A,B组成的集合及其补集),然后紧接着进行下一次遍历,依次检查和新拉入的顶点B有关联边的所有顶点,根据其与B的关连边的权重和其自身当前的优先级取最低并以该最小值更新该顶点的优先级,在这次迭代中遍历所有顶点,选择优先级数最低的点拉入遍历树,按照这一规律,将所有顶点都拉入遍历树,最小支撑树生成完毕。

    实现:根据此思路构造函数对象PrimPU作为优先级更新策略,带入优先级搜索框架中对整个图进行遍历。

    template<typename V, typename E> struct PrimPU
    {
    	void operator()(graph<V, E>* g, int uk, int v)
    	{
    		if (g->status(v) == UNDISCOVERED)   //若顶点v尚未被发现
    			if ((g->weight(uk, v)) < (g->priority(v)))  //比较当前边的权重和之前遍历时设置的优先级数
    			{
    				g->priority(v) = g->weight(uk, v);   //根据权重设置优先级数
    				g->parent(v) = uk;   //更新父节点
    				cout << "寻找顶点(uk,v)" << "(" << uk << "," << v << ")" <<"----w---"<<g->weight(uk,v)<< endl;
    			}
    	}
    };
    
    template<typename Tv, typename Te> void graph<Tv, Te>::prim(int s)
    {
    	PrimPU<Tv, Te> prioUpdater;
    	pfs(s, prioUpdater);
    }

    效率:若图G=(V,E)中共有n个顶点和e条边,则tSort仅需O(n^2)时间。

    展开全文
  • 最小支撑树(最小生成树)

    千次阅读 2019-05-04 20:33:23
    如下图所示,连通图G的某无环两通子图T若覆盖G所有的顶点,则称作G的支撑树或生成树(spanning tree)。 其中顶点数为n,其边数为n-1。 如果其生成树各边权值和最小,那么称其为最小生成树(可以不唯一)...

    如下图所示,连通图G的某一无环两通子图T若覆盖G中所有的顶点,则称作G的一棵支撑树生成树(spanning tree)。

    其中顶点数为n,其边数为n-1。

    如果其生成树中各边权值和最小,那么称其为最小生成树(可以不唯一)。

     

    实现一 Prim算法

    在图中G=(V;E)中,顶点集V的任一非平凡子集U及其补集V\U都构成G的一个(cut),记作(U:V\U)。若边uv满足u属于U且v不属于U,则称作该割的一条跨越边(crosssing edge)。因此类边联接于V及其补集之间,称作该割为(bridge)。 

    Prim算法就是,每次采用最短的跨越边。 

     

    b> 首先选择A结点作为点集

    c> 找A--B,A--D,A--G权值最小的点(B),之后将其加入点集中

    d> 找点集中跨越边最小的边,A--D,A--G,B--C,到D的权值最小,将其加入到点集中

    e> 重复上述过程,A--G,D--G,D--E,B--C,到G的权值最小,将其加入到点集中

    一直重复上述步骤直到找到的边数为n-1条,i就是通过Prim算法找到的最小生成树了。

    模板

    #include<cstdio>
    #include<cstdlib>
    #include<iostream>
    
    using namespace std;
    /*最小生成树Prim未优化版*/
    
    int book[100];//用于记录这个点有没有被访问过
    int dis[100];//用于记录距离树的距离最短路程
    int MAX = 99999;//边界值
    int maps[100][100];//用于记录所有边的关系
    
    int main()
    {
        int i,j,k;//循环变量
        int n,m;//输入的N个点,和M条边
        int x,y,z;//输入变量
        int min,minIndex;
        int sum=0;//记录最后的答案
        
        cin>>n>>m;
    
        //初始化maps,除了自己到自己是0其他都是边界值
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if(i!=j)
                    maps[i][j] = MAX;
                else
                    maps[i][j] = 0;
            }
        }
                
        for (i = 1; i <= m; i++)
        {
            cin>>x>>y>>z;//输入的为无向图
            maps[x][y] = z;
            maps[y][x] = z;
        }
    
        //初始化距离数组,默认先把离1点最近的找出来放好
        for (i = 1; i <= n; i++)
            dis[i] = maps[1][i];
    
        book[1]=1;//记录1已经被访问过了
    
        for (i = 1; i <= n-1; i++)//1已经访问过了,所以循环n-1次
        {
            min = MAX;//对于最小值赋值,其实这里也应该对minIndex进行赋值,但是我们承认这个图一定有最小生成树而且不存在两条相同的边
            //寻找离树最近的点
            for (j = 1; j <= n; j++)
            {
                if(book[j] ==0 && dis[j] < min)
                {
                    min = dis[j];
                    minIndex = j;
                }
            }
    
            //记录这个点已经被访问过了
            book[minIndex] = 1;
            sum += dis[minIndex];
    
            for (j = 1; j <= n; j++)
            {
                //如果这点没有被访问过,而且这个点到任意一点的距离比现在到树的距离近那么更新
                if(book[j] == 0 && maps[minIndex][j] < dis[j])
                    dis[j] = maps[minIndex][j];
            }
        }
    
        cout<<sum<<endl;
    }
    

     

    实现二 kruskal算法

    先将每条边按照权值的大小非降序的排列,之后按照顺序选取边(不在同一集合),如果两个结点不在同一集合,就将它们合并,直到所有结点在同一集合为止。

    蓝色为放弃的边,因为依次选取时3--4,4--1都为同一个集合,而2--3不为一个集合,所有选择2--3。

    模板

    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #define MAXN 11  //顶点个数的最大值
    #define MAXM 20  //边的个数的最大值
    using namespace std; 
    
    struct edge  //边
    {
        int u, v, w; //边的顶点、权值
    }edges[MAXM]; //边的数组
    
    int parent[MAXN];  //parent[i]为顶点 i 所在集合对应的树中的根结点
    int n, m;  //顶点个数、边的个数
    int i, j;  //循环变量
    void UFset( )  //初始化
    {
        for( i=1; i<=n; i++ ) 
            parent[i] = -1;
    }
    int Find( int x ) //查找并返回节点 x 所属集合的根结点
    {
        int s; //查找位置
        for( s=x; parent[s]>=0; s=parent[s] );
        while( s!=x ) //优化方案―压缩路径,使后续的查找操作加速。
        {
            int tmp = parent[x];
            parent[x] = s;
            x = tmp;
        }
        return s;
    }
    
    //将两个不同集合的元素进行合并,使两个集合中任两个元素都连通
    void Union( int R1, int R2 )
    {
        int r1 = Find(R1), r2 = Find(R2); //r1 为 R1 的根结点,r2 为 R2 的根结点
        int tmp = parent[r1] + parent[r2]; //两个集合结点个数之和(负数)
        //如果 R2 所在树结点个数 > R1 所在树结点个数(注意 parent[r1]是负数)
        if( parent[r1] > parent[r2] ) //优化方案――加权法则
        {
            parent[r1] = r2; 
            parent[r2] = tmp;
        }
        else
        {
            parent[r2] = r1; 
            parent[r1] = tmp;
        }
    }
    bool cmp( edge a, edge b ) //实现从小到大排序的比较函数
    {
        return a.w <= b.w;
    }
    void Kruskal( )
    {
        int sumweight = 0;  //生成树的权值
        int num = 0;  //已选用的边的数目
        int u, v;  //选用边的两个顶点
        UFset( ); //初始化 parent[]数组
        for( i=0; i<m; i++ )
        {
            u = edges[i].u; v = edges[i].v;
            if( Find(u) != Find(v) )
            {
                printf( "%d %d %d\n", u, v, edges[i].w );
                sumweight += edges[i].w; num++;
                Union( u, v );
            }
            if( num>=n-1 ) break;
        }
        printf( "weight of MST is %d\n", sumweight );
    }
    int main( )
    {
        int u, v, w; //边的起点和终点及权值
        scanf( "%d%d", &n, &m ); //读入顶点个数 n
        for( int i=0; i<m; i++ )
        {
        scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
        edges[i].u = u; edges[i].v = v; edges[i].w = w;
        }
        sort(edges,edges+m,cmp);
        Kruskal();
        return 0;
    }

     

    展开全文
  • 文章目录前言、Prim算法(由小树长成大树)(1)思路(2)代码实现二、kruskal算法(合木成林)(1)...用我的理解,就是不断拓展树的大小,用贪心思想,在目前的最小支撑树的邻接点搜索与树相连的边的最小权值,并
  • Prim算法 普里姆算法(Prim算法),图论的一种算法,可在加权连通图里搜索最小生成。意即由此算法搜索到的边子集...此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成的初始形态,在随后的算法执行
  • 概念:设G=(V,E)是一个无向连通图,生成树上各边的权值之和为该生成树的代价,在G的所有生成树,代价最小的生成树就称为最小支撑树,或称最小生成树。 区别:最小生成树是各边权值和最小的数  最优归并树是...
  • 连通图支撑树的常用方法总结

    千次阅读 2015-12-22 09:42:28
    反圈法求支撑树 二避圈法求支撑树 三破圈法求支撑树
  • 两种算法的唯一差别在于,如何选取下一个节点的问题。如果将选取下一节点的策略抽象为获取优先级最高的节点,则对于BFS或是DFS则可统一处理,他们的区别仅在于更新节点的优先级的策略不同而已。根据优先级来遍历,...
  • 首先什么是最小生成树(我的教材称为最小支撑树)?它是一个图的极小连通子图。那什么是?什么是极小连通子图? 是一种数据结构,由顶点集合V(非空)和边集合E构成,记为G=(V,E)。G即Graph,V即Vertex顶点,E...
  • 兔子与星空 题目内容:很久很久以前,森林里住着一群兔子。...第一行只包含一个表示星星个数的数n,n不大于26,并且这n个星星是由大写字母表里的前n个字母表示。接下来的n-1行是由字母表的前n-1个...
  • 7-5 最小支撑树 (10分)

    2021-01-28 15:53:02
    7-5 最小支撑树 (10分) 给定一个包含n个顶点的正权无向,编号为0至n-1。...对于每组数据,若存在最小支撑树则输出一个整数,为最小支撑树各边权值之和;若不存在最小支撑树,则输出“There is no minimum
  • 给定一个包含n个顶点的正权无向,编号为0至n-1。...对于每组数据,若存在最小支撑树则输出一个整数,为最小支撑树各边权值之和;若不存在最小支撑树,则输出“There is no minimum spanning tree.”
  • 7-5 最小支撑树 (10分) 给定一个包含n个顶点的正权无向,编号为0至n-1。...对于每组数据,若存在最小支撑树则输出一个整数,为最小支撑树各边权值之和;若不存在最小支撑树,则输出“There is no minimum
  • 无向连通图的生成树个

    千次阅读 2013-06-24 21:41:22
    对于一个无向连通图来说,它可能有很多生成,那么如何求得它的生成个数呢? 首先给出一个非常一般的计算方法 -- 矩阵行列式法 对于任何一个顶点数为n的无向连通图,我们列出一个矩阵。 矩阵的规则是: ...
  • 的生成最小生成

    万次阅读 多人点赞 2017-11-26 22:37:14
     在一个任意连通图G,如果取它的全部顶点和一部分边构成一个子图G',即:V(G')=V(G)和E(G')⊆E(G)  若同时满足边集E(G')的所有边既能够使全部顶点连通而又不形成任何回路,则称子图G'是原图G的一棵...
  • 最小生成

    2016-08-21 10:05:57
    图G为带权连通图,MST为一个包含G所有顶点及其(|V|-1) 条边(子集)的自由:边权和最小;连通! 应用场景: 怎样使得在几个城市之间建立的电话网(高速公路)所需线路最短? 怎么使连接电路板上一系列接头所需...
  • 给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,并且子集中所有边的权值之和为所有子集中最小的。 本节介绍三种算法求解最小生成:Prim算法...
  • 给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,并且子集中所有边的权值之和为所有子集中最小的。 本节介绍三种算法求解最小生成:Prim算法...
  • 给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,并且子集中所有边的权值之和为所有子集中最小的。 本节介绍三种算法求解最小生成:Prim算法...
  • 亲爱的读者朋友大家晚上好,前两篇文章我们介绍了点集合的直径和连通分量的数量这两问题,这次我们来分析近似最小支撑树,还是照例,我们先来看一下问题的形式化定义。 定义 已知:G=(V,E),ϵ,d=deg(G)G=(V,E),\...
  • 最小生成:Prim算法

    万次阅读 多人点赞 2018-09-17 20:48:08
    生成是指:在一个连通图Graph,包含Graph所有n个顶点的极小连通子图,一定包含Graph的n-1条边(如果小于n-1条边,生成会不连通。如果大于n-1条边,就一定会产生回路,那么就不是了,树中不能产生回路)...
  • 最小生成

    2016-05-04 20:15:52
    简介在一个无向连通图中,如果存在一个连通子图包含原图所有的节点和部分边,且这个子图不存在回路,那么我们称这个子图为原图的一棵生成。在带权图,所有的生成树中边权最小的一课或者几棵称为最小生成。...
  • 理解最小生成与权值最小边无关

    千次阅读 2016-11-21 14:07:45
    理解最小生成与权值最小边无关@(算法学习)驳斥:具有n顶点的有向G的最小生成不唯一,则其权值最小的边一定有多条。有两种最小生成,但是实际上权值最小的边只有条。更简洁的说,最小生成与权值最小的...
  • 1.BFS 优先访问最先发现的节点,可以根据FIFO队列的特点,...等同于结构的层次遍历 //whole graph template <typename Tv, typename Te> void Graph<Tv,Te>::bfs(int s){ reset(); int clock=0...
  • 最小生成详解(模板 + 例题)

    万次阅读 多人点赞 2020-10-15 16:04:26
    作为一个伪ACMer,先来首广为人知的打油诗: 模拟只会猜题意,贪心只能过样例,数学上来先打表,规律一般是DP,组合数学碰运气,计算几何瞎暴力,图论一顿套模板,...如果一个无向连通图不包含回路(连通图中不存在环),.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 791
精华内容 316
关键字:

一个连通图中的最小支撑树