简单无向图(GraphUpgrade) -- C++实现 升级代码


使用stl的自带hash_map做底层结构,可以处理大多数数据类型的图。支持删除边/删除顶点

实现代码

// 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; // 边的数量

	public:

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

		void Show();

		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++;
	}

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

// 		// 如果当前顶点的连通顶点为空,则删除该顶点
// 		if (m_mapList[v].Size() == 0)
// 		{
// 			m_mapList.erase(v);
// 		}
// 
// 		// 如果当前顶点的连通顶点为空,则删除该顶点
// 		if (m_mapList[w].Size() == 0)
// 		{
// 			m_mapList.erase(w);
// 		}

		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>
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(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.Show();
	cout << "-----------------------------" <<endl;
	gra.DeleteVertex(6);
	gra.Show();
	cout << "-----------------------------" <<endl;
	gra.DeleteEdge(1,0);
	gra.Show();

}

 

暂无评论

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