最小生成树(Kruskal 算法和 Prim 算法)——贪心算法(C语言)

2018年9月12日 2点热度 0条评论 来源: 空杯的境界

  本内容将介绍 最小生成树(MST:Minimum Cost Spanning Tree) 的两种解法,分别为 Kruskal 算法(克鲁斯卡尔算法)Prim 算法(普里姆算法),并且它们都属于贪心算法

问题描述:
  产生最小生成树(MST:Minimum Cost Spanning Tree)

一、Kruskal算法

解题思路:

  1. 排序(按照边的权重,从小到大排序)。
  2. 从还没有加入到生成树中所有边中选出最小的边。然后检查加入这条边后,是否会形成环。如果没有形成环,将这条边进入生成树;否则,丢弃它。
  3. 重复第 2 步,直到遍历完所有边或者产生了最小生成树。

算法描述:

  1. 选择一种排序算法进行排序。
  2. 因为第 1 步我们已经按照边的权重已经从小到大进行排序了,所以我们可以使用一个循环,遍历所有的边。其中,如何检查是否形成环的方法:即新加入的边的两个顶点的 parent 是否相同。

代码实现:

#include <stdio.h>

#define VER_LEN (101)
#define EDGE_LEN (10001)

typedef struct { 
    int u, v;
    int cost;
} edge;

edge Edge[EDGE_LEN];
int Parent[VER_LEN];
int Size[VER_LEN];
int Flag[VER_LEN];

// 排序,按照边的权重,从小到大排序
void sort(int edge_num) { 
    int i, j;
    int temp_u, temp_v, temp_cost;

    for(i = 1; i < edge_num; i++) { 
        for(j = 1; j <= edge_num - i; j++) { 
            if(Edge[j].cost > Edge[j+1].cost) { 
                temp_u = Edge[j].u;
                temp_v = Edge[j].v;
                temp_cost = Edge[j].cost;
                Edge[j].u = Edge[j+1].u;
                Edge[j].v = Edge[j+1].v;
                Edge[j].cost = Edge[j+1].cost;
                Edge[j+1].u = temp_u;
                Edge[j+1].v = temp_v;
                Edge[j+1].cost = temp_cost;
            }
        }
    }
}

void init(int ver_num) { 
    int i;

    for(i = 1; i <= ver_num; i++) { 
         // 将parent初始化为自身
        Parent[i] = i;
         // 将size初始化为1,用于按秩压缩(如果不需要进行按秩压缩,不需要这个数组信息)
        Size[i] = 1;
    }
}

int find(int vertex) { 
    if(vertex != Parent[vertex]) { 
        Parent[vertex] = find(Parent[vertex]); // 路径压缩
    }

    return Parent[vertex];
}

int union_set(int i) { 
    int parent_u = find(Edge[i].u);
    int parent_v = find(Edge[i].v);

    // 节点u和v已经在同一颗树上了
    if(parent_u == parent_v) { 
        return 0;
    }

    // 按秩压缩,将秩小一些的树加入到秩大一些的树
    if(Size[parent_u] > Size[parent_v]) { 
        Parent[parent_v] = parent_u;
        Size[parent_u] += Size[parent_v];
    } else { 
        Parent[parent_u] = parent_v;
        Size[parent_v] += Size[parent_u];
    }
    return 1;
}

void Kruskal(int ver_num, int edge_num) { 
    int i;
    int counter;

    // 排序,按照边的权重,从小到大排序
    sort(edge_num);

    // 进行初始化
    init(ver_num);

    counter = 0;
    // 按照边的权重,从小到大遍历所有的边
    // 直到编译完所有边,或者生成了最小生成树为止
    for(i = 1; i <= edge_num && counter < ver_num-1; i++) { 
        // 当新加入的边会形成环时,需要舍弃
        if(union_set(i) == 0) { 
            continue;
        }

        // 将新加入的边的编号保存在Flag数组中,以便输入
        counter++;
        Flag[counter] = i;
    }
}

int main() { 
    int i;
    int ver_num, edge_num;

    freopen("input.txt", "r", stdin);

    scanf("%d %d", &ver_num, &edge_num);
    for(i = 1; i <= edge_num; i++) { 
        scanf("%d %d %d", &Edge[i].u, &Edge[i].v, &Edge[i].cost);
    }

    Kruskal(ver_num, edge_num);

    for(i = 1; i < ver_num; i++) { 
        printf("%d to %d\n", Edge[Flag[i]].u, Edge[Flag[i]].v);
    }

    return 0;
}

二、Prim 算法

解题思路:
  假设 G = ( V , E ) G = (V,E) G=(V,E) 是连通图, T E TE TE G G G 上最小生成树中边的集合。算法从 U = U 0 U = {U_0} U=U0 U 0 U_0 U0 属于 V V V), T E = { } TE = \{\} TE={ }开始。

  1. 将所有顶点 V i V_i Vi { V i V_i Vi 属于 V − U V-U VU,即不在最小生成树中的顶点} 到最小生成树的权重进行更新(即保存最小值)。
  2. 然后选出最小权重的那条边,并将这个顶点加入到 U U U 中(即最小生成树)。
  3. 重复第 1 步和第 2 步,直到 U = V U = V U=V

算法描述:

  1. 任意选出一个顶点加入到 U U U 中作为初始顶点,然后将这个初始顶点到顶点 V i V_i Vi { V i V_i Vi 属于 V − U V-U VU,即不在最小生成树中的顶点} 的权重作为各个顶点的 cost 值
  2. 然后选出 cost 值最小的那个顶点,并将其加入到 U U U 中。
  3. 根据第 2 步新加入的顶点,调整顶点 V i V_i Vi { V i V_i Vi 属于 V − U V-U VU,即不在最小生成树中的顶点} 的 cost 值。
  4. 重复第 2 步和第 3 步,直到产生最小生成树。

代码实现:

#include <stdio.h>

#define MAXINT (0X7FFF7FFF)
#define VER_LEN (101)

typedef struct { 
    int cost;
    int flag;
    int pre;
} vertex;

int Graph[VER_LEN][VER_LEN];
vertex Vertex[VER_LEN];

// 初始化图的数据,初始化为两点之间互不连接
void init_graph(int length) { 
    int i, j;

    for(i = 1; i <= length; i++) { 
        for(j = 1; j <= length; j++) { 
            Graph[i][j] = MAXINT;
        }
    }
}

void prim(int start, int length) { 
    int i, j;
    int min_cost, min_v;

    // 根据初始顶点start,初始为各顶点的相关信息
    // cost表示权重,flag表示是否已经加入最小生成树,pre表示其parent节点
    for(i = 1; i <= length; i++) { 
        Vertex[i].cost = Graph[start][i];
        Vertex[i].flag = 0;
        Vertex[i].pre = start;
    }

    // 将初始顶点加入到最小生成树中
    Vertex[start].cost = 0;
    Vertex[start].flag = 1;

    for(i = 2; i <= length; i++) { 
        min_cost = MAXINT;
        // 找出cost最小的边
        for(j = 1; j <= length; j++) { 
            if(Vertex[j].flag == 0 && Vertex[j].cost < min_cost) { 
                min_cost = Vertex[j].cost;
                min_v = j;
            }
        }

        // 将上面找出来的cost最小的边的顶点加入到最小生成树中
        Vertex[min_v].flag = 1;

        // 根据上面新加入到最小生成树的顶点调整各顶点的cost值
        for(j = 1; j <= length; j++) { 
            if(Vertex[j].flag == 0 && Vertex[j].cost > Graph[min_v][j]) { 
                Vertex[j].cost = Graph[min_v][j];
                Vertex[j].pre = min_v;
            }
        }
    }
}

int main() { 
    int i;
    int ver_num, edge_num;
    int edge_u, edge_v, cost;

    freopen("input.txt", "r", stdin);

    scanf("%d %d", &ver_num, &edge_num);
    init_graph(ver_num);

    for(i = 1; i <= edge_num; i++) { 
        scanf("%d %d %d", &edge_u, &edge_v, &cost);
        Graph[edge_u][edge_v] = cost;
        Graph[edge_v][edge_u] = cost;
    }

    prim(1, ver_num);

    for(i = 2; i <= ver_num; i++) { 
        printf("%d to %d, the cost is %d\n", Vertex[i].pre, i, Vertex[i].cost);
    }

    return 0;
}
    原文作者:空杯的境界
    原文地址: https://blog.csdn.net/benzhujie1245com/article/details/82663201
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。