有向图(DirectionGraph) -- 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; // 入度数
	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);

		DirectionGraph();
		~DirectionGraph();

	};

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

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

	template<typename T>
	int DirectionGraph<T>::Indegree(T v )
	{
		hash_map<T,int>::iterator it;
		it = m_iInDegree.begin();
		if (m_iInDegree.find(v) == m_iInDegree.end())
		{
			// 如果顶点不存在
			return 0;
		}
		return m_iInDegree[v];
	}

	template<typename T>
	int DirectionGraph<T>::Outdegree(T v )
	{
		hash_map<T,int>::iterator it;
		it = m_mapList.begin();
		if (m_mapList.find(v) == m_mapList.end())
		{
			// 如果顶点不存在
			return 0;
		}
		return m_mapList[v].Size();
	}

	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>::Reverse(DirectionGraph<T> &tmp)
	{

		hash_map<T,LinkList<T> >::iterator it;
		for (it = m_mapList.begin(); it!= m_mapList.end();it++)
		{
			T v = it->first;
			LinkList<T>::iterator it2;
			for (it2 = m_mapList[v].begin(); it2 != m_mapList[v].end();it2++)
			{
				T w = it2->m_value;
				tmp.AddEdge(w,v);
			}
		}


	}

};

#endif

 

暂无评论

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