图的自环/平行边(重边)的计算 -- C++实现


实现代码

// GraphUpgrade.h
// 无向图升级版
#ifndef GRAPHUPGRADE_H
#define GRAPHUPGRADE_H

#include "Component.h"

namespace jay{

	template<typename T>
	class GraphUpgrade
	{
	private:

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

		int m_iCountCC; //联通分量的个数

		hash_map<T,bool> m_marked; // 是否已遍历
		hash_map<T,T> m_edgeTo;
		T m_DFSVertex;
		hash_map<T,int> m_distTo; //  这里记录当前顶点到起点的距离(边的个数)
		hash_map<T,LinkList<T> > m_iCCid; // 分量ID(以分量的首顶点做ID) 和 其联通的分量顶点
		hash_map<int,int> m_iSizeCC;

		T m_CurrentIDCC;

		queue<T> m_cycle;
		void ClearQueue(queue<T>& q) ;
	public:

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

		queue<T> GenerateConnectedComponent();
		void ShowComponent(T v);

		void DeepFristSearch(T v);
		void DFS(T v);
		bool isConnectTo(T v);
		void ShowPathTo(T v);

		void Show();

		bool hasSelfLoop(); // 是否存在自环
		bool hasParallelEdges(); // 是否存在平行边

		void ResetMarkTag(bool mark = false);

		GraphUpgrade();
		~GraphUpgrade();

	};

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

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

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

		m_marked[v] = false;
		m_marked[w] = false;
	}

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

	template<typename T>
	bool GraphUpgrade<T>::hasSelfLoop()
	{
		ClearQueue(m_cycle);
		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 = it->second.begin(); it2 != it->second.end(); it2++) 
			{
				// 如果邻接顶点和顶点一样,则说明存在自环
				if (v == it2->m_value) 
				{
					m_cycle.push(v);
					m_cycle.push(v);
					return true;
				}
			}
		}
		return false;
	}

	template<typename T>
	void GraphUpgrade<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>
	bool GraphUpgrade<T>::hasParallelEdges()
	{
		ClearQueue(m_cycle);
		ResetMarkTag();

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

		// 遍历所有顶点
		for (it2 = m_mapList.begin(); it2 != m_mapList.end(); it2++) 
		{
			T v = it2->first;
			LinkList<T>::iterator it3;
			// 遍历顶点v的邻接顶点
			for (it3 = it2->second.begin(); it3 != it2->second.end(); it3++) 
			{
				// 如果等于v是自环
				if (m_marked[it3->m_value] && it3->m_value != v ) 
				{
					// 对于同一个顶点的邻接矩阵,如果当前邻接顶点已被遍历过,则说明存在平行边
					m_cycle.push(v);
					m_cycle.push(it3->m_value);
					m_cycle.push(v);
					return true;
				}
				else
				{
					// 如果当前邻接顶点没有被遍历过,则标记遍历
					m_marked[it3->m_value] = true;
				}
				
			}

			// 对于顶点v来说,不存在平行边
			ResetMarkTag();
		}

		return false;
	}


	template<typename T>
	void GraphUpgrade<T>::DFS(T v)
	{
		DeepFristSearch(v);
	}

	template<typename T>
	void GraphUpgrade<T>::DeepFristSearch(T v)
	{
		m_marked[v] = true;//marked数组保存的值如果为True则代表dfs算法有到达该顶点,说明了该顶点和起点是连通的,所以hasPathTo要查询某一顶点v是否和起点连通直接返回marked[v]的值即可
		m_iCCid[m_CurrentIDCC].Add(v);
		LinkList< T>::iterator it;
		for (it = m_mapList[v].begin();it!=m_mapList[v].end();it++)
		{
			if (!m_marked[it->m_value]) 
			{
				DeepFristSearch(it->m_value);
			}
		}
	}

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

	template<typename T>
	void GraphUpgrade<T>::ShowPathTo(T v)
	{
		if (!isConnectTo(v))
		{
			cout << "当前DFS顶点和指定顶点不连通" << endl;
			return;
		}

		T tmpold = v;

		stack<T> myStack;
		for (T tmp = v;v !=m_DFSVertex;v = m_edgeTo[v])
		{
			myStack.push(v);
		}
		myStack.push(m_DFSVertex);

		while (!myStack.empty())
		{
			T tmp = myStack.top();
			cout << tmp;
			if (tmp != tmpold)
			{
				cout << " -> ";
			}
			myStack.pop();
		}

		cout << endl;
	}


	template<typename T>
	void GraphUpgrade<T>::DeleteEdge(T v,T w )
	{
		m_mapList[v].Delete(w);
		m_mapList[w].Delete(v);

		m_E--;
	}

	// 删除顶点
	template<typename T>
	void GraphUpgrade<T>::DeleteVertex(T v)
	{
		// 获取和v已连通的顶点
		// LinkList<T> deleteV = m_mapList[v];

		LinkList<T>::iterator it;
		for(it = m_mapList[v].begin();it != m_mapList[v].end();it++)
		{
			m_mapList[it->m_value].Delete(v); // 从其他顶点删除v
		}

		for(int i=0;i<m_mapList[v].Size();i++ )
		{
			T BUF = m_mapList[v].Get(0);
			m_mapList[v].Delete(BUF); // 从v删除其他顶点
		}

		// 删除顶点v
		m_mapList.erase(v);
	}

	template<typename T>
	void GraphUpgrade<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();
		}
	}
};

#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"

using namespace jay;



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

	GraphUpgrade<int> gra;
	gra.AddEdge(0,5);
	gra.AddEdge(4,3);
	gra.AddEdge(0,1);
	gra.AddEdge(9,12);
	gra.AddEdge(6,4);
//	gra.AddEdge(6,4);
	gra.AddEdge(5,4);
	gra.AddEdge(0,2);
	gra.AddEdge(11,12);
	gra.AddEdge(9,10);
	gra.AddEdge(0,6);
	gra.AddEdge(7,8);
	gra.AddEdge(9,11);
	gra.AddEdge(5,3);
//	gra.AddEdge(5,5);
	gra.Show();

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

	
	
}

 

暂无评论

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