【算法和數據結構】1.9--圖的最小生成樹之Prim算法（C++實現）

2019-11-06 07:10:34

字體：大中小

來源：轉載

供稿：網友

給定一個圖的數據結構G=(V,E)是一個具有含權邊的連通無向圖，它的一棵生成樹(V,T)是G最為樹的子圖。若(V,T)滿足T的所有邊權值相加為最小值，那么這樣的生成樹稱為最小（耗費）生成樹。

計算一個給定加權連通圖最小生成樹的一個可行方法叫做PRim算法，它是從一個任一頂點開始生長生成樹。其基本步驟如下：

設G=(V,E)，為了方便起見，V取整數集合{1，2，3，……，n}。建立兩個集合X={1}，Y={2，3，……，n}。從頂點1開始生長一棵生成樹，每次一條邊。在每一步（循環）中，找出權值最小的邊（x，y），這里x∈X，y∈Y。然后把y從Y中移至X中，并把這條邊添加到當前最小生成樹邊集T中。當然，T最開始是空的。重復第3~4步，直至Y為空集。此時得到的邊集T即為最小生成樹的所有邊集合。

我們在上一節用鄰接矩陣實現圖的基礎上來實現Prim算法。在上一節的基礎上，添加了輔助類Edge用以表示邊這種數據類型。另外在Graph類的基礎上，添加了成員Edge *m_pEgde用以表示上述T集合。

下面先給出一個連通無向圖的簡單例子，我們將基于這個例子來做測試。這里寫圖片描述

下面先給出代碼實現及測試代碼：

#include<iostream>#include<cstdlib>#include<vector>using namespace std;/*節點類*/class Node{public: Node(char identifier = 0); char m_identifier; //頂點編號 bool m_isVisited; //頂點訪問標志位：true表示已經被訪問};Node::Node(char identifier){ m_identifier = identifier; m_isVisited = false;}/*邊類，用于輔助實現生成最小生成樹*/class Edge{public: Edge(int NodeIndexA = 0, int NodeIndexB = 0, int WeightValue = 0); int m_NodeIndexA, m_NodeIndexB; //邊的兩端點（索引），這里以無向圖為例 int m_weightValue; //邊的權值 bool m_selected; //選擇標志位，true表示已被選擇};Edge::Edge(int NodeIndexA, int NodeIndexB, int WeightValue){ m_NodeIndexA = NodeIndexA; m_NodeIndexB = NodeIndexB; m_weightValue = WeightValue; m_selected = false; //初始時未被選擇}/*圖類*/class Graph{public: Graph(int capacity); ~Graph(); int getGraphSize(); //獲取當前圖的大小 void resetNode(); //重置所有頂點的訪問標志位為false，未訪問 bool addNode(Node *pNode); //添加新頂點 bool addEdgeForUndirectedGraph(int row, int col, int val = 1); //添加邊以構造無向圖，val表示權值，默認權值1 bool addEdgeForDirectedGraph(int row, int col, int val = 1); //添加邊以構造有向圖，val表示權值，默認權值1 void printMatrix(); //打印鄰接矩陣 void depthFirstTraverse(int nodeIndex); //深度優先遍歷，指定第一個點 void widthFirstTraverse(int nodeIndex); //廣度優先遍歷，指定第一個點 void MSTPrim(int nodeIndex); //Prim算法求最小生成樹，指定第一個點private: bool getValueOfEdge(int row, int col, int &val); //獲取邊權值 void widthFirstTraverseImplement(vector<int> preVec); //利用vector實現廣度優先遍歷 int getMinEdge(vector<Edge> edgeVec); //Prim算法輔助函數，用于在邊集中選擇權值最小的邊 int m_iCapacity; //圖容量，即申請的數組空間最多可容納的頂點個數 int m_iNodeCount; //圖的現有頂點個數 Node *m_pNodeArray; //存放頂點的數組 int *m_pMatrix; //為了方便，用一維數組存放鄰接矩陣 Edge *m_pEgde; //邊指針，存儲最小生成樹的邊};Graph::Graph(int capacity){ m_iCapacity = capacity; m_iNodeCount = 0; m_pNodeArray = new Node[m_iCapacity]; m_pMatrix = new int[m_iCapacity*m_iCapacity]; for (int i = 0;i < m_iCapacity*m_iCapacity;i++) //初始化鄰接矩陣 { m_pMatrix[i] = 0; } m_pEgde = new Edge[m_iCapacity - 1]; //最小生成樹節點和邊數量關系}Graph::~Graph(){ delete []m_pNodeArray; delete []m_pMatrix; delete []m_pEgde;}int Graph::getGraphSize(){ return m_iNodeCount;}void Graph::resetNode(){ for (int i = 0;i < m_iNodeCount;i++) { m_pNodeArray[i].m_isVisited = false; }}bool Graph::addNode(Node *pNode){ if (pNode == NULL) return false; m_pNodeArray[m_iNodeCount].m_identifier = pNode->m_identifier; m_iNodeCount++; return true;}bool Graph::addEdgeForUndirectedGraph(int row, int col, int val){ if (row < 0 || row >= m_iCapacity) return false; if (col < 0 || col >= m_iCapacity) return false; m_pMatrix[row*m_iCapacity + col] = val; m_pMatrix[col*m_iCapacity + row] = val; return true;}bool Graph::addEdgeForDirectedGraph(int row, int col, int val){ if (row < 0 || row >= m_iCapacity) return false; if (col < 0 || col >= m_iCapacity) return false; m_pMatrix[row*m_iCapacity + col] = val; return true;}void Graph::printMatrix(){ for (int i = 0;i < m_iCapacity;i++) { for (int k = 0;k < m_iCapacity;k++) cout << m_pMatrix[i*m_iCapacity + k] << " "; cout << endl; }}void Graph::depthFirstTraverse(int nodeIndex){ int value = 0; //訪問第一個頂點 cout << m_pNodeArray[nodeIndex].m_identifier << " "; m_pNodeArray[nodeIndex].m_isVisited = true; //訪問其他頂點 for (int i = 0;i < m_iCapacity;i++) { getValueOfEdge(nodeIndex, i, value); if (value != 0) //當前頂點與指定頂點連通 { if (m_pNodeArray[i].m_isVisited == true) //當前頂點已被訪問 continue; else //當前頂點沒有被訪問，則遞歸 { depthFirstTraverse(i); } } else //沒有與指定頂點連通 { continue; } }}void Graph::widthFirstTraverse(int nodeIndex){ //訪問第一個頂點 cout << m_pNodeArray[nodeIndex].m_identifier << " "; m_pNodeArray[nodeIndex].m_isVisited = true; vector<int> curVec; curVec.push_back(nodeIndex); //將第一個頂點存入一個數組 widthFirstTraverseImplement(curVec);}void Graph::widthFirstTraverseImplement(vector<int> preVec){ int value = 0; vector<int> curVec; //定義數組保存當前層的頂點 for (int j = 0;j < (int)preVec.size();j++) //依次訪問傳入數組中的每個頂點 { for (int i = 0;i < m_iCapacity;i++) //傳入的數組中的頂點是否與其他頂點連接 { getValueOfEdge(preVec[j], i, value); if (value != 0) //連通 { if (m_pNodeArray[i].m_isVisited==true) //已經被訪問 { continue; } else //沒有被訪問則訪問 { cout << m_pNodeArray[i].m_identifier << " "; m_pNodeArray[i].m_isVisited = true; //保存當前點到數組 curVec.push_back(i); } } } } if (curVec.size()==0) //本層次無被訪問的點，則終止 { return; } else { widthFirstTraverseImplement(curVec); }}bool Graph::getValueOfEdge(int row, int col, int &val){ if (row < 0 || row >= m_iCapacity) return false; if (col < 0 || col >= m_iCapacity) return false; val = m_pMatrix[row*m_iCapacity + col]; return true;}void Graph::MSTPrim(int nodeIndex){ int value = 0; //存儲當前邊的權值 int edgeCount = 0; //已選出的邊數量，用以判斷算法終結 vector<int> nodeVec; //存儲點（索引）集的數組 vector<Edge> edgeVec; //存儲邊的數組 cout << m_pNodeArray[nodeIndex].m_identifier << endl; nodeVec.push_back(nodeIndex); m_pNodeArray[nodeIndex].m_isVisited = true; while (edgeCount < m_iCapacity - 1) { int temp = nodeVec.back(); //將當前頂點索引復制給temp for (int i = 0;i < m_iCapacity;i++) //循環判斷每一個頂點與當前頂點連接情況 { getValueOfEdge(temp, i, value); if (value != 0) //連通 { if (m_pNodeArray[i].m_isVisited == true) //已經被訪問 continue; else //未被訪問,則將邊放入被選邊集合 { Edge edge(temp, i, value); edgeVec.push_back(edge); } } } /*選擇最小邊*/ int edgeIndex = getMinEdge(edgeVec); if (edgeIndex == -1) { cout << "獲取最小邊失敗，請重置后再試！" << endl; break; } edgeVec[edgeIndex].m_selected = true; //設置選擇標志位為true，已被選擇 cout << edgeVec[edgeIndex].m_NodeIndexA << "---" << edgeVec[edgeIndex].m_NodeIndexB<<" "; cout << edgeVec[edgeIndex].m_weightValue << endl; m_pEgde[edgeCount] = edgeVec[edgeIndex]; edgeCount++; /*尋找當前選擇的最小邊相連的下一個頂點*/ int nextNodeIndex = edgeVec[edgeIndex].m_NodeIndexB; nodeVec.push_back(nextNodeIndex); m_pNodeArray[nextNodeIndex].m_isVisited = true; cout << m_pNodeArray[nextNodeIndex].m_identifier << endl; } cout << "最小生成樹計算完畢，如上所示！" << endl;}int Graph::getMinEdge(vector<Edge> edgeVec){ int minWeight = 0; //用于輔助選擇最小權值邊 int edgeIndex = 0; //用于存儲最小邊索引 int i = 0; /*找出第一條未被選擇的邊*/ for (;i < (int)edgeVec.size();i++) { if (edgeVec[i].m_selected == false) //當前邊未被選擇 { minWeight = edgeVec[i].m_weightValue; edgeIndex = i; break; } } if (minWeight == 0) //邊集所有邊被訪問 { return -1; } for (;i < (int)edgeVec.size();i++) { if (edgeVec[i].m_selected == true) continue; else { if (minWeight > edgeVec[i].m_weightValue) { minWeight = edgeVec[i].m_weightValue; edgeIndex = i; } } } return edgeIndex;}int main(){ Graph *pGraph = new Graph(6); cout << "初始化頂點中……" << endl; Node *pNodeA = new Node('A'); Node *pNodeB = new Node('B'); Node *pNodeC = new Node('C'); Node *pNodeD = new Node('D'); Node *pNodeE = new Node('E'); Node *pNodeF = new Node('F'); cout << "添加頂點至圖中……" << endl; pGraph->addNode(pNodeA); pGraph->addNode(pNodeB); pGraph->addNode(pNodeC); pGraph->addNode(pNodeD); pGraph->addNode(pNodeE); pGraph->addNode(pNodeF); pGraph->addEdgeForUndirectedGraph(0, 1, 6); pGraph->addEdgeForUndirectedGraph(0, 4, 5); pGraph->addEdgeForUndirectedGraph(0, 5, 1); pGraph->addEdgeForUndirectedGraph(1, 5, 2); pGraph->addEdgeForUndirectedGraph(1, 2, 3); pGraph->addEdgeForUndirectedGraph(2, 5, 8); pGraph->addEdgeForUndirectedGraph(2, 3, 7); pGraph->addEdgeForUndirectedGraph(3, 5, 4); pGraph->addEdgeForUndirectedGraph(3, 4, 2); pGraph->addEdgeForUndirectedGraph(4, 5, 9); cout << "鄰接矩陣如下:" << endl; pGraph->printMatrix(); cout << endl << endl; cout << "深度優先遍歷：" << endl; pGraph->depthFirstTraverse(0); cout << endl << endl; pGraph->resetNode(); cout << "廣度優先遍歷：" << endl; pGraph->widthFirstTraverse(0); cout << endl << endl; pGraph->resetNode(); cout << "最小生成樹為：" << endl; pGraph->MSTPrim(0); cout << endl; system("pause");}

程序運行結果如下：這里寫圖片描述