C++

C++ – Minimum spanning tree

_Redstone_c_

definition

  1. Connected graph: Any two vertices vi and vj are connected by a path.
  2. Strongly connected graph: any two vertices vi and vj are connected by paths.
  3. Connected graph: The edges of the graph have a certain meaning, and each change has a corresponding weight.
  4. Spanning tree: The spanning tree of a connected graph refers to a connected subgraph, which contains all n vertices in the graph.
  5. Minimum spanning tree: Establish a spanning tree with the least amount of weight.

PS: If another edge is added to the spanning tree, it will definitely form a loop.

The minimum spanning tree can be found using Kruskal's algorithm or Prim's algorithm.

Greedy algorithm:

Every step should be the best, the edge with the smallest weight.

Required constraints:

  1. Smart use of edges that exist in the graph.
  2. Intelligence uses exactly |v|-1 edges.
  3. There can be no loops.

Kruskal algorithm

This algorithm can be called the "edge addition method". The initial number of minimum spanning tree edges is 0. Each iteration selects a minimum cost edge that meets the conditions and adds it to the edge set of the minimum spanning tree.

  1. Sort all the edges in the graph from small to large in cost.
  2. Think of the n vertices in the graph as a forest composed of n independent trees.
  3. Select edges from small to large weights. If the two vertices ui and vi connected by the selected edge belong to two different trees, they will become an edge of the minimum spanning tree, and the two trees will be merged into one tree. .
  4. Repeat [3] until all vertices are in a tree or there are n-1 edges.

pseudocode

void Kruskal(Graph G) {
    MST = {};
    while(MST中不到|V|-1条边&&E中还有边) {
        从E中取一条权重最小的边E(V,W);
        将E(V,W)从E中删除;
        if(E(V,W)不在MST中构成回路)
            将E(V,W)加入MST;
        else
            彻底无视E(V,W);
    }
    if(MST中不到|V|-1条边)
        Error(生成树不存在);
}

T = O(|E|log|E|)

full code

int ans;
int fat[MAXN];
int tfind(int n) {
    if(fat[n] != n) fat[n] = tfind(fat[n]);
    return fat[n];
}
void kruskal() {
    ans = 0;
    sort(edge, edge + tot);
    for(int i = 0; i < n; i++) fat[i] = i;
    for(int i = 0; i < tot; i++) {
        if(tfind(edge[i].u) != tfind(edge[i].v)) {
            ans += edge[i].w;
            fat[tfind(edge[i].u)] = tfind(edge[i].v);
        }
    }
}

Prim's algorithm

This algorithm can be called the "adding point method". Each iteration selects the point corresponding to the edge with the lowest cost and adds it to the minimum spanning tree.

The algorithm starts from a certain vertex s and gradually reaches all vertices covering the entire connected network.

  1. The set of all vertices of the graph is V; initially let the set u={s},v=V−u.
  2. Among the edges that can be formed by two sets u and v, select the edge with the smallest cost (u0, v0), add it to the minimum spanning tree, and merge v0 into the set u.
  3. Repeat the above steps until the minimum spanning tree has n-1 edges or n vertices.

pseudocode

void Prim() {
    MST = {s};
    while(true) {
        V = 未收录顶点中dist最小者;
        if(这样的V不存在)
            break;
        将V收录进MST：dist[V] = 0;
        for(V的每个邻接点W)
            if(dist[W]!=0)
                if(E(v,w) < dist[W]) {
                    dist[W] = E(v,w);
                    parent[W] = V;
                }
    }
    if(MST中收的顶点不到|V|个)
        Error(生成树不存在);
}

T=O(|V|2)

full code

int ans;
bool vis[MAXN];
int dis[MAXN];
void prim() {
    memset(vis, false, sizeof vis);
    memset(dis, INF, sizeof dis);
    for(int i = head[0]; ~i; i = edge[i].nxt)
        if(dis[edge[i].v] > edge[i].w)
            dis[edge[i].v] = edge[i].w;\
    vis[0] = true;
    ans = 0;
    while(true) {
        int k = 0;
        int minn = INF;
        for(int i = 0; i < n; i++) {
            if(!vis[i] && dis[i] < minn) {
                minn = dis[i];
                k = i;
            }
        }
        if(minn == INF) return;
        vis[k] = true;
        ans += dis[k];
        dis[k] = 0;
        for(int i = head[k]; ~i; i = edge[i].nxt)
            if(!vis[edge[i].v] && dis[edge[i].v] > edge[i].w)
                dis[edge[i].v] = edge[i].w;
    }
}

Post Reply