有向图的拓扑排序(TopologicalSort) -- C++实现


实现代码

// DirectionGraph.h

#ifndef DIRECTIIONGRAPH_H
#define DIRECTIIONGRAPH_H

#include "Component.h"

namespace jay{

	template<typename T>
	class DirectionGraph
	{
	private:

		// 可以用自己实现的散列表,嫌麻烦,直接使用stl提供的hashmap
		hash_map<T,LinkList<T>> m_mapList; // 邻接表 存放了每个对应对应的已连通的顶点
		int m_V; // 顶点的数量
		int m_E; // 边的数量

		hash_map<T,int> m_iInDegree; // 入度数
		hash_map<T,bool> m_marked;
		hash_map<T,bool> m_OnStack;
		hash_map<T,T> m_edgeTo;
		queue<T> m_cycle;
		bool m_isHasCycle;

		queue<T> preorder; // 所有顶点的前序排列
		deque<T> postorder; //所有顶点的后序排列
		// 逆后序是后序的逆序
	public:

		void AddEdge(T v,T w );
		void DeleteEdge(T v,T w );
		void DeleteVertex(T v);
		void checkValid(T v);

		void Show();

		int Outdegree(T v);
		int Indegree(T v);

		void Reverse(DirectionGraph<T> &tmp);

		bool isReachable(T v);

		void ResetMarkTag(bool mark = false);
		void DeepFristSearch(T v);
		void DFS();

		void TopologicalSort(); 

		void ClearQueue(queue<T>& q) ;
		bool hasLoop();
		bool hasLoop(T v);

		DirectionGraph();
		~DirectionGraph();

	};

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

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

	template<typename T>
	bool DirectionGraph<T>::isReachable(T v)
	{
		return m_marked[v];
	}

	template<typename T>
	void DirectionGraph<T>::TopologicalSort()
	{
		DFS();

		cout << "前序:";
		while(!preorder.empty())
		{
			T v = preorder.front();
			preorder.pop();
			cout << v << " ";
		}
		cout <<endl;

		deque<T> tmp = postorder;
		cout << "后序:";
		while(!postorder.empty())
		{
			T v = postorder.back();
			postorder.pop_back();
			cout << v << " ";
		}
		cout <<endl;

		cout << "拓扑排序(逆后序)):";
		while(!tmp.empty())
		{
			T v = tmp.front();
			tmp.pop_front();
			cout << v << " ";
		}
		cout <<endl;

		// 逆后序是后序的逆顺序

	}

	template<typename T>
	void DirectionGraph<T>::DFS()
	{
		// 初始化相关操作
		m_edgeTo.clear();
		ResetMarkTag();

		hash_map<T,LinkList<T>>::iterator it;
		for (it = m_mapList.begin();it!=m_mapList.end();it++)
		{
			if (!m_marked[it->first]) 
			{
				DeepFristSearch(it->first);
			}
		}
	}

	template<typename T>
	void DirectionGraph<T>::DeepFristSearch(T v)
	{
		m_marked[v] = true;
		LinkList< T>::iterator it;
		preorder.push(v); //前序 递归前入队列 获取顺序的时候得到的结果是 比邻接顶点顺序更前
		for (it = m_mapList[v].begin();it!=m_mapList[v].end();it++)
		{
			if (!m_marked[it->m_value]) 
			{
				m_edgeTo[it->m_value] = v;
				DeepFristSearch(it->m_value);
			}
		}

		postorder.push_front(v);//后序 在递归调用之后 获取顺序的时候得到的结果是比邻接顶点顺序更后
	}

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

	template<typename T>
	void DirectionGraph<T>::AddEdge(T v,T w)
	{
		m_mapList[v].Add(w);

		m_iInDegree[w]++;

		m_E++;
	}

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

	template<typename T>
	void DirectionGraph<T>::ClearQueue(queue<T>& q) 
	{
		queue<T> empty;
		swap(empty, q);
	}

	template<typename T>
	bool DirectionGraph<T>::hasLoop()
	{
		ClearQueue(m_cycle);
		ResetMarkTag();
		m_isHasCycle = false;

		hash_map<T,LinkList<T> >::iterator it2;

		// 遍历所有顶点
		for (it2 = m_mapList.begin(); it2 != m_mapList.end(); it2++) 
		{
			T v = it2->first;

			if (!m_marked[v])
			{
				hasLoop(v);
				if (m_isHasCycle)
				{
					return m_isHasCycle;
				}
			}

			ResetMarkTag();
		}

		return false;
	}

	template<typename T>
	bool DirectionGraph<T>::hasLoop(T v)
	{
		m_marked[v] = true;
		m_OnStack[v] = true; // 标记本次已遍历
		LinkList< T>::iterator it;
		for (it = m_mapList[v].begin();it!=m_mapList[v].end();it++)
		{
			T w = it->m_value;
			if (!m_OnStack[w]) 
			{
				hasLoop(w);
			}
			else // 
			{
				m_isHasCycle = true;
			}
		}

		m_OnStack[v] = false; // 取消标记本次已遍历

		return m_isHasCycle;
	}

};

#endif

测试代码

//main.cpp

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

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

using namespace jay;



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

	DirectionGraph<int> gra;

	gra.AddEdge(0,5);
	gra.AddEdge(5,4);
	gra.AddEdge(0,1);
	gra.AddEdge(2,0);
	gra.AddEdge(2,3);
	gra.AddEdge(3,5);
	gra.AddEdge(0,6);
	gra.AddEdge(6,4);

	gra.AddEdge(8,7);
	gra.AddEdge(7,6);
	gra.AddEdge(6,9);
	gra.AddEdge(9,10);
	gra.AddEdge(9,11);
	gra.AddEdge(11,12);
	gra.AddEdge(9,12);

	gra.Show();

	if (!gra.hasLoop())
	{
		gra.TopologicalSort();
	}
	else
	{
		cout << "当前有向图有环,无法做拓扑排序"<<endl;
	}


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

 

暂无评论

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