chapter §34 求最小生成树----prim算法

思想

对图G(V ,E)设置集合S来存放已经被访问的顶点,然后执行下面两个步骤,共执行n次。
a、每次从集合V-S中选择与集合S最近的一个顶点u(所谓最近,是指集合S中某一顶点v到V-S中的顶点u之间的边权最小,则u作为离S最近的顶点),访问u并加入集合S,同时把这条离集合S最近的边加入最小生成树中。

b、令顶点u作为集合S与集合V-S连接的接口,优化从u能到达的未访问的顶点v与集合S的最短距离。
具体实现:1、类比Dijkstra算法,使用一个bool类型的数组visit[]表示顶点是否已被访问。visit[i]==true表示顶点的Vi已被访问,为false时表示未被访问。
2、令int型数组d[]来存放顶点Vi与集合S的最短距离。初始时除了起点s的d[s]=0,其余顶点用INF来表示不可达。

3、每次从d[]中选则最小的,记录下标为minNum,标记已被访问,并且将d[minNum]累加到sum(边权值之和)中,然后对从minNum出发的所有顶点v,如果使u作为中介点,可以使得d[v]更小。则优化d[v]。

一、基于邻接矩阵

int prim_Matrix() { //默认从0号顶点开始求最小生成树
    fill(d, d + MAX, INF);
    d[0] = 0;
    int sum = 0;//最小生成树边权之和
    for (int i = 0; i < n; ++i) {
        int minNum = -1, minDistance = INF;
        for (int j = 0; j < n; ++j) {
            if (visit[i] == false && d[i] < minDistance) {//选择最小的d[j]
                minNum = i;
                minDistance = d[i];
            }
        }
        if (minNum == -1) return -1;
        visit[minNum] = true;//minNum加入S
        sum += d[minNum];
        for (int v = 0; v < n; ++v) {
            if (visit[v] == false && G[minNum][v] != INF && d[v] > G[minNum][v]) {
                d[v] = G[minNum][v];//更新d[v]
            }
        }
    }
    return sum;
}

二、基于邻接表

struct Node {
    int v, dis;//v为目标顶点,dis为边权
};
vector<Node> Adj[MAX];//邻接表

int prim_Adj() { //默认从0号顶点开始
    fill(d, d + MAX, INF);
    d[0] = 0;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int minNum = -1, minDistance = INF;
        for (int j = 0; j < n; ++j) {
            if (visit[j] == false && d[j] < minDistance) {
                minNum = j;
                minDistance = d[j];
            }
        }
        if (minNum == -1) return -1;
        visit[minNum] = true;
        sum += d[minNum];
        for (int j = 0; j < Adj[minNum].size(); ++j) {
            int v = Adj[minNum][j].v;
            if (visit[v] == false && Adj[minNum][v].dis < d[v])
                d[v] = Adj[minNum][v].dis;
        }
    }
    return sum;
}
上一篇:Effective C++ chapter_5


下一篇:Beyond the Basic Stuff with Python