Kruskal算法 · 數據結構與算法分析-C語言描述

? ?**Kruskal算法**是求圖最小生成樹的一種算法，另外一種是[Prim算法](http://blog.csdn.net/u012796139/article/details/49865361)。 ? ?**Kruskal算法思想**：Kruskal算法按照邊的權重(從大到小)處理它們，將邊加入最小生成樹中，加入的邊不會對已經加入的邊構成環，直到樹中含有V-1條邊為止。 **源代碼**示例： ~~~ #include <iostream> #include <vector> #include <set> #include <algorithm> #include <functional> using namespace std; class Edge { public: Edge(size_t _v, size_t _w, double _weight) : v(_v), w(_w), weight(_weight) {} double getWeight() const { return weight; } size_t either() const { return v; } size_t other(size_t v) const { if (v == this->v) return this->w; else if (v == this->w) return this->v; else { cout << "error in Edge::other()" << endl; exit(1); } } void print() const{ cout << "(" << v << ", " << w << ", " << weight << ") "; } private: size_t v, w; // 兩個頂點 double weight; // 權重 }; /// 加權無向圖 class EdgeWeithtedGraph { public: EdgeWeithtedGraph(size_t vertax_nums) : vertaxs(vertax_nums), edges(0), arr(vertax_nums) {} void addEdge(const Edge e); vector<Edge> adj(size_t v) const { return v < arrSize() ? arr[v] : vector<Edge>(); } vector<Edge> allEdges() const; // 返回加權無向圖的所有邊 size_t arrSize() const { return arr.size(); } size_t vertax() const { return vertaxs; } size_t edge() const { return edges; } void printVertax(size_t v) const; void printGraph() const; private: size_t vertaxs; // 頂點個數 size_t edges; // 邊的個數 vector<vector<Edge>> arr; // 鄰接表 }; /// 無向圖數據結構，用于測試Kruskal算法中的邊是否能構成環 class Graph { public: Graph(size_t n) : arr(n), edges(0), vertaxs(n) {} void addEdge(size_t a, size_t b) { if (!(a < arr.size() && b < arr.size())) return; arr[a].push_back(b); arr[b].push_back(a); edges++; } vector<size_t> adj(size_t n) const { if (n < arr.size()) return arr[n]; else return vector<size_t>(); } /// 返回頂點個數 size_t vertax() const { return arr.size(); } private: vector<vector<size_t>> arr; // 鄰接表 size_t edges; // 邊的個數 size_t vertaxs; // 頂點個數 }; /// 使用深度優先遍歷判斷Graph是否是無環圖 class Cycle { public: Cycle(const Graph &graph) : marked(graph.vertax()), has_cycle(false) { for (size_t i = 0; i < graph.vertax(); i++) marked[i] = false; for (size_t i = 0; i < graph.vertax(); i++) { if (!marked[i]) dfs(graph, i, i); } } bool hasCycle() const { return has_cycle; } private: void dfs(const Graph &graph, size_t v, size_t u) { marked[v] = true; vector<size_t> vec = graph.adj(v); for (size_t i = 0; i < vec.size(); i++) { if (!marked[vec[i]]) dfs(graph, vec[i], v); else if (vec[i] != u) // 無環圖其實就是樹，此時v是樹中一個節點，其父節點為u，當marked[vec[i]]==true時，表示v的父節點一定為u，否則圖中有環 has_cycle = true; } } vector<bool> marked; bool has_cycle; }; /// 判斷最小生成樹中是否有環，在Kruskal算法算法中被調用 bool hasCycle(vector<Edge> vec, size_t nvextax) { if (vec.size() == 0) return false; Graph graph(nvextax); for (size_t i = 0; i < vec.size(); i++) { size_t v = vec[i].either(); size_t w = vec[i].other(v); graph.addEdge(v, w); } Cycle cycle(graph); return cycle.hasCycle(); } /// 為了存放Kruskal算法過程中的邊，這些邊按照權值從小到大排列 template <typename T> struct greator { bool operator()(const T &x, const T &y) { return x.getWeight() < y.getWeight(); } }; /// 最小生成樹的Kruskal算法 class KruskalMST { public: KruskalMST(const EdgeWeithtedGraph &graph) { set<Edge, greator<Edge>> pq; // 計算過程保存邊的set vector<Edge> vec = graph.allEdges(); set<Edge>::iterator miniter; for (size_t i = 0; i < vec.size(); i++) // 將所有的邊存到pq中 pq.insert(vec[i]); while (!pq.empty() && mst.size() < graph.arrSize() - 1) // graph.arrSize()可替換為變量 { miniter = pq.begin(); mst.push_back(*miniter); if (hasCycle(mst, graph.arrSize())) removeEdge(*miniter); pq.erase(miniter); } } vector<Edge> edges() const { return mst; } void printEdges() const { for (size_t i = 0; i < mst.size(); i++) { mst[i].print(); } cout << endl; } private: void removeEdge(Edge e) { size_t v = e.either(); size_t w = e.other(v); for (size_t i = 0; i < mst.size(); i++) { size_t iv = mst[i].either(); size_t iw = mst[i].other(iv); if (v == iv && w == iw) { mst.erase(mst.begin() + i); return; } } } vector<Edge> mst; }; int main(void) { EdgeWeithtedGraph graph(8); graph.addEdge(Edge(0, 7, 0.16)); graph.addEdge(Edge(0, 2, 0.26)); graph.addEdge(Edge(0, 4, 0.38)); graph.addEdge(Edge(0, 6, 0.58)); graph.addEdge(Edge(1, 7, 0.19)); graph.addEdge(Edge(5, 7, 0.28)); graph.addEdge(Edge(2, 7, 0.34)); graph.addEdge(Edge(4, 7, 0.37)); graph.addEdge(Edge(1, 3, 0.29)); graph.addEdge(Edge(1, 5, 0.32)); graph.addEdge(Edge(1, 2, 0.36)); graph.addEdge(Edge(2, 3, 0.17)); graph.addEdge(Edge(6, 2, 0.40)); graph.addEdge(Edge(3, 6, 0.52)); graph.addEdge(Edge(4, 5, 0.35)); graph.addEdge(Edge(6, 4, 0.93)); cout << "arrSize: " << graph.arrSize() << endl; cout << "vertax: " << graph.vertax() << endl; cout << "edge: " << graph.edge() << endl; cout << "----------------" << endl; graph.printGraph(); cout << endl; // 輸出無向圖的所有邊 vector<Edge> vec = graph.allEdges(); for (size_t i = 0; i < vec.size(); i++) vec[i].print(); cout << endl << endl; // Kruskal算法 KruskalMST prim(graph); prim.printEdges(); system("pause"); return 0; } void EdgeWeithtedGraph::addEdge(const Edge e) { size_t v = e.either(); size_t w = e.other(v); if (!(v < arrSize() && w < arrSize())) return; arr[v].push_back(e); arr[w].push_back(e); this->edges++; } vector<Edge> EdgeWeithtedGraph::allEdges() const { vector<Edge> vec; for (size_t i = 0; i < arrSize(); i++) { for (size_t j = 0; j < arr[i].size(); j++) { if (arr[i][j].other(i) > i) // 所有邊的權重各不不同，可以這樣判斷，每個邊只保留一個 vec.push_back(arr[i][j]); } } return vec; } void EdgeWeithtedGraph::printVertax(size_t v) const { if (v >= arrSize()) return; for (size_t i = 0; i < arr[v].size(); i++) arr[v][i].print(); cout << endl; } void EdgeWeithtedGraph::printGraph() const { for (size_t i = 0; i < arrSize(); i++) { cout << i << ": "; printVertax(i); } } ~~~ **參考資料**： ? ? ?1、[https://github.com/luoxn28/algorithm_data_structure](https://github.com/luoxn28/algorithm_data_structure)?（里面有常用的數據結構源代碼，圖相關算法在graph文件夾中） ? ? ?2、《算法第4版》圖的Prim算法章節 ? ? ?3、[Prim算法](http://blog.csdn.net/u012796139/article/details/49865361)