数据结构与算法：最小生成树

最小生成树的概念

最小生成树，即构造连通网的总代价（总权值）最小的树为最小生成树。

最小生成树的一些性质：

1. 最小生成树一定是连通的。
2. 如果去掉某条边，则最小生成树就不再连通。
3. 最小生成树的边数一定等于顶点数减1。
4. 一个连通图可以有多个生成树。
5. 生成树中不存在环。
6. 对于包含n个顶点的连通图，其最小生成树包含n-1条边。
7. 对于包含n个顶点的完全无向图，最多包含n^(n-2)条边。

最小生成树的算法

普里姆算法

思路

我们将顶点分为两类，一类为A，另一类为B，其中A类表示已经加入最小生成树的顶点，B类表示尚未加入最小生成树的顶点。
我们每次都从B类中寻找一个顶点加入A类并使得A类中得顶点权值之和最小，这样我们就可以得到一个最小生成树。
为了实现上述思路，我们使用邻接表，并且还需要一个辅助空间dist来挑选权值最小的顶点。

代码实现

定义如下数据结构：
令最大顶点数为10
Edge表示边表，Vertex为相连的顶点，Weight为权值
Graph表示图，其中Vertex为顶点，Edge为边表指针
G图，下标为顶点
dist为辅助数组,用于记录最短的距离
Visited为辅助数组，如果顶点在A中则标为1，否则为0
Tree用来存放结果

#define MaxVertexNum 10
#define INF 2^31-1
struct Edge
{
    int Vertex;
    int Weight;
};

struct Graph
{
    int Vertex;
    int* Edge;
};

Graph G[MaxVertexNum];
int dist[MaxVertexNum]={INF};
bool Visted[MaxVertexNum]={false};

struct Tree
{
    int Begin;
    int End;
    int Weight;
};
Tree T[MaxVertexNum-1];

算法实现

void Prime(MGraph& G)
{
    Visited[0]=1; //先把第一个顶点加入到A类中
    int count=0;

    while(count!=MaxVertexNum-1){
        //寻找最小距离
        int Min=INF;
        for(int i=0;i<MaxVertexNum;i++){          
            for(int j=0;j<G[i].size();j++){
                if(Visited[G[i][j].Vertex]==false){
                    dist[G[i][j].Vertex]=G[i][j].Weight;
                    Min=min(Min,G[i][j].Weight);
                }               
            }        
        }
        //将最小距离加入到树中
        for(int j=0;j<G[i].size();j++){
            if(dist[j]==Min && Visited[j]==false){
                Visited[j]=true;
                T[count].Begin=i;
                T[count].End=G[i][j].Vertex;
                T[count].Weight=Min;
                count++;
                break;
            }
        }
    }
}

克鲁斯卡尔算法

思路

采用贪心策略，我们每次都挑选一个权值最小的边放入生成树中并检查是否成环，知道所有节点都加入生成树中。
这里使用边集数组来表示图，并在构建图时按权值递增构建或使用sort进行排序。
如何检测有环生成：定义一个终点数组，下标为起始点，值为终点，为INF表示没有节点相连，每次都在这个数组例查询终点，若指向数组中的同一个位置，则说明有环（并查集）。

代码实现

定义如下结构:
最大定点数
边集数组
结果数组
终点数组，下标对应顶点，值对应终点

#define MaxVertexNum 10
#definde MaxEdgeNum 15
#define INF 2^21-1
struct Graph
{
    int Begin;
    int End;
    int Weight;
};

struct Tree
{
    int Begin;
    int End;
    int Weight;
};

Graph G[MaxEdgeNum];
Tree T[MaxVertexNum-1];
int EndArray[MaxVertexNum]={INF};

算法实现

int Get(int cur)
{
    while(EndArray[cur]!=INF){
        cur=EndArray[cur];
    }

    return cur;
}

void Kruskal(MGraph& G)
{
    //假设图的权值是递增的
    int count=0;
    int i=0,j=0;
    int EdgeNum=0;
    while(EdgeNum<MaxVertexNum-1){
        if(Get(G[count].Begin)==Get(G[count].End)){
            count++;
            continue;
        }else{
            T[EdgeNum].Begin=G[count].Begin;
            T[EdgeNum].End=G[count].End;
            T[EdgeNum].Weight=G[count].Weight;
            EdgeNum++;
            EndArray[Get(G[count].Begin)]=G[count].End;
            count++;
        }        
    }
}

• 本文作者： KongXinQing
• 本文链接： https://13114987559.github.io/2023/09/09/note/数据结构与算法-最小生成树/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！