加权无向图的最小生成树(MST)Kruskal算法 -- C++实现


实现代码

// EdgesWeightGraph.h

#ifndef EDGESWEIGHTGRAPH_H
#define EDGESWEIGHTGRAPH_H

#include "Component.h"
#include "PriorityQueueMin.h"

namespace jay{

	template<typename T>
	class EdgesWeightGraph
	{
	private:

		hash_map<T,list<Edges<T>>> m_mapList; // 邻接表 存放了每个对应对应的已连通的顶点
		int m_V; // 顶点的数量
		int m_E; // 边的数量

		queue<Edges<T>> m_mst;     // 最小生成树(MST)的边
		hash_map<T,bool> m_marked; // marked[v] = true if v on tree
		double m_MstWeight; // 整个树的权重
		PriorityQueueMin<Edges<T>> m_minpq; // 横切边 优先队列

		QuickUnionUF_T<T> m_uf; // 目前的强连通分量是有bug的,前期实现的时候没有考虑通用模板的问题,这里展示只能使用int类型

	public:

		void AddEdge(T v,T w,double weight);
		void Show();
		void ShowMST();

		bool hasSelfLoop();

		void Kruskal();

		void ResetMarkTag(bool mark = false);

		int VertexCount();

		EdgesWeightGraph();
		~EdgesWeightGraph();

	};

	template<typename T>
	EdgesWeightGraph<T>::EdgesWeightGraph()
	{
		m_V = 0;
		m_E = 0;
	}

	template<typename T>
	EdgesWeightGraph<T>::~EdgesWeightGraph()
	{
	}

	template<typename T>
	void EdgesWeightGraph<T>::AddEdge(T v,T w,double weight)
	{
		Edges<T> edges(v,w,weight);
		m_mapList[v].push_front(edges);

		Edges<T> edges2(w,v,weight);
		m_mapList[w].push_front(edges2);

		m_E++;
	}

	template<typename T>
	int EdgesWeightGraph<T>::VertexCount()
	{
		return m_mapList.size();
	}

	template<typename T>
	void EdgesWeightGraph<T>::Kruskal()
	{
		PriorityQueueMin<Edges<T>> pq;
		// 图的所有边入队列
		hash_map<T,list<Edges<T>>>::iterator it;
		for(it = m_mapList.begin();it != m_mapList.end();it++)
		{
			list<Edges<T>>::iterator it2;
			for (it2 = it->second.begin(); it2!=it->second.end();it2++)
			{
				pq.Insert(*it2);
			}

		}

		while (!pq.IsEmpty() && (m_mst.size() < VertexCount() - 1)) 
		{
			Edges<T> e = pq.PopMin();// 权值最小的边出队列

			int v = e.EitherVertex(); // 获得边e的两个顶点
			int w = e.OtherVertex(v);

			// 对于uf来说,当v和w不相连,也就是他们其中至少有一个顶点没有加入MST时,将该边入MST,并且在uf中对这两个顶点v和w进行相连
			// 对于uf来说,当如果v和w相连,则说明这两点已在MST中,不需要再处理
			// 或者按照书本的理解V和w已经连通了,再添加一个连通路径就形成了回路
			if (!m_uf.isConnected(v, w)) 
			{ // v-w does not create a cycle 
				m_uf.Union(v, w);  // merge v and w components
				m_mst.push(e);  // add edge e to mst
				m_MstWeight += e.Weight();
			}
		}

		ShowMST();

	}

	template<typename T>
	void EdgesWeightGraph<T>::Show()
	{
		hash_map<T,list<Edges<T>>>::iterator it;
		for(it = m_mapList.begin();it != m_mapList.end();it++)
		{
			cout << "当前顶点 " << it->first << ": ";
			list<Edges<T>>::iterator it2;

			for (it2 = it->second.begin(); it2!=it->second.end();it2++)
			{
				cout << it2->SecondVertex() << "(" << it2->Weight() << ") ";
			}

			cout << endl;

		}
	}

	template<typename T>
	void EdgesWeightGraph<T>::ShowMST()
	{
		cout << "MST :" << endl;

		while(!m_mst.empty())
		{
			Edges<T> e = m_mst.front();
			m_mst.pop();
			cout << e.FristVertex() << " " << e.SecondVertex() << "(" << e.Weight() << ")" ;
			cout << endl;
		}
	}

	template<typename T>
	bool EdgesWeightGraph<T>::hasSelfLoop()
	{
		hash_map<T,list<Edges<T>>>::iterator it;

		// 遍历所有顶点
		for (it = m_mapList.begin(); it != m_mapList.end(); it++) 
		{
			T v = it->first;
			list<Edges<T>>::iterator it2;
			// 遍历顶点的邻接顶点
			for (it2 = it->second.begin(); it2 != it->second.end(); it2++) 
			{
				// 如果邻接顶点和顶点一样,则说明存在自环
				if (v == it2->SecondVertex()) 
				{
					return true;
				}
			}
		}

		return false;
	}
	
	template<typename T>
	void EdgesWeightGraph<T>::ResetMarkTag(bool mark = false)
	{
		hash_map<T,bool>::iterator it;
		for (it = m_marked.begin();it!=m_marked.end();it++)
		{
			it->second = mark;
		}
	}


};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#include "Component.h"
#include "EdgesWeightGraph.h"


using namespace jay;



int main(int argc, char* argv[])
{

	EdgesWeightGraph<int> gra;
	/*
	gra.AddEdge(0,5,1.1);
	gra.AddEdge(5,4,1.2);
	gra.AddEdge(0,1,1.3);
	gra.AddEdge(2,0,1.4);
	gra.AddEdge(2,3,1.5);
	gra.AddEdge(3,5,1.6);
	gra.AddEdge(0,6,1.7);
	gra.AddEdge(6,4,1.8);

	gra.AddEdge(8,7,1.9);
	gra.AddEdge(7,6,2.0);
	gra.AddEdge(6,9,2.1);
	gra.AddEdge(9,10,2.2);
	gra.AddEdge(9,11,2.3);
	gra.AddEdge(11,12,2.4);
	gra.AddEdge(9,12,2.5);
//	gra.AddEdge(12,12,2.5); 自环测试
//	gra.AddEdge(12,9); // 有环测试
	
	*/
	
	int iCount = 0;
	int p,q;
	double z;
	while(cin>>p)
	{
		cin>>q;
		cin>>z;
		gra.AddEdge(p,q,z);
	}

	gra.Show();

	cout << "hasSelfLoop? " <<gra.hasSelfLoop()<<endl;

	gra.Kruskal();
	
//	gra.KosarajuCC();
	

//	cout << "hasParallelEdges? " << gra.hasParallelEdges() << endl;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。