C++ 图进阶系列之 kruskal 和 Prim 算法_图向最小生成树的华丽转身

2.2.2 实现kruskal算法

本质是使用并查集合并指定边两端的顶点。

//描述图中顶点与顶点之间的关系
template
struct Edge {
	T from;
	T to;
	int weight;
};
/*
* Kruskal 算法
*/
template
class Kruskal {
	private:
		//集合群（森林）
		map*,Tree*> trees;
		//森林中树的数量
		int size;
	public:
        /*
        *构造集合（森林）群
        */
		Kruskal(T datas[],int size) {
			this->size=size;
			this->initSets(datas);
		}
		/*
		*初始化森林
		*/
		void initSets(T datas[]) {
			for(int i=0; isize; i++ ) {
				//创建只有根结点的树
				Tree* tree=new Tree(datas[i]);
				//存入集合群
				this->trees[tree->getRoot()]=tree;
			}
		}
		/*
		* 通过节点值查找其所在的树(集合)
		* 返回树的根结点（唯一标志符）
		*/
		Vertex* find(T value) {
			typename::std::map*,Tree*>::iterator begin=trees.begin();
			typename::std::map*,Tree*>::iterator end=trees.end();
			while(begin!=end) {
				Tree *tree=begin->second;
				Vertex* root=tree->getRoot(value);
				if(root!=NULL)return root;
				begin++;
			}
			return NULL;
		}
		/*
		*合并树
		*/
		bool unionSet(T from,T to,int weight=1) {
			Vertex* root =this->find(from);
			Vertex* root_ =this->find(to);
            //同一棵树
			if(root==root_)return false;
			Vertex* ver=this->trees[root]->findVertex(from);
			Vertex* ver_=this->trees[root_]->findVertex(to);
             //合并两个顶点
			ver->addChild(ver_,weight);
			//合并树
			this->trees[root]->unionTree(this->trees[root_] );
			//删除
			this->trees.erase(root_);
			this->size--;
		}
		/*
		*查找最小生成树
		*/
		void kruskal_(Edge relation[]) {
			for(int i=0; iunionSet(relation[i].from,relation[i].to,relation[i].weight);
			}
		}
		/*
		*输出最小生成树
		*/
		void showAllTree() {
			typename::std::map*,Tree*>::iterator begin=trees.begin();
			typename::std::map*,Tree*>::iterator end=trees.end();
			while(begin!=end) {
				Vertex* root=begin->first;
				Tree *tree=begin->second;
				tree->showAll();
				begin++;
			}
		}
};

测试： 简化了图的描述，直接提供已经排序的信息，侧重测试算法设计是否准确。

int main(int argc, char** argv) {
	char datas[7]= {'A','B','C','D','E','F','G'};
    //硬代码，对图中的边按权重由小到大排序
	Edge relations[9]= { {'A','B',1}, {'A','C',2},{'B','G',2},{'B','F',3},{'F','G',3},{'F','E',3},{'G','D',4},{'C','D',5},{'D','E',6} };
    //初始算法
	Kruskal kruskal(datas,7);
	kruskal.kruskal_( relations);
	kruskal.showAllTree();
	return 0;
}

输出结果：和前文演示结果一致。

3. Prim(普里姆) 算法

Prim算法核心也是贪心思想，算法流程类似于最短路径算法Dijkstra算法。

相比较于kruskal，前者基于静态信息（提前对边按权重排序），后者基于动态信息（由优先队列随时调整）。

3.1 算法流程

如查询如下图结构的最小生成树。

• 任意选择一顶点，如A。然后把与此顶点相邻的边(A,B,1)、(A,C,2)压入到优先队列中，优先队列以边的权重小为优先。如下图所示。

• 从优先队列中选择(A,B,1)这条边，检查边两端的顶点是否已经被选择，选择B顶点。然后把B相邻的邻接边(B,G,2)、(B,F,3)压入到优先队列。

• 从队列中选择(A,C,2)边，选择C顶点，且把C相邻边(C,D,5)压入队列。

• 选择（B,G,2）边，选择G顶点，且把(G,F,3)、(G,D,4)压入队列。

• 从队列中选择(B,F,3)，选择F顶点，且压入(F,E,3)边。

• 选择(G,F,3)边，因边两端顶点都已经选择，再选择(F,E,3)边，选择E顶点，且把(E,d,6)压入队列。

• 最后选择(G,D,4)，选择D顶点，完成最小生成树。

3.2 编码实现

顶点类和树类和前面的kruskal算法一样。

因为需要动态获取边的权重，对边类升级：

template
struct Edge {
	Vertex* from;
	Vertex* to;
	int weight;
	Edge() {}
	Edge(Vertex* from,Vertex* to,int weight) {
		this->from=from;
		this->to=to;
		this->weight=weight;
	}
    /*
    * 用于优先队列的比较法则
    */
	bool operator() (Edge* v1, Edge* v2) {
		//由小到大排列
		return v1->weight > v2->weight;
	}
};

Prim 算法类：

/*
*算法类
*/
template
class Prim {
	private:
		//优先队列容器
		priority_queue* ,vector*>,Edge > priorityQueue;
		//图的顶点
		map*> graph;
		//图的邻接矩阵
		int** martix;
		//图的顶点数量
		int size;
		//最小生成树
		Tree* tree;
	public:
		/*
		*构造函数
		*/
		Prim(T data[],int** martix) {
			this->size= sizeof(data)/sizeof(T);
			//初始化图顶点
			for(int i=1; isize; i++ ) {
				Vertex* ver=new Vertex(i,data[i]);
				this->graph[ver->code]=ver;
			}
			//初始化最小生成树
			this->tree=new Tree( this->graph[1]);
            //图的邻接关系
			this->martix=martix;
		}
		/*
		*查找与某顶点邻接的边,并压入队列中
		*/
		void pushQueue(Vertex* ver) {
			int row=ver->code;
			Vertex* to=NULL;
			for(int i=1; isize; i++) {
				if(this->martix[row][i]>0) {
					to=this->graph[i];
					Edge* edge=new Edge(ver,to,this->martix[row][i]);
					//添加边至队列
					this->priorityQueue.push(edge);
                     //标志已经使用
					this->martix[row][i]=0;
				}
			}
		}
		/*
		*核心
		*/
		void prim() {
			//得到最小生成树的根结点
			Vertex* from= this->tree->getRoot();
			//找到邻接边
			this->pushQueue(from);
			while( !this->priorityQueue.empty() ) {
				//边出队列
				Edge* edge = this->priorityQueue.top();
				this->priorityQueue.pop();
				//把结点添加至树中
				if(this->tree->addVertex(edge->from)) {
                      //查找相邻边
					this->pushQueue(edge->from);
				}
				if(this->tree->addVertex(edge->to)) {
					this->pushQueue(edge->to);
					edge->from->addChild(edge->to,edge->weight);
				}
			}
		}
		void showTree() {
			this->tree->showAll();
		}
};

测试

int main(int argc, char** argv) {
	char datas[8]= {'0','A','B','C','D','E','F','G'};
	//邻接矩阵存储顶点之间的关系
	int** martix=new int*[8];
	martix[0]=new int[8] {0,0,0,0,0,0,0,0};
	martix[1]=new int[8] {0,0,1,2,0,0,0,0};
	martix[2]=new int[8] {0,1,0,0,0,0,3,2};
	martix[3]=new int[8] {0,2,0,0,5,0,0,0};
	martix[4]=new int[8] {0,0,0,5,0,6,0,4};
	martix[5]=new int[8] {0,0,0,0,6,0,3,0};
	martix[6]=new int[8] {0,0,3,0,0,3,0,3};
	martix[7]=new int[8] {0,0,2,0,4,0,3,0};
	Prim prim(datas,martix);
	prim.prim();
    cout<<"Prim 最小生成树算法"<