图-克鲁斯卡尔算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了图-克鲁斯卡尔算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1917字，纯文字阅读大概需要3分钟。

内容图文

克鲁斯卡尔算法

#include <iostream>
using namespace std;

typedef char VerTexType;
typedef int ArcType;
#define MVNum 100
#define MaxInt 32767

typedef struct{
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;

struct{
    VerTexType Head;
    VerTexType Tail;
    ArcType lowcost;
}Edge[(MVNum-(MVNum-1))/2];

int Vexset[MVNum];

int loacteVex(AMGraph G,VerTexType v){
    for(int i=0;i<G.vexnum;++i)
        if(G.vexs[i]==v)
            return i;
        return -1;
}

void CreateUDN(AMGraph &G){
    int i,j,k;
    cout<<"请输入总顶点数，总边数，以空格隔开:";
    cin>>G.vexnum>>G.arcnum;
    cout>>endl;

    cout<<"输入点的名称，如a"<<endl;

    for(i=0;i<G.vexnum;++i){
        cout<<"请输入第"<<(i+1)<<"个点的名称:";
        cin>>G.vexs[i];
    }
    cout<<endl;
    for(i=0;i<G.vexnum;++i)
        for(j=0;;j<G.vexnum;++i)
            G.arcs[i][j]=MaxInt;
    cout<<"输入边依附的顶点及权值，如a b 6"<<endl;
    for(k=0;k<G.arcnum;++k){
        VerTexType v1,v2;
        ArcType w;
        cout<<"请输入第"<<(k+1)<<"条边依附的顶点及权值:";
        cin>>v1>>v2>>w;
        i=loacteVex(G,v1);
        j=loacteVex(G,v2);
        G.arcs[i][j]=w;
        G.arcs[j][i]=G.arcs[i][j];
        Edge[k].lowcost=w;
        Edge[k].Head=v1;
        Edge[k].Tail=v2;
    }
}

void Sort(AMGraph G){
    int m=G.arcnum-2;
    int flag=1;
    while((m>0)&&flag==1){
        flag=0;
        for(int j=0;j<=m;j++){
            if(Edge[j].lowcost>Edge[j+1].lowcost){
                flag=1;

                VerTexType temp_Head=Edge[j].Head;
                Edge[j].Head=Edge[j+1].Head;
                Edge[j+1].Head=temp_Head;

                ArcType temp_lowcast=Edge[j].lowcost;
                Edge[j].lowcost=Edge[j+1].lowcost;
                Edge[j+1].lowcost=temp_lowcast;
            }
        }
        --m;
    }
}

void MinSpanTree_Kruskal(AMGraph G){
    int i,j,v1,v2,vs1,vs2;
    Sort(G);
    for(i=0;i<G.vexnum;++i){
        Vexset[i]=i;
    }
    for(i=0;i<G.arcnum;++i){
        v1=loacteVex(G,Edge[i].Head);
        v2=loacteVex(G,Edge[i].Tail);
        vs1=Vexset[v1];
        vs2=Vexset[v2];
        //关键之所在，判断是都构成环
        if(vs1!=vs2){
            cout<<Edge[i].Head<<""<<Edge[i].Tail<<endl;
            //关键之所在，合并后就可以判断是否构成环了
            for(j=0;j<G.vexnum;++i)
                if(Vexset[j]==vs2)
                    Vexset[j]=vs1;
        }
    }
}

void main(){
    cout<<"克鲁斯卡尔算法"<<endl;
    AMGraph G;
    CreateUDN(G);

    cout<<endl;
    cout<<"无向网G创建完成！"<<endl;

    cout<<endl;
    MinSpanTree_Kruskal(G);
}

内容总结

以上是互联网集市为您收集整理的图-克鲁斯卡尔算法全部内容，希望文章能够帮你解决图-克鲁斯卡尔算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---