Prim算法求最小生成树

Prim算法： 采用贪婪算法，通过迭代逐步加入权重最小的边进行构造。

伪代码：

1，初始化U={u₀},E为空集；　　//E是最小生成树的边集合，U是其顶点集合，选定构造最小生成树的出发点u₀；

2，重复以下步骤直到U=V；

2.1 以顶点集U和顶点集V-U之间的所有边作为侯选边，从中寻找权值最小的边(u,v)

2.2 令U=U∪{v}，E=E∪{(u,v)}

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <climits>

using namespace std;

template<class T>
struct GraphNode
{
    bool visited;
    int index;
    int weight;
    T vertexName;
                                                        //自定义优先级：weight小的优先
    friend bool operator<(GraphNode a, GraphNode b) {
        return a.weight > b.weight;
    }
};

template<class T>
class Graph
{
public:
    Graph() {}
    Graph(int * vertexArray, T * nameOfVertex, int numberOfVertex);

    //Prim
    void Prim(int source);

private:
    int vertexNum, arcNum;
    vector<vector<int>>adjacencyMatrix;                    //邻接矩阵
    vector<GraphNode<T>>graphNodeArray;                    //顶点信息，只初始化index和vertexName
};


int main()
{
    const int numofVertex = 7;
    int cost[numofVertex][numofVertex] = {
        { INT_MAX,       12 ,          5 ,      11 ,INT_MAX ,    INT_MAX ,INT_MAX },
        { 12,      INT_MAX ,    INT_MAX ,INT_MAX ,     33 ,    INT_MAX ,INT_MAX },
        { 5,          INT_MAX , INT_MAX ,     21 ,INT_MAX ,      19 ,INT_MAX },
        { 11,      INT_MAX ,      21 ,INT_MAX ,     28 ,       8 ,INT_MAX },
        { INT_MAX,        33, INT_MAX ,     28 ,INT_MAX , INT_MAX ,      6 },
        { INT_MAX, INT_MAX ,      19 ,      8 ,INT_MAX , INT_MAX ,     16 },
        { INT_MAX, INT_MAX , INT_MAX ,INT_MAX ,      6 ,      16 ,INT_MAX }
    };
    //初始化各顶点
    string verName[numofVertex] = { "A","B","C","D","E","F","G" };
    Graph<string>g(*cost, verName, numofVertex);

    cout << "Prim算法执行结果：" << endl;
    try {
        g.Prim(0);
    }
    catch (...) {
        cout << "算法执行失败" << endl;
    }
    system("pause");
    return 0;
}

template<class T>
Graph<T>::Graph(int * vertexArray, T * nameOfVertex, int numberOfVertex)
{
    vertexNum = numberOfVertex;                        //顶点数
    arcNum = 0;
    GraphNode<T> tempgraphNode;
    for (int i = 0; i < vertexNum; i++)
    {
        tempgraphNode.index = i;
        tempgraphNode.vertexName = nameOfVertex[i];
        graphNodeArray.push_back(tempgraphNode);
    }
    //分配所需空间
    adjacencyMatrix.resize(vertexNum, vector<int>(vertexNum));
    for (int i = 0; i < vertexNum; i++)
        for (int j = 0; j < vertexNum; j++)
            adjacencyMatrix[i][j] = *(vertexArray + i*vertexNum + j);
}

template<class T>
void Graph<T>::Prim(int source)
{
    int vertextNum = adjacencyMatrix.size();
    if (source > vertexNum)
        throw"位置";

    vector<int>path(vertexNum);
    priority_queue<GraphNode<T>>queue;
    int minIndex;
    graphNodeArray.resize(vertextNum);                //重置足够空间

    for (int i = 0; i < vertextNum; i++)
    {
        graphNodeArray[i].visited = false;
        graphNodeArray[i].weight = INT_MAX;
        path[i] = source;                            //记录U 集合双亲关系
    }
    graphNodeArray[source].weight = 0;
    queue.push(graphNodeArray[source]);

    while (!queue.empty())
    {
        GraphNode<T> tempGraphNode = queue.top();
        queue.pop();
        if (tempGraphNode.visited)
            continue;
        tempGraphNode.visited = true;
        minIndex = tempGraphNode.index;                //两个集合之间的权值最小边对应的V-U 中顶点的序号
        for(int j=0; j<vertextNum; j++)
                                                    //两个集合之间的权值最小边对应的V-U中的顶点 的关联边入队
            if (j != minIndex && !graphNodeArray[j].visited&&adjacencyMatrix[minIndex][j] < graphNodeArray[j].weight)
            {
                path[j] = minIndex;
                graphNodeArray[j].weight = adjacencyMatrix[minIndex][j];
                queue.push(graphNodeArray[j]);        //边入队，顺便找到其在队中位置
            }
    }
    for (int j = 0; j < vertextNum; j++)
    {
        int priorindex = path[j];
        if (priorindex != j)
            cout << graphNodeArray[priorindex].vertexName << "----" << graphNodeArray[j].vertexName << " ";
    }
    cout << endl;
}

参考前一篇：   Kruskal