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

    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)中,顶点集VV的任一子集UU及其补集VUV-U都构成GG的一个割,记作(U:V(U:V-U)U)。若边uuvv满足uUu\in Uv∉Uv\not\in U,则称作该割的一条跨越边。跨越边连接VVVV的补集,故可将其形象地看作该割的一座桥。而Prim算法基于以下事实:最小支撑树总是会采用联结每一割的最短跨越边。

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

    1. U=u0,(u0V),TE={}U={u_0},(u_0\in V),TE=\{\}
    2. 在所有的uU,vVUu\in U,v\in V-U的边(u,v)E(u,v)\in E中找一条代价最小的边(u,v0)(u,v_0)并入集合TETE,同时v0v_0并入UU
    3. 重复2,直到U=VU=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];      
        }
          
    }
    
    展开全文
  • [题目分析]连通图的生成包括图中的全部n顶点和足以使图连通的n-1条边,最小生成是边上权值之和最小的生成。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除条当前权值最大的边后,就去测试...

    [

    题目分析]连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。

    void

    SpnTree (AdjList g)

    //用“破圈法”求解带权连通无向图的一棵最小代价生成树。{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数 node

    edge[];

    scanf( "%d%d",&e,&n) ;

    //输入边数和顶点数。      for (i=1;i<=e;i++)     //输入e条边:顶点,权值。         scanf("%d%d%d" ,&edge[i].i

    ,&edge[i].j ,&edge[i].w);

    for (i=2;i<=e;i++)    //按边上的权值大小,对边进行逆序排序。       {edge[0]=edge[i];

    j=i-1;

    while

    (edge[j].w

    edge[j+1]=edge[j--];edge[j+1]=edge[0]; }//for

    k=1;

    eg=e;

    while (eg>=n)       //破圈,直到边数e=n-1.         {if (connect(k))  //删除第k条边若仍连通。            {edge[k].w=0;

    eg--; }//测试下一条边edge[k],权值置0表示该边被删除k++;  //下条边         }//while

    }//算法结束。

    connect()是测试图是否连通的函数,可用图的遍历实现,若是连通图,一次进入dfs或bfs就可遍历完全部结点,否则,因为删除该边而使原连通图成为两个连通分量时,该边不应删除。前面第17,18题就是测连通分量个数的算法,请参考。“破圈”结束后,可输出edge中w不为0的n-1条边。限于篇幅,这些算法不再写出。

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

    千次阅读 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)思路 最小支撑树总是会采用联结每...


    前言

    树:同时满足极小连通图与极大无环图
    支撑树:能够覆盖图中每一个顶点的树
    最小支撑树:有权网络中满足各边权值之和最小的支撑树

    对于一幅图来说,存在的最小支撑树并不唯一。


    一、Prim算法(由小树长成大树)

    (1)思路

    最小支撑树总是会采用联结每一割的最短跨越边。
    用我的理解,就是不断拓展树的大小,用贪心思想在目前的最小支撑树的邻接点中搜索与树相连的边的最小权值,并将其加入树,之后更新树的邻接点的数据,直到树能够覆盖所有的顶点

    适用于稠密图,O(|V|^2)

    (2)代码实现

    #include<bits/stdc++.h>
    #define MAX 0x3f3f3f;
    using namespace std;
    int sum;
    int n,m;//输入的N个点,和M条边
    int x,y,z;//输入变量
    int i,j,k;//循环变量
    int book[100];//用于记录这个点有没有被访问过
    int dis[100];//用于记录距离树的距离最短路程
    int maps[100][100];//用于记录所有边的关系
    int Prim(){
    	int min,minIndex;
    	//初始化距离数组,默认先把离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;//对于最小值赋值
            for (j = 1; j <= n; j++){//搜索树的邻接点与树相连的边的权最小值及该顶点 
                if(!book[j]&& dis[j] < min)
                {
                    min = dis[j];
                    minIndex = j;
                }
            }
     		//记录这个点已经被访问过了
            book[minIndex] = 1;
            sum += dis[minIndex];
     
            for (j = 1; j <= n; j++){
                //刚刚树增加了一个点,现在把与这个点相连的边的数据更新为更小的权值
    			//通过这一步骤,我们可以在dis里面存入树的邻接点与树相连的边的权值 
                if(book[j] == 0 && maps[minIndex][j] < dis[j])
                    dis[j] = maps[minIndex][j];
            }
        }
    }
    int main(){    
        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;
        }
    //----------------------------------------------------
        
         cout<<Prim()<<endl;
    }
    

    二、kruskal算法(合木成林)

    (1)思路

    贪心思想,每次会在剩余的边中选出权值最小的边,从而构成一棵棵子树,最终合木成林,但对于边的选择却存在要求,边不能属于同一棵子树,否则就形成了环路,不符合树的要求,直至边数等于总顶点数减一,结束检索。

    适用于稀疏图,O(|V|*log|V|)

    (2)代码实现

    #include <bits/stdc++.h>
    using namespace std;
    struct Edge{
        int u;
        int v;
        int w;
    };
    int parent[201];
    //---------------------------------------- 
    bool cmp(Edge e1, Edge e2){//对于结构体内部数据排序所需要 
    	return e1.w < e2.w; 
    }
    //---------------------------------------- 
    int find(int x) {//递归求子树最终根节点 
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]);//更新每个点的最终根节点 
    }
    //---------------------------------------- 
    int merge(int x, int y){//判断是否属于同一棵子树 
        int a = find(x);
        int b = find(y);
        if (a != b) {
            parent[b] = a;
            return 1;
        }
        return 0;
    }
    int main(){
        int n, e;
        while (cin >> n >> e){
            Edge edge[e];
            for (int i = 0; i <e; i++){//进行初始化 
            parent[i] = i;//先保证不同 
        	}
            for (int i = 0; i < e; i++){
                cin>>edge[i].u>>edge[i].v>>edge[i].w;
            }
            sort(edge,edge+e,cmp);
            int cnt = 0, sum = 0;//cnt为树中的边数,sum为树中各边之和 
            for (int i = 0; i < e; i++){
                if (merge(edge[i].u, edge[i].v)){
                    cnt++;
                    sum += edge[i].w;
                }
                if (cnt == n - 1)
                    break;
            }
            if (cnt == n - 1)
                cout << sum << endl;
            else
                cout <<"NO TREE"<< endl;
        }
        return 0;
    }
    
    
    展开全文
  • 程序名称MST_k.m.%这是一个通过避圈法求解连通带权图的最小生成的程序.n=input('请输入的顶点数目:n= ')W=input('请输入的加权邻接矩阵:[W(1,1),..,W(1,n);..;W(n,1),..,W(n,n)]=')%用W(i,i)="inf" 代替 "=0"%...
  • 最小支撑树:对于一个带权网络G,若G的某一无环连通子图能覆盖G中所有的顶点,且其各边的权重总和最低,则称此树为G的最小支撑树。 事实上,在实际生活中的网络架构设计,VLSI布线设计等诸多问...
  • 概念:设G=(V,E)是一个无向连通图,生成树上各边权值之和为该生成树代价,在G所有生成树,代价最小生成树就称为最小支撑树,或称最小生成树。 区别:最小生成树是各边权值和最小数  最优归并树是...
  • 兔子与星空 题目内容:很久很久以前,森林里住着一群兔子。...第一行只包含一个表示星星个数数n,n不大于26,并且这n个星星是由大写字母表里前n个字母表示。接下来n-1行是由字母表前n-1个...
  • 前几节介绍的算法都是针对无权的,本节将介绍带权图的最小支撑树(minimum spanning tree)算法。给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,...
  • 前几节介绍的算法都是针对无权的,本节将介绍带权图的最小支撑树(minimum spanning tree)算法。给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,...
  • 前几节介绍的算法都是针对无权的,本节将介绍带权图的最小支撑树(minimumspanningtree)算法。给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,并且...
  • 若图G=(V,E)生成子图是棵树,则称该树为图G生成树(spanning tree),也称支撑树,简称为图G树。图G属于生成树边称为树枝(branch)。 连通图G=(V,E),每条边上有非负权L(e)。棵树上所有树枝上权...
  • 前几节介绍的算法都是针对无权的,本节将介绍带权图的最小支撑树(minimumspanningtree)算法。给定一个无向G,并且它的每条边均权值,则MST是一个包括G的所有顶点及边的子集的,这个子集保证连通的,并且...
  • 与网络分析

    千次阅读 2015-12-20 22:23:16
    当除去边割后,连通图变为不连通,而除去边割真子集后,连通图仍然连通支撑树如果G=(V,E)支撑子图G’=(V’,E’)是树,称其为G的支撑树,G属于支撑树的边称为树枝,不属于支撑树的边称为弦。 图G有支撑树的
  • 《计算机仿真》期末大作业实现算法MatlabPrim...Matlab连线问题数学模型就是图论连通的赋权上求权最小的支撑树。试用算法(避圈法)。分别实现求最小支撑Prim算法和Krusal.基本要求:画出程序流程...
  • 普利姆算法

    2020-06-26 12:50:45
    简介 上述问题就是最小支撑树的应用。我们可以把七个村庄抽象成图像中的7个顶点,图像之间用边来表示,村庄之间的距离通过权重进行表示。那么应该如何求出把七个村庄...这n-1条边和图的n个顶点构成一个连通图(1) 该
  • 克鲁斯卡尔算法

    2020-07-04 21:46:20
    克鲁斯卡尔算法 问题引入 可以看出,普利姆算法和克鲁斯卡尔算法要解决的问题是同类的的问题。 有几顶点。 顶点之间通过有向边或者无向边连接 ...设连通图为N=(V,E C), T为N的最小支撑树,。初始时,
  • 实用标准文档 计算机仿真期末大作业 Prim 算法和 Kruskal 算法 Matlab 实现 05605 刘禹 ...连线问题数学模型就是图论连通的赋权上求权最小的支撑树 试用 Matlab 分别实现求最小支撑 Prim 算法和 Krus
  • 本题本质上就是让你从给定无向图的所有支撑树中找出边权值之差最小的那个,很像是一个变形BST(最小生成树)问题,然而,BST问题可以通过贪心每次选择权值最小的那条边来解决,可本题不行,并没有类似贪心策略,...
  • 题目要求每节点需要选择条路径将数据发送到root号节点,即要求图中所有节点连通,root节点不用管,没有实际 作用,只需要找出最小支撑树中最大边长即可。 采用Kruskal算法 但不知道到为什么自己测试过了却...
  • 科已经发展成为一个内涵繁杂综合性学科,至少可以划分为计算机工程(CE)、计算机科学(CS)、 信息系统(IS)、信息技术(IT)和软件工程(SE)等五个领域,而且不同领域人才所应具备知 识结构与能力侧重也...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

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