精华内容
下载资源
问答
  • G中仅含T的一条弦的回路Cr称作对应弦的基本回路,{C1,C2...}这一集合称作对应生成树T的基本回路系统 基本割集 如果图G的某个割集Sr只含有一条树枝,其余边均为弦,则称之为树枝的基本割集,{S1,S2...}为对应T的...

    G为无向连通图,T为G的生成子图且为树,则称T是G的生成树。

    G在T中的边称为树枝,不在的称为弦,T的所有弦的集合的导出子图称为T的余树

    基本回路

    设无向图Gm条边,n个点。T为G的一个生成树

    G中仅含T的一条弦e_{r}的回路Cr称作对应弦e_{r}的基本回路,{C1,C2...C_{m-n+1}}这一集合称作对应生成树T的基本回路系统

    基本割集

    如果图G的某个割集Sr只含有一条树枝e_{r}',其余边均为弦,则称之为树枝e_{r}'的基本割集,{S1,S2...S_{n-1}}为对应T的基本割集系统

    展开全文
  • 一、最小生成树 算法 最小生成树(Minimum Spanning Tree,MST)是在一个给定的无向图G(V,E)中求一棵树T,使得这棵树拥有图G中的所有顶点,且所有边都是来自图G中的边,并且满足整棵树的边权之和最小。 求解最小生成树...

    一、最小生成树

    算法

    最小生成树(Minimum Spanning Tree,MST)是在一个给定的无向图G(V,E)中求一棵树T,使得这棵树拥有图G中的所有顶点,且所有边都是来自图G中的边,并且满足整棵树的边权之和最小。
    求解最小生成树一般有两种算法,即prim算法与kruskal算法。这两个算法都是采用了贪心法的思想,只是贪心的策略不太一样。

    prim算法

    其基本思想是对图G(V,E)设置集合S,存放已被访问的顶点,然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令顶点u为中介点,优化所有从u能到达的顶点v与集合S之间的最短距离。这样的操作执行n次(n为顶点个数),直到集合S已包含所有顶点。可以发现,prim 算法的思想与最短路径中Djkstra算法的思想几乎完全相同,只是在涉及最短距离时使用了集合S代替Dijkstra算法中的起点s。

    代码如下。

    //最小生成树-prim算法
    #include<iostream>
    #define N 105
    #define INF 0x3fffffff
    using namespace std;
    int g[N][N],dis[N];
    bool vis[N];
    void init(int n)
    {
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=INF;
            }
            g[i][i]=0;
            vis[i]=false;
            dis[i]=INF;
        }
    }
    int prim(int s,int n)
    {
        int ans=0;
        dis[s]=0;
        for(int i=1;i<=n;i++){
            int u=-1,MIN=INF;
            for(int j=1;j<=n;j++){
                if(vis[j]==false&&dis[j]<MIN){
                    MIN=dis[j];
                    u=j;
                }
            }
            if(u==-1) return -1;
            vis[u]=true;
            ans+=dis[u];
            for(int v=1;v<=n;v++){
                if(vis[v]==false&&g[u][v]!=INF&&g[u][v]<dis[v]){
                    dis[v]=g[u][v];
                }
            }
        }
        return ans;
    }
    int main()
    {
        int m,n;
        while(cin>>m&&m!=0){
            cin>>n;
            init(n);
            while(m--){
                int a,b,c;
                cin>>a>>b>>c;
                if(g[a][b]>c) g[a][b]=g[b][a]=c;
            }
            int ans=prim(1,n);
            if(ans==-1) cout<<"?\n";
            else cout<<ans<<"\n";
        }
        return 0;
    }
    

    kruskal算法

    从图中不断的选择路径最小的边进行归并,知道包含所有的节点。
    其基本思想为:在初始状态时隐去图中的所有边,这样图中每个顶点都自成一个连通块。之后执行下面的步骤:

    1. 对所有边按边权从小到大进行排序。
    2. 按边权从小到大测试所有边,如果当前测试边所连接的两个顶点不在同一个连通块中,则把这条测试边加入当前最小生成树中;否则,将边舍弃。
    3. 执行步骤2,直到最小生成树中的边数等于总顶点数减1或是测试完所有边时结束。而当结束时如果最小生成树的边数小于总顶点数减1,说明该图不连通。

    代码如下。

    //最小生成树-kruskal算法
    #include<iostream>
    #include<string.h>
    #include<algorithm>
    #define M 105
    #define INF 0x3fffffff
    using namespace std;
    int father[M];
    bool isin[M][M];
    struct  edge{
        int u,v;//边的两个断点
        int cost=0;//花费
    }Edge[M];
    bool cmp(edge e1,edge e2)
    {
        return e1.cost<e2.cost;
    }
    int find(int x)
    {
        if(x==father[x]) return x;
        else{
            return find(father[x]);
        }
    }
    int Kruskal(int n,int cnt)//n为顶点个数,cnt为边的个数
    {
        int ans=0,edge_cnt=0;
        for(int i=1;i<=n;i++) father[i]=i;
        sort(Edge,Edge+cnt,cmp);//从小到大排序
        for(int i=0;i<cnt;i++){
            int fu=find(Edge[i].u);
            int fv=find(Edge[i].v);
            if(fu!=fv){
                father[fv]=fu;
                ans+=Edge[i].cost;
                edge_cnt++;
                if(edge_cnt==n-1) break;
            }
        }
        if(edge_cnt!=n-1) return -1;
        else return ans;
    }
    int main()
    {
        int m,n;
        while(cin>>m&&m!=0){
            cin>>n;
            for(int i=0;i<M;i++)
                for(int j=0;j<M;j++)
                    isin[i][j]=false;
            int cnt=0;
            while(m--){
                int a,b,c;
                cin>>a>>b>>c;
                if(isin[a][b]==false){
                    isin[a][b]=isin[b][a]=true;
                    Edge[cnt].u=a;
                    Edge[cnt].v=b;
                    Edge[cnt].cost=c;
                    cnt++;
                }else{
                    for(int j=0;j<cnt;j++){
                        if(((Edge[j].u==a&&Edge[j].v==b)||(Edge[j].u==b&&Edge[j].v==a))&&Edge[j].cost>c){
                            Edge[j].cost=c;
                            break;
                        }
                    }
                }
            }
            int ans=Kruskal(n,cnt);
            if(ans==-1) cout<<"?\n";
            else cout<<ans<<"\n";
        }
        return 0;
    }
    

    刷题(牛客网-考研复试机试题

    1. 畅通工程
      直接使用prim算法/kruskal算法模板即可。

    2. 继续畅通工程
      同样可以直接使用算法模板,需要注意的是,已修建好的道路将其费用置为0。

    3. Freckles
      直接使用算法模板;需要计算每个节点间的距离;同时需要注意数据的类型。

    二、欧拉回路

    欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。(不需要考虑孤立的节点)

    • 无向图存在欧拉回路:连通,所有节点均为偶度点
    • 有向图存在欧拉回路:连通,节点的入度之和=节点的出度之和
    • 题目:欧拉回路
      代码如下。
    #include<iostream>
    #define N 1005
    using namespace std;
    bool g[N][N];
    int fa[N],d[N];
    void init(int n)
    {
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=false;
            }
            fa[i]=i;
            g[i][i]=true;
            d[i]=0;
        }
    }
    int find(int x)
    {
        if(x==fa[x]) return x;
        else return find(fa[x]);
    }
    bool solute(int n)
    {
        //判断是否是连通,使用并查集
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(g[i][j]){
                    int f1=find(i);
                    int f2=find(j);
                    if(f1!=f2){
                        fa[f1]=f2;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
            if(fa[i]==i&&d[i]) //不考虑孤立的点
               cnt++;
        if(cnt!=1) return false;
        //判断所有节点是否为偶度节点
        for(int i=1;i<=n;i++){
            if(d[i]%2) return false;
        }
        return true;
    }
    int main()
    {
        int n,m;
        while(cin>>n&&n!=0){
            cin>>m;
            init(n);
            while(m-->0){
                int a,b;
                cin>>a>>b;
                g[a][b]=g[b][a]=true;
                if(a!=b){
                    d[a]++;
                    d[b]++;
                }
            }
            bool f=solute(n);
            if(f) cout<<"1\n";
            else cout<<"0\n";
        }
        return 0;
    }
    

    三、树的判断

    什么是树?在无环的情况下,根节点的入度为0,其余节点的入度为1。

    题目:Is It a Tree?

    这道题的关键在于如何判断是否存在环,可以使用并查集进行判断。

    代码如下。

    #include<iostream>
    #define N 10005
    using namespace std;
    bool isnode[N];
    int fa[N];
    void init()
    {
        for(int i=0;i<N;i++){
            isnode[i]=false;
            fa[i]=i;
        }
    }
    int find(int x)
    {
        if(x==fa[x]) return x;
        else return find(fa[x]);
    }
    //只有根结点的入度为0,其余为1;
    int main()
    {
        int s,e,k=0;
        bool flag=true;
        init();
        while(cin>>s>>e){
            if(s==-1&&e==-1) break;
            if(s==0&&e==0){//输入处理
                k++;
                bool f=false;
                int cnt=0;
                for(int i=0;i<N;i++){
                    if(isnode[i]) f=true;
                    if(isnode[i]&&fa[i]==i) cnt++;
                }
                if(f==false) cout<<"Case "<<k<<" is a tree.\n";
                else if(cnt==1&&flag) cout<<"Case "<<k<<" is a tree.\n";
                else cout<<"Case "<<k<<" is not a tree.\n";
                //初始化
                flag=true;
                init();
            }else{
                isnode[s]=true;
                isnode[e]=true;
                int f1=find(s);
                int f2=find(e);
                if(fa[e]!=e&&fa[e]!=s) {
                    flag=false;        //说明入度大于1
                    continue;
                }
                if(f1==f2) flag=false;  //有环
                else fa[e]=s;
            }
        }
        return 0;
    }
    

    文章参考胡凡的《算法笔记》。

    展开全文
  • 树之 (一).了解 自由树就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根,则成为一棵通常的树)。...在图论中,如果连通图 的一个子图是一棵包含 的所有顶点的树,则该子图称为G的生成树(SpanningTr

    树之

    (一).了解

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

    (①).生成树:

    在图论中,如果连通图  的一个子图是一棵包含 的所有顶点的树,则该子图称为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算法之间的差异将会清晰的显性出来。



    展开全文
  • 生成树与最小生成树

    2018-04-02 10:54:00
    生成树是对图遍历访问的一条无回路的遍历路径称为图的生成树,生成树不是唯一的,深度优先和广度优先的访问路径就是一棵生成树.深度优先搜索与广度优先搜索的生成树分别称为***, 最小生成树 最小生成树是对带有...
  • ) new_graph.show(file_name="Prim最小生成树") def min_span_tree_by_kruskal(self): """ 最小生成树 寻找最小权重的边加到图中 条件就是 不能形成环,直到所有节点都被连接停止 未使用 Find/Join 模型 :return: ...
  • 图的生成树和最小生成树

    万次阅读 多人点赞 2017-11-26 22:37:14
     若同时满足边集E(G')中的所有边既能够使全部顶点连通而又不形成任何回路,则称子图G'是原图G的一棵生成树。  下面简单说明一下,在既能够连通图G中的全部n个顶点又没有形成回路的子图G'(即
  • 最小生成树

    2019-06-20 06:59:23
    文章目录最小生成树构造实验目的实验内容与要求源程序示例结果 最小生成树构造 实验目的 熟悉最小生成树的构造算法,掌握最小生成树的构造过程。 实验内容与要求 定义1 设T是一个连通且回路的无向图,则称T为无向...
  • 称所有基本回路的集合为对应生成树T的基本回路系统。 求基本回路的算法 设弦e=(u,v),先求T中u到v的路径,再加上弦e。 例如 基本割集与基本割集系统 定义 设T是连通图G的一颗生成树,对T的每一条树枝a,存在唯一的...
  • 生成树

    2019-09-21 06:18:55
    生成树专题 cover by 一堆大佬的博客 百度百科等#%¥%~ 反正不是我写的 首先 让我们先了解一下生成树的概念 生成树 在图论中,如果连通图 的一个子图是一棵包含 的所有顶点的树,则该子图称为G的生成树(Spanning...
  • 最小生成树 定义 最小生成树,是在一个n点边的强连通无向图中,边权值之和最小的n点n-1条边的强连通量(树),一般情况下可以与并查集同解,常见的使用prim和kruskal。 性质 MST性质:设G=(V,E)是一个连通网络...
  • 学习这部分内容首先要学习图这种数据类型的基本知识 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 好了话不多说 概念:...
  • 一个图可以可能对应多个最小生成树 最小生成树的权值唯一。虽然树不唯一,当是他们的权值一定是唯一的,且是最小的。 最小生成树的边数等于顶点数减1。这是树的性质 带全图ADT及其实现 public interface WeightedGr
  • 9.3 最小生成树算法

    2021-02-12 21:30:07
    产生最小生成树必须解决下边两个问题:(1) 尽可能选取权值小的边,但不能构成回路;(2) 选取n-1条恰当的边以连通n个顶点。 最小生成树的算法主要有Kruskal算法和Prim算法,他们都是贪心算法的应用。 最小生成树的...
  • 最小生成树 Prim

    2020-08-31 00:43:05
    最小生成树 Minimum Spanning Tree 最小生成树首先是一棵树 ...一个图若存在对应的最小生成树,则此图为连通图,反之也成立 Prim算法 Prim算法的思路是:从一个根节点开始,让这棵小树慢慢长大 ...
  • 最小生成树的构造

    千次阅读 2019-11-06 16:13:18
    最小生成树 树也是图的一个特例 什么是生成树? 连通图的生成树是包含全部顶点的一个极小连通子图,即此树包含图中所有的顶点,并且只含尽可能少的边,此树还是连通 一个图的生成树不只一个,权(各边权值之和)最小的...
  • 最小生成树算法

    2021-01-16 19:54:34
    最小生成树算法最小生成树Prim算法 最小生成树       一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边,对于加权图...
  • 关于最小生成树问题

    千次阅读 2014-06-22 09:51:24
    我们通过一个例子来看一下最小生成树的qiuf
  • 图的应用——最小生成树

    千次阅读 2019-12-30 14:25:02
    最小生成树求最小生成树构造最小生成树的准则贪心算法(Greedy Algorithm)Prim(普里姆)算法算法思想 —— 归并顶点算法设计KrusKal(克鲁斯卡尔)算法算法思想 —— 归并边算法设计Prim和KrusKal比较 最小生成树 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,049
精华内容 2,419
关键字:

对应生成树的基本回路