首页 > 代码库 > 最小生成树之克鲁斯卡尔算法

最小生成树之克鲁斯卡尔算法

2024-07-11 11:05:22   222人阅读

克鲁斯卡尔算法：
假设连通网N = {V,{E}},则令最小生成树的初始状态为只有n个顶点而无边的非连通图T = {V,{}}，图中每个顶点自成一个连通分量。在E中选择一个最小代价边，若该边依附的顶点落在T中的不同连通分量上，则将此边加入到T中，否则舍去此边而选择下一条最小代价边【最小生成树不存在环】。依次类推，直至T中所有顶点都在同一连通分量上为止。【连通分量：无向图的极大连通子图】

考虑如下连通图：

用边集数组表示为：


注：这里为了算法方便，将边集数组内容按权值从小到大进行了排序。

下面使用克鲁斯卡尔算法构造最小生成树(对照代码)：
1.初始化辅助数组(parent)：


2.从已经排好序的边集数组中取出第一行数据,分别计算Find（begin）和Find（end），看是否会形成环(m==n)，若不形成环，则输出，并更新辅助数组(parent[n] = m),在这里，find(0) = 0,find(2) = 2
所以将0---2这条边纳入生成树集合:

辅助数组为：


3.第二次循环，会将3---5纳入生成树集合:


辅助数组为：


4.如此再循环两次：


辅助数组：


此时，再准备下次循环时，对应的是边集数组的第四组：


计算find(0)=5,find(3)=5,即m==n,形成了环，所以被舍去!直到遇到边集数组第六组时才不会形成环。最终生成树为：


实现：

/*******************************************
最小生成树之克鲁斯卡尔算法
by Rowandjj
2014/7/9
*******************************************/
#include<iostream>
using namespace std;

#define MAX_VERTEX_NUM 20//最大顶点数

typedef struct _EDGE_
{
    int begin;//起始点序号
    int end;//终点序号
    int weight;//权值
}Edge[MAX_VERTEX_NUM];//边集数组

typedef struct _GRAPH_
{
    Edge edge;//边集数组
    int numVertiexs;//顶点数
    int numEdges;//边数
}Graph;//图存储结构--->边集数组结构

//------------------------------------------
void CreateGraph(Graph* g);//构建有权无向图g
void Display(Graph g);//输出图g的相关信息

int Find(int *parent,int f);
void MiniSpanTree_Kruskal(Graph g);//最小生成树之克鲁斯卡尔算法
//------------------------------------------
void CreateGraph(Graph* g)
{
    int i;

    cout<<"输入顶点数、边数:";
    cin>>g->numVertiexs;
    cin>>g->numEdges;

    cout<<"按权值从小到大顺序输入每条边的两个顶点及权值:"<<endl;
    //初始化边集数组
    for(i = 0; i < g->numEdges; i++)
    {
        cin>>g->edge[i].begin;
        cin>>g->edge[i].end;
        cin>>g->edge[i].weight;
    }
}

void Display(Graph g)
{
    cout<<"顶点数:"<<g.numVertiexs<<" 边数:"<<g.numEdges<<endl;
    cout<<"打印各边信息:"<<endl;
    for(int i = 0; i < g.numEdges; i++)
    {
        cout<<g.edge[i].begin<<"---->"<<g.edge[i].end<<" : "<<g.edge[i].weight<<endl;
    }
}

int Find(int *parent,int f)
{
    while(parent[f] > 0)
    {
        f = parent[f];
    }
    return f;
}

void MiniSpanTree_Kruskal(Graph g)//最小生成树之克鲁斯卡尔算法
{
    int i;
    int m,n;
    int parent[MAX_VERTEX_NUM];//定义辅助数组，用来判断边与边之间是否存在环路
    //1.初始化辅助数组
    for(i = 0; i < g.numVertiexs; i++)
    {
        parent[i] = 0;
    }

    //2.计算最小生成树
    for(i = 0; i < g.numEdges; i++)
    {
        n = Find(parent,g.edge[i].begin);
        m = Find(parent,g.edge[i].end);
        if(n != m)//如果没有形成c环，那么输出
        {
            parent[n] = m;//表示此顶点已经在生成树集合中
            
            cout<<g.edge[i].begin<<"--->"<<g.edge[i].end<<" : "<<g.edge[i].weight<<endl;
        }
    }
}
//------------------------------------------
int main()
{
    Graph g;
    CreateGraph(&g);
    Display(g);

    cout<<"\n最小生成树如下\n"<<endl;
    MiniSpanTree_Kruskal(g);
    return 0;
}
测试：


联系
我们