在前面兩節(jié)圖和圖的最小生成樹之PRim算法的基礎(chǔ)上，這里給出另外一種求解MST（最小生成樹）的算法—–Kruskal算法。
Kruskal算法可以概括為：
取出連通無(wú)向圖G的所有邊。從第一步形成的邊集合中選取權(quán)值最小的邊，加入最小生成樹邊集合T中。求出第二步中選出邊的兩端頂點(diǎn)，判斷他們所在頂點(diǎn)集的關(guān)系以確認(rèn)是否存在回路。若不存在回路，則確認(rèn)將此最小邊加入T中，若存在回路，則丟棄。 同Prim算法，我們用下面這一連通無(wú)向圖作為示例： 
下面給出實(shí)現(xiàn)代碼以及測(cè)試代碼：（在圖以及Prim算法的基礎(chǔ)上增加而來(lái)，若讀者覺(jué)得閱讀有困難，可參看前兩節(jié)文章）
#include<iostream>#include<cstdlib>#include<vector>using namespace std;/*節(jié)點(diǎn)類*/class Node{public: Node(char identifier = 0); char m_identifier; //頂點(diǎn)編號(hào) bool m_isVisited; //頂點(diǎn)訪問(wèn)標(biāo)志位：true表示已經(jīng)被訪問(wèn)};Node::Node(char identifier){ m_identifier = identifier; m_isVisited = false;}/*邊類，用于輔助實(shí)現(xiàn)生成最小生成樹*/class Edge{public: Edge(int NodeIndexA = 0, int NodeIndexB = 0, int WeightValue = 0); int m_NodeIndexA, m_NodeIndexB; //邊的兩端點(diǎn)（索引），這里以無(wú)向圖為例 int m_weightValue; //邊的權(quán)值 bool m_selected; //選擇標(biāo)志位，true表示已被選擇};Edge::Edge(int NodeIndexA, int NodeIndexB, int WeightValue){ m_NodeIndexA = NodeIndexA; m_NodeIndexB = NodeIndexB; m_weightValue = WeightValue; m_selected = false; //初始時(shí)未被選擇}/*圖類*/class Graph{public: Graph(int capacity); ~Graph(); int getGraphSize(); //獲取當(dāng)前圖的大小 void resetNode(); //重置所有頂點(diǎn)的訪問(wèn)標(biāo)志位為false，未訪問(wèn) bool addNode(Node *pNode); //添加新頂點(diǎn) bool addEdgeForUndirectedGraph(int row, int col, int val = 1); //添加邊以構(gòu)造無(wú)向圖，val表示權(quán)值，默認(rèn)權(quán)值1 bool addEdgeForDirectedGraph(int row, int col, int val = 1); //添加邊以構(gòu)造有向圖，val表示權(quán)值，默認(rèn)權(quán)值1 void printMatrix(); //打印鄰接矩陣 void depthFirstTraverse(int nodeIndex); //深度優(yōu)先遍歷，指定第一個(gè)點(diǎn) void widthFirstTraverse(int nodeIndex); //廣度優(yōu)先遍歷，指定第一個(gè)點(diǎn) void MSTPrim(int nodeIndex); //Prim算法求最小生成樹，指定第一個(gè)點(diǎn) void MSTKruskal(); //Kruskal算法求最小生成樹，指定第一個(gè)點(diǎn)private: bool getValueOfEdge(int row, int col, int &val); //獲取邊權(quán)值 void widthFirstTraverseImplement(vector<int> preVec); //利用vector實(shí)現(xiàn)廣度優(yōu)先遍歷 int getMinEdge(vector<Edge> edgeVec); //最小生成樹算法輔助函數(shù)，用于在邊集中選擇權(quán)值最小的邊 bool isInSet(vector<int> nodeSet, int target); //Kruskal輔助函數(shù)，用于判斷指定頂點(diǎn)是否在給定點(diǎn)集中 void mergeNodeSets(vector<int> &nodeSetA, vector<int> nodeSetB); //Kruscal輔助函數(shù)，用于合并兩個(gè)點(diǎn)集 int m_iCapacity; //圖容量，即申請(qǐng)的數(shù)組空間最多可容納的頂點(diǎn)個(gè)數(shù) int m_iNodeCount; //圖的現(xiàn)有頂點(diǎn)個(gè)數(shù) Node *m_pNodeArray; //存放頂點(diǎn)的數(shù)組 int *m_pMatrix; //為了方便，用一維數(shù)組存放鄰接矩陣 Edge *m_pEgde; //邊指針，存儲(chǔ)最小生成樹的邊};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]; //最小生成樹節(jié)點(diǎn)和邊數(shù)量關(guān)系}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; //訪問(wèn)第一個(gè)頂點(diǎn) cout << m_pNodeArray[nodeIndex].m_identifier << " "; m_pNodeArray[nodeIndex].m_isVisited = true; //訪問(wèn)其他頂點(diǎn) for (int i = 0;i < m_iCapacity;i++) { getValueOfEdge(nodeIndex, i, value); if (value != 0) //當(dāng)前頂點(diǎn)與指定頂點(diǎn)連通 { if (m_pNodeArray[i].m_isVisited == true) //當(dāng)前頂點(diǎn)已被訪問(wèn) continue; else //當(dāng)前頂點(diǎn)沒(méi)有被訪問(wèn)，則遞歸 { depthFirstTraverse(i); } } else //沒(méi)有與指定頂點(diǎn)連通 { continue; } }}void Graph::widthFirstTraverse(int nodeIndex){ //訪問(wèn)第一個(gè)頂點(diǎn) cout << m_pNodeArray[nodeIndex].m_identifier << " "; m_pNodeArray[nodeIndex].m_isVisited = true; vector<int> curVec; curVec.push_back(nodeIndex); //將第一個(gè)頂點(diǎn)存入一個(gè)數(shù)組 widthFirstTraverseImplement(curVec);}void Graph::widthFirstTraverseImplement(vector<int> preVec){ int value = 0; vector<int> curVec; //定義數(shù)組保存當(dāng)前層的頂點(diǎn) for (int j = 0;j < (int)preVec.size();j++) //依次訪問(wèn)傳入數(shù)組中的每個(gè)頂點(diǎn) { for (int i = 0;i < m_iCapacity;i++) //傳入的數(shù)組中的頂點(diǎn)是否與其他頂點(diǎn)連接 { getValueOfEdge(preVec[j], i, value); if (value != 0) //連通 { if (m_pNodeArray[i].m_isVisited==true) //已經(jīng)被訪問(wèn) { continue; } else //沒(méi)有被訪問(wèn)則訪問(wèn) { cout << m_pNodeArray[i].m_identifier << " "; m_pNodeArray[i].m_isVisited = true; //保存當(dāng)前點(diǎn)到數(shù)組 curVec.push_back(i); } } } } if (curVec.size()==0) //本層次無(wú)被訪問(wèn)的點(diǎn)，則終止 { 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; //存儲(chǔ)當(dāng)前邊的權(quán)值 int edgeCount = 0; //已選出的邊數(shù)量，用以判斷算法終結(jié) vector<int> nodeVec; //存儲(chǔ)點(diǎn)（索引）集的數(shù)組 vector<Edge> edgeVec; //存儲(chǔ)邊的數(shù)組 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(); //將當(dāng)前頂點(diǎn)索引復(fù)制給temp for (int i = 0;i < m_iCapacity;i++) //循環(huán)判斷每一個(gè)頂點(diǎn)與當(dāng)前頂點(diǎn)連接情況 { getValueOfEdge(temp, i, value); if (value != 0) //連通 { if (m_pNodeArray[i].m_isVisited == true) //已經(jīng)被訪問(wèn) continue; else //未被訪問(wèn),則將邊放入被選邊集合 { Edge edge(temp, i, value); edgeVec.push_back(edge); } } } /*選擇最小邊*/ int edgeIndex = getMinEdge(edgeVec); if (edgeIndex == -1) { cout << "獲取最小邊失敗，請(qǐng)重置后再試！" << endl; break; } edgeVec[edgeIndex].m_selected = true; //設(shè)置選擇標(biāo)志位為true，已被選擇 cout << edgeVec[edgeIndex].m_NodeIndexA << "---" << edgeVec[edgeIndex].m_NodeIndexB<<" "; cout << edgeVec[edgeIndex].m_weightValue << endl; m_pEgde[edgeCount] = edgeVec[edgeIndex]; edgeCount++; /*尋找當(dāng)前選擇的最小邊相連的下一個(gè)頂點(diǎn)*/ int nextNodeIndex = edgeVec[edgeIndex].m_NodeIndexB; nodeVec.push_back(nextNodeIndex); m_pNodeArray[nextNodeIndex].m_isVisited = true; cout << m_pNodeArray[nextNodeIndex].m_identifier << endl; } cout << "最小生成樹計(jì)算完畢，如上所示！";}void Graph::MSTKruskal(){ int value = 0; //存儲(chǔ)當(dāng)前邊的權(quán)值 int edgeCount = 0; //已選出的邊數(shù)量 /*存放節(jié)點(diǎn)集合的數(shù)組,不同于Prim，Kruskal算法過(guò)程中可能出現(xiàn)多個(gè)點(diǎn)集*/ vector<vector<int>> nodeSets; /*取出所有邊*/ vector<Edge> edgeVec; for (int i = 0;i < m_iCapacity;i++) //去鄰接矩陣的右上角的三角部分，不含對(duì)角線。無(wú)向圖鄰接矩陣對(duì)稱 { for (int k = i + 1;k < m_iCapacity;k++) { getValueOfEdge(i, k, value); if (value != 0) { Edge edge(i, k, value); edgeVec.push_back(edge); } } } /*循環(huán)尋找最小生成樹的邊*/ while (edgeCount < m_iCapacity - 1) { int minEdgeIndex = getMinEdge(edgeVec); edgeVec[minEdgeIndex].m_selected = true; //選出最小邊，并標(biāo)記為已選 int nodeAIndex = edgeVec[minEdgeIndex].m_NodeIndexA; int nodeBIndex = edgeVec[minEdgeIndex].m_NodeIndexB; //找出最小邊兩端頂點(diǎn) bool nodeAIsInSet = false; //標(biāo)記某個(gè)頂點(diǎn)是否在指定點(diǎn)集中 bool nodeBIsInSet = false; int nodeAInSetLabel = -1; //某個(gè)頂點(diǎn)所在點(diǎn)集的索引 int nodeBInSetLabel = -1; for (int i = 0;i < (int)nodeSets.size();i++) //尋找A頂點(diǎn)所在點(diǎn)集 { nodeAIsInSet = isInSet(nodeSets[i], nodeAIndex); if (nodeAIsInSet) { nodeAInSetLabel = i; //保存當(dāng)前點(diǎn)集索引 } } for (int i = 0;i < (int)nodeSets.size();i++) //尋找B頂點(diǎn)所在點(diǎn)集 { nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex); if (nodeBIsInSet) { nodeBInSetLabel = i; //保存當(dāng)前點(diǎn)集索引 } } /*根據(jù)結(jié)果做相應(yīng)處理*/ if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1) //兩頂點(diǎn)均不在已有點(diǎn)集中 { //建立新的點(diǎn)集 vector<int> vec; vec.push_back(nodeAIndex); vec.push_back(nodeBIndex); nodeSets.push_back(vec); } else if (nodeAInSetLabel == -1 && nodeBInSetLabel != -1) //某頂點(diǎn)在已有點(diǎn)集中 { //將另外一個(gè)節(jié)點(diǎn)加入已有點(diǎn)集 nodeSets[nodeBInSetLabel].push_back(nodeAIndex); } else if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1) { nodeSets[nodeAInSetLabel].push_back(nodeBIndex); } else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel) //兩個(gè)頂點(diǎn)在不同的點(diǎn)集中 { //合并兩個(gè)集合，到前一參數(shù)點(diǎn)集，并將頂點(diǎn)從第二個(gè)參數(shù)點(diǎn)集刪除 mergeNodeSets(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]); for (int k = nodeBInSetLabel;k < (int)nodeSets.size()-1;k++) { nodeSets[k] = nodeSets[k + 1]; } } else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel) //兩個(gè)頂點(diǎn)在同一點(diǎn)集 { //存在回路，放棄當(dāng)前邊 continue; } m_pEgde[edgeCount] = edgeVec[minEdgeIndex]; edgeCount++; cout << edgeVec[minEdgeIndex].m_NodeIndexA << "---" << edgeVec[minEdgeIndex].m_NodeIndexB << " "; cout << edgeVec[minEdgeIndex].m_weightValue << endl; }}int Graph::getMinEdge(vector<Edge> edgeVec){ int minWeight = 0; //用于輔助選擇最小權(quán)值邊 int edgeIndex = 0; //用于存儲(chǔ)最小邊索引 int i = 0; /*找出第一條未被選擇的邊*/ for (;i < (int)edgeVec.size();i++) { if (edgeVec[i].m_selected == false) //當(dāng)前邊未被選擇 { minWeight = edgeVec[i].m_weightValue; edgeIndex = i; break; } } if (minWeight == 0) //邊集所有邊被訪問(wèn) { 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;}bool Graph::isInSet(vector<int> nodeSet, int target){ for (int i = 0;i < (int)nodeSet.size();i++) { if (nodeSet[i] == target) return true; } return false;}void Graph::mergeNodeSets(vector<int> &nodeSetA, vector<int> nodeSetB){ for (int i = 0;i < (int)nodeSetB.size();i++) { nodeSetA.push_back(nodeSetB[i]); }}int main(){ Graph *pGraph = new Graph(6); cout << "初始化頂點(diǎn)中……" << 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 << "添加頂點(diǎn)至圖中……" << 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 << "深度優(yōu)先遍歷：" << endl; pGraph->depthFirstTraverse(0); cout << endl << endl; pGraph->resetNode(); cout << "廣度優(yōu)先遍歷：" << endl; pGraph->widthFirstTraverse(0); cout << endl << endl; pGraph->resetNode(); cout << "最小生成樹為：" << endl; pGraph->MSTKruskal(); cout << endl; system("pause");} 測(cè)試結(jié)果如下： 
在文章開始對(duì)Kruskal算法的描述中，涉及到循環(huán)的每一次都要尋找最小邊的問(wèn)題。我們可以換一種思路，作如下描述：
對(duì)G的邊以飛降序權(quán)重排序。對(duì)于排序表中的每條邊，如果現(xiàn)在把它加入T不會(huì)形成回路，則將其加入T集合中，否則丟棄。有興趣的讀者可以自己用這一種算法描述來(lái)改進(jìn)Krukal算法，這樣就不需要每進(jìn)行一次循環(huán)就需要調(diào)用getMinEdge()函數(shù)，可以減少算法時(shí)間開銷。這樣一來(lái)，若G含有m條邊，則其算法時(shí)間復(fù)雜度為O（m * log m）。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
