当前位置:   article > 正文

树-生成树-最小生成树_生成树和树

生成树和树

树之

(一).了解

自由树就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根,则成为一棵通常的树)。从根开始,为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序,则它就成为一棵有序树。在图的应用中,我们常常需要求给定图的一个子图,使该子图是一棵树。

(①).生成树:

在图论中,如果连通图  的一个子图是一棵包含 的所有顶点的树,则该子图称为G的生成树(SpanningTree)。

生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得

不同的生成树。

通用定义:

若从图的某顶点出发,可以系统地访问到图中所有顶点,则遍历时经过的边和图的所有顶点所构成的子图,称作

该图的生成树。

(1)若G是强连通的有向图,则从其中任一顶点v出发,都可以访问遍G中的所有顶点,从而得到以v为根的生成树。

(2)若G是有根的有向图,设根为v,则从根v出发可以完成对G的遍历,得到G的以v为根的生成树。

(3)若G是非连通的无向图,则要若干次从外部调用DFS(或BFS)算法,才能完成对G的遍历。每一次外部调用,

只能访问到G的一个连通分量的顶点集,这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。

G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。

(4)若G是非强连通的有向图,且源点又不是有向图的根,则遍历时一般也只能得到该有向图的生成森林。

(②).DFS生成树和BFS生成树

1)生成树的求解方法

设图 n个顶点的连通图。则从G的任一顶点(源点)出发,作一次深度优先搜索

(广度优先搜索),搜索到的n个顶点和搜索过程中从一个已访问过的顶点  搜索到一个未曾访问过的邻接点 

所经过的边 (共n-1条)组成的极小连通子图就是生成树。(源点是生成树的根)通常,由深度优先搜索得到

的生成树称为深度优先生成树,简称为DFS生成树;由广度优先搜索得到的生成树称为广度优先生成树,简称为

BFS生成树。


注意:
①图的广度优先生成树的树高不会超过该图其它生成树的高度
  ②图的生成树不惟一,从不同的顶点出发进行遍历,可以得到不同的生成树。

(③).最小生成树

概念

对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,记作:


其中,TE表示T的边集,w(u,v)表示边(u,v)的权。权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。

最小生成树可简记为MST。

今天着重讲的是最小生成树!!!

一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的

最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。


(二).算法

求最小生成树的算法
(1) 克鲁斯卡尔算法
图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很

实用,浪费时间.
(2) 普里姆算法
图的存贮结构采用邻接矩阵.此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,开始为空集,以后将以连通

的顶点陆续加入到集合中,全部顶点加入集合后就得到所需的最小生成树 .

(①).Kruskal算法

1.Kruskal是一个计算最小生成树的算法,其算法原理如下。首先,将每个顶点放入其自身的数据集合中。然后,按照

权值的升序来选择边。当选择每条边时,判断定义边的顶点是否在不同的数据集中。如果是,将此边插入最小生

树的集合中,同时,将集合中包含每个顶点的联合体取出,如果不是,就移动到下一条边。重复这个过程直到所有

的边都探查过。

1 初始情况,一个联通图,定义针对边的数据结构,包括起点,终点,边长度:

struct _node{

    intval;  //长度
    intstart;//边的起点
    intend;  //边的终点

}Node;
2.先找到第一短的边,将a,e放到同一个集合里面


3 继续找到第二短的边,将cd再放入同一个集合里:

4 继续找,找到第三短的边ab,因为a,e已经在一个集合里,再将b加入:

5 继续找,找到b,e,因为b,e已经同属于一个集合,连起来的话就形成环了,所以边be不加入最小生成树:

6 再找,找到bc,因为c,d是一个集合的,a,b,e是一个集合,所以再合并这两个集合:

这样所有的点都归到一个集合里,生成了最小生成树。

2.先写一下一个基本的能够形成最小生成树能够找到最短路径的Kruskal算法代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 7
using namespace std;
struct Node
{
    int start;
    int endd;
    int leng;
}V[N];
int edge[N][3]={{ 0, 1, 3 },
                    { 0, 4, 1 },
                    { 1, 2, 5 },
                    { 1, 4, 4 },
                    { 2, 3, 2 },
                    { 2, 4, 6 },
                    { 3, 4, 7}
                };
int father[N]={0,};//记录每个点的父结点(属于哪个集合)
int dis[N]={0,};//记录一个集合的长度


int cmp(const void *a,const void *b)//排序用到的cmp()函数
{
    return (*(Node*)a).leng-(*(Node*)b).leng;  //此为升序的方式
}
int find_f(int x)//找寻父结点
{
    if(x!=father[x])
        father[x]=find_f(father[x]);
    return father[x];
}
void Merge(int a,int b)//合并两个集合
{
    int x=find_f(a);
    int y=find_f(b);
    if(x==y)
        return ;
    if(dis[x]<dis[y])
        father[x]=find_f(y);
    else
    {

if(dis[x]==dis[y])
        dis[x]+=dis[y];
        father[y]=find_f(x);
    }
}
int Kruskal()
{
    int counts=0;//记录总的路程;
    for(int i=0;i<N;i++)//初始化集合,让所有的点都各成一个集合,每个集合都只包含自己
    {
        father[i]=i;//记录每个点的父结点
        dis[i]=1;//记录每个边长度
    }
    for(int i=0;i<N;i++)
    {
        if(find_f(V[i].start)!=find_f(V[i].endd))
        {
            Merge(V[i].start,V[i].endd);
            counts+=V[i].leng;
        }
    }
    return counts;
}
int main()
{
    for(int i=0;i<N;i++)//将存储的数据赋值给结构体
    {
        V[i].start=edge[i][0];
        V[i].endd=edge[i][1];
        V[i].leng=edge[i][2];
    }
    qsort(V,N,sizeof(V[0]),cmp);//用qsort()函数先进行升序排序
    printf("%d",Kruskal());
    return 0;
}

3.例题

①.https://vjudge.net/contest/173215#problem/E

题意:

         给你 N 个字符串,求串通他们的最小距离和
每个字符串都只有 7 个字符
        两个字符串的距离就是数出对应位置不同的字符个数
思路:
         把每个字符串看成一个地点,字符串间不同的字符个数看成地点间的距离。套用最小生成树就好了

Kruskal算法代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2001
using namespace std;
char maps[N][10];
int dis[N];
int m,n;
int father[N];
struct Node//建立一个能够表达成一条边的结构体
{
    int start;
    int endd;
    int leng;
}node[N*N/2];
//sort函数的排序函数
int cmp(Node a,Node b)
{
    return a.leng<b.leng;
}
//通过判断不同字母的个数形成这条边的长度
int Get_leng(int x,int y)
{
    int co=0;
    for(int i=0;i<7;i++)
        if(maps[x][i]!=maps[y][i])
            co++;
    return co;
}
//寻找一个点的父结点(这个点所在的集合)
int find_f(int x)
{
    if(x!=father[x])
        father[x]=find_f(father[x]);
    return father[x];
    //return x==father[x]? x:father[x]=find_f(father[x]);//上边的完全可以由这一行代替
}
//合并两个不同的集合
void Merge(int a,int b)
{
    int x=father[a];
    int y=father[b];
    if(x==y)
        return ;
    if(dis[x]>dis[y])
        father[y]=father[x];
    else
    {
        if(dis[x]==dis[y])
            dis[y]++;
        father[x]=father[y];
    }
}
//Kruskal算法
int Kruskal()
{
    int counts=0;
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=0;i<m;i++)
        if(find_f(node[i].start)!=find_f(node[i].endd))//判断这条边是否在同一个集合里面防止成环;
        {
            Merge(node[i].start,node[i].endd);//合并
            counts+=node[i].leng;//将符合条件的边进行加和得到总的路径长度
        }
    return counts;
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",maps[i]);
        m=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                node[m].start=i;
                node[m].endd=j;
                node[m++].leng=Get_leng(i,j);
            }
        sort(node,node+m,cmp);
        printf("The highest possible quality is 1/%d.\n",Kruskal());
    }
    return 0;
}

(②).Prim算法

1.Prim算法是一种产生最小生成树的算法。

Prim算法从任意一个顶点开始,每次选择一个与当前顶点集最近的一个顶点,并将两顶点之间的边加入到树中。Prim算法在找当前最近顶点时使用到了贪婪算法。

算法描述:
1. 在一个加权连通图中,顶点集合V,边集合为E
2. 任意选出一个点作为初始顶点,标记为visit,计算所有与之相连接的点的距离,选择距离最短的,标记visit.
3. 重复以下操作,直到所有点都被标记为visit
在剩下的点钟,计算与已标记visit点距离最小的点,标记visit,证明加入了最小生成树。

下面我们来看一个最小生成树生成的过程:
1 .起初,从顶点a开始生成最小生成树
这里写图片描述
2 .选择顶点a后,顶点啊置成visit(涂黑),计算周围与它连接的点的距离:
这里写图片描述
3. 与之相连的点距离分别为7,6,4,选择C点距离最短,涂黑C,同时将这条边高亮加入最小生成树:
这里写图片描述
4 .计算与a,c相连的点的距离(已经涂黑的点不计算),因为与a相连的已经计算过了,只需要计算与c相连的点,如果一个点与a,c都相连,那么它与a的距离之前已经计算过了,如果它与c的距离更近,则更新距离值,这里计算的是未涂黑的点距离涂黑的点的最近距离,很明显,ba7bc的距离为6,更新b和已访问的点集距离为6,而f,ec的距离分别是8,9,所以还是涂黑b,边bc高亮
这里写图片描述
5. 接下来很明显,d距离b最短,将d涂黑,bd高亮:
这里写图片描述
6. f距离d7,距离b4,更新它的最短距离值是4,所以涂黑f,高亮bf
这里写图片描述
7 .最后只有e了:
这里写图片描述


2.在写一下一个基本的能够形成最小生成树能够找到最短路径的Prim算法代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 10000
using namespace std;
const int N=6;//常量
int index;//存储需要处理的点
int counts;//所求的形成最小生成树的边长加和
bool visit[N];//作为标记点是否被处理的bool类型数组
int dis[N];//记录存储一个点到其他点的距离
int Edge[N][N]={{INF,7,4,INF,INF,INF},   //INF代表两点之间不可达
                    {7,INF,6,2,INF,4},
                    {4,6,INF,INF,9,8},
                    {INF,2,INF,INF,INF,7},
                    {INF,INF,9,INF,INF,1},
                    {INF,4,8,7,1,INF}
                };
int Prim(int cur)
{
    index=cur;
    counts=0;
    printf("%d ",index);//输出第一个点
    memset(visit,0,sizeof(visit[0]));//初始化标记数组
    visit[cur]=1;//表明cur这个点已经被处理了;
    for(int i=0;i<N;i++)
        dis[i]=Edge[cur][i];
    for(int i=1;i<N;i++)//开始找寻另外的N-1个点
    {
        int pos=INF;//只是作为一个比较值
        for(int j=0;j<N;j++)
            if(!visit[j]&&dis[j]<pos)//找到未访问的点中,距离当前最小生成树距离最小的点
            {
                index=j;
                pos=dis[j];
            }
        visit[index]=1;//更新这个点的状态(已经被处理)
        counts+=pos;
        printf("%d ",index);
        for(int j=0;j<N;j++)  //执行更新,如果点距离当前点的距离更近,就更新dis[j];
            if(!visit[j]&&dis[j]>Edge[index][j])
                dis[j]=Edge[index][j];
    }
    printf("\n");
    return counts;//返回最小生成树的总路径值
}
int main()
{
    printf("%d\n",Prim(0));//传递的参数就起始的点
    return 0;
}

3.例题

(①).上面的那个Kruskal算法可以解决的例题https://vjudge.net/contest/173215#problem/E

同样可以用Prim算法解决

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 100000
#define N 2100
using namespace std;
char a[N][10];//由字符串组成的数据
int maps[N][N];    //存储由字符串转换成数字的数
int n;//总的输入多少种情况
int dis[N],visit[N]; //记录一个点到其他点的距离,,标记一个点是否被处理
//将字符转换为两点之间的长度
int Get_l(int x,int y)
{
    int co=0;
    for(int i=0;i<7;i++)
        if(a[x][i]!=a[y][i])
            co++;
    return co;
}
//Prim算法
int Prim()
{
    int counts=0;//记录形成最小生成树走过的总的路径
    int pos;//记录正要处理的点
    int mins;//记录最小的值
    memset(visit,0,sizeof(visit));//初始化标记数组
    for(int i=0;i<n;i++)//初始化未被处理的边
        dis[i]=INF;
    for(int i=1;i<n;i++)//将第一个点所连接的边赋给dis()
        dis[i]=maps[0][i];
    visit[0]=1;
    //Prim算法的基本模式
    for(int i=1;i<n;i++)
    {
        mins=INF;
        for(int j=0;j<n;j++)
        {
            if(!visit[j]&&dis[j]<mins)
            {
                pos=j;
                mins=dis[j];
            }
        }
        visit[pos]=1;
        counts+=mins;
        for(int j=0;j<n;j++)
            if(!visit[j]&&dis[j]>maps[pos][j])
                dis[j]=a[pos][j];
    }
    return counts;
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;i++)
            scanf("%s",a[i]);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                int m=Get_l(i,j);//转换函数
                maps[i][j]=m;
                maps[j][i]=m;
            }
        printf("The highest possible quality is 1/%d.\n",Prim());
    }
    return 0;
}

(三).知识点

并查集

(①).了解

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。

定义:

并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

集就是让每个元素构成一个单元素的集合,也就是按一定顺序将属于同一组的元素所在的集合合并。

主要操作:

①.初始化

把每个点所在集合初始化为其自身。

通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。

②.查找

查找元素所在的集合,即根节点。

③.合并

将两个元素所在的集合合并为一个集合。

通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。

(②).算法

在最小生成树里面只有Kruskal算法用到了并查集;

先是建立数据结构:

struct Node//建立一个能够表达成一条边的结构体
{
    int start;
    int endd;
    int leng;
}node[N*N/2];

明确在Kruskal算法中对并查集的应用:

for(int i=1;i<=n;i++)
        father[i]=i;

 if(find_f(node[i].start)!=find_f(node[i].endd))//判断这条边是否在同一个集合里面防止成环;
        {
            Merge(node[i].start,node[i].endd);//合并
            counts+=node[i].leng;//将符合条件的边进行加和得到总的路径长度
        }

①.初始化

for(int i=1;i<=n;i++)
        father[i]=i;

②.查找

//寻找一个点的父结点(这个点所在的集合)
int find_f(int x)
{
    if(x!=father[x])
        father[x]=find_f(father[x]);
    return father[x];
    //return x==father[x]? x:father[x]=find_f(father[x]);//上边的完全可以由这一行代替
}

③.合并

//合并两个不同的集合
void Merge(int a,int b)
{
    int x=father[a];
    int y=father[b];
    if(x==y)
        return ;
    if(dis[x]>dis[y])
        father[y]=father[x];
    else
    {
        if(dis[x]==dis[y])
            dis[y]++;
        father[x]=father[y];
    }
}


(四).总结:

 Prim算法和Kruskal算法都能从连通图找出最小生成树。区别在于Prim算法是挨个找,而Kruskal是先排序再找。Kruskal算法在效率上要比Prim算法快,因为Kruskal只需要对权重边做一次排序,而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边,但是随着所使用的排序算法的效率的提高,Kruskal算法和Prim算法之间的差异将会清晰的显性出来。



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/820772
推荐阅读
相关标签
  

闽ICP备14008679号