“test.cpp”
#include<iostream> using namespace std; #include<vector> #include<string> #include<assert.h> #include "Heap.h" #include "UnionFindFet.h" template<class V,class W> class GraphLink { public: struct Node { W _w; size_t _src; size_t _dst; Node* _next; Node(size_t src,size_t dst,const W& w) :_src(src) ,_dst(dst) ,_w(w) ,_next(NULL) {} }; GraphLink(V* vertexs,size_t size,bool isDirected = false) :_vertexs(vertexs,vertexs+size) ,_isDirected(isDirected) { _table.resize(size); } GraphLink(bool isDirected) :_isDirected(isDirected) {} public: void AddEdge(const V& src,const V& dst,const W& w) { size_t newsrc = _GetIndex(src); size_t newdst = _GetIndex(dst); if(_isDirected) _AddEdge(newsrc,newdst,w); else { _AddEdge(newsrc,newdst,w); _AddEdge(newdst,newsrc,w); } } void Display() { for(size_t i = 0;i < _vertexs.size();++i) { cout<<_vertexs[i]<<"["<<i<<"]->"; Node* cur = _table[i]; while(cur) { cout<<cur->_w<<"["<<cur->_dst<<"]->"; cur = cur->_next; } cout<<"NULL"<<endl; } } //克鲁斯卡尔算法 bool Kruskal(GraphLink<V,W>& mintree) { assert(_isDirected == false); mintree._vertexs = _vertexs; mintree._isDirected = _isDirected; mintree._table.resize(_vertexs.size()); //仿函数，用权值来对堆进行建小堆 struct Compare { bool operator()(Node* L,Node* R) { return L->_w < R->_w; } }; Heap<Node*,Compare> minheap; for (size_t i = 0;i < _table.size();i++) { Node* cur = _table[i]; while (cur) { //对无向图进行过滤，不让相同的边重复进入 if (cur->_src < cur->_dst) { minheap.Push(cur); } cur = cur->_next; } } size_t n = 0; //使用并查集高效的判断是否成环 UnionSet ufs(_vertexs.size()); while (n < (_vertexs.size() - 1)) { if(minheap.Empty()) return false; Node* edge = minheap.Top(); minheap.Pop(); int root1 = ufs.FindRoot(edge->_src); int root2 = ufs.FindRoot(edge->_dst); if (root1 != root2) { ufs.UnionSetFrient(root1,root2); mintree._AddEdge(edge->_src,edge->_dst,edge->_w); ++n; } } //打印最小生成树的顶点之间的边 mintree._KruskalDisplay(); return true; } private: void _KruskalDisplay() { for (size_t i = 0;i < _table.size();++i) { Node* cur = _table[i]; while (cur) { cout<<cur->_src<<"--"<<cur->_dst<<","; cur = cur->_next; } } } void _AddEdge(size_t src,size_t dst,const W& w) { Node* tmp = new Node(src,dst,w); tmp->_next = _table[src]; _table[src] = tmp; } size_t _GetIndex(const V& v) { for(size_t i = 0;i < _vertexs.size();++i) if(_vertexs[i] == v) return i; assert(false); } private: vector<V> _vertexs; vector<Node*> _table; bool _isDirected; }; void test() { string arr[] = {"A","B","C","D","E"}; int size = sizeof(arr)/sizeof(arr[0]); GraphLink<string,int> gl(arr,size); gl.AddEdge("A","D",10); gl.AddEdge("D","B",20); gl.AddEdge("B","C",10); gl.AddEdge("C","E",40); gl.AddEdge("E","B",30); gl.AddEdge("E","A",20); gl.Display(); GraphLink<string,int> g2(false); //最小生成树 gl.Kruskal(g2); } int main() { test(); system("pause"); return 0; } “Heap.h” #pragma once #include <vector> #include <assert.h> template<class T> struct Less { bool operator()(const T& left,const T& Right) { return left < Right; } }; template<class T> struct Greater { bool operator()(const T& left,const T& Right) { return left > Right; } }; template<class T,class Compare = Greater<T>>//缺省值给大堆 class Heap { public: Heap(){} Heap(const T* arr,const size_t size) { for (int i = 0;i < size;i++) { _arr.push_back(arr[i]); } //建堆 for (int i = (_arr.size() - 2) / 2;i >= 0;i--) { //寻找非叶子结点，向下调整； AdjustDown(i); } } void Push(const T& data) { _arr.push_back(data); AdjustUp(_arr.size()-1); } void Pop() { assert(_arr.empty() != true); swap(_arr[0],_arr[_arr.size()-1]); _arr.pop_back(); AdjustDown(0); } T Top() { return _arr[0]; } bool Empty() { return _arr.empty(); } int Size() { return _arr.size(); } void Cout() { for (int i = 0; i < _arr.size();i++) { cout<<_arr[i]<<" "; } cout<<endl; } private: void AdjustDown(int parent) { int child = 2 * parent + 1;//左孩子 Compare com; while (child < _arr.size()) { if (((child+1) < _arr.size())&&(com(_arr[child + 1],_arr[child]))) { ++child; } if (com(_arr[child],_arr[parent])) { swap(_arr[child],_arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void AdjustUp(int child) { int parent = (child - 1) / 2; Compare com; while (child > 0) { if (com(_arr[child],_arr[parent])) { swap(_arr[child],_arr[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } private: vector<T> _arr; }; “UnionFindSet.h” #pragma once #include<vector> class UnionSet { public: UnionSet(int n) :_n(n) { _set.resize(n+1,-1); for(size_t i = 0;i < _set.size();++i) { _set[i] = -1; } } void UnionSetFrient(int root1,int root2) { int newroot1 = FindRoot(root1); int newroot2 = FindRoot(root2); if(newroot1 != newroot2) { _set[newroot1] += _set[newroot2]; _set[newroot2] = newroot1; } } int Count() { int count = 0; for(size_t i = 0;i < _set.size();++i) { if(_set[i] < 0) ++count; } //初始化时0位置的下标为-1，0位置下标不参与计算 return (count - 1); } int FindRoot(int x) { if(_set[x] >= 0)//不是根 { x = _set[x]; } return x; } private: //int* _set; vector<int> _set; int _n; };