Prim 算法: 采用贪婪算法, 通过迭代逐步加入权重最小的边进行构造.
伪代码:
1, 初始化 U={u0},E 为空集; //E 是最小生成树的边集合, U 是其顶点集合, 选定构造最小生成树的出发点 u0;
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
来源: http://www.bubuko.com/infodetail-3336393.html