lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

Prim算法

Posted on 2009-04-10 19:11 lzmagic 阅读(4334) 评论(1)  编辑 收藏 引用 所属分类: Algorithm
/**
 * PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree) 
 * 输入：图g；                 // 有向图或者无向图 
 * 输出：(1)最小生成树长sum； 
 *         (2)最小生成树prev。
 * 结构: 图g用邻接矩阵表示，最短边长dist用数组表示。 
 * 算法：Prim算法  
 * 复杂度：O(|V|^2) 
 */ 
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;                    // n : 顶点个数 
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示) 
vector<bool> known;        // known : 各点是否已经选取 
vector<int> dist;        // dist : 已选取点集到未选取点的最小边长 
vector<int> prev;        // prev : 最小生成树中各点的前一顶点
int s;                    // s : 起点(start) 
int sum;                // sum : 最小生成树长 

bool Prim()                // 贪心算法(Greedy Algorithm) 
{
    known.assign(n, false);
    dist.assign(n, INT_MAX);
    prev.resize(n);            // 初始化known、dist、prev。 
    dist[s] = 0;            // 初始化起点到自身的路径长为0。
    int i; 
    for (i = 0; i < n; ++i)
    {
        int min = INT_MAX, v;
        for (int i = 0; i < n; ++i)
            if (!known[i] && min > dist[i])
                min = dist[i], v = i;    // 寻找未知的最短路径长的顶点v， 
        if (min == INT_MAX) break;        // 如果找不到，退出； 
        known[v] = true;                // 如果找到，将顶点v设为已知，
        sum += dist[v];                 // 调整最小生成树长 
        for (int w = 0; w < n; ++w)        // 遍历所有v指向的顶点w， 
            if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
                dist[w] = g[v][w], prev[w] = v;    // 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。 
    }
    return i == n; // 如果选取顶点个数为n，成功。 
}

int main()
{
    n = 7;
    g.assign(n, vector<int>(n, INT_MAX));
    g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4;   g[0][3] = g[3][0] = 1;
    g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
    g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
    g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
    g[4][6] = g[6][4] = 6;
    g[5][6] = g[6][5] = 1; 
    
    s = 0;        // 起点任选 
    sum = 0;
    if (Prim())
    {
        cout << sum << endl;
        for (int i = 1; i < n; ++i)
            if(i != s) cout << prev[i] << "->" << i << endl;
    }
    else
    {
        cout << "Some vertex cann't be reached." << endl; 
    }
    
    system("pause");
    return 0;
}

Feedback

# re: Prim算法  回复  更多评论   

2009-04-15 12:52 by brightcoder
good!~

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理