加权无向图(EdgesWeightGraph) -- C++实现


实现代码

// EdgesWeightGraph.h

#ifndef EDGESWEIGHTGRAPH_H
#define EDGESWEIGHTGRAPH_H

#include "Component.h"

namespace jay{

	template<typename T>
	class EdgesWeightGraph
	{
	private:

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

	public:

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

		bool hasSelfLoop();

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

};

#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;
	while(cin>>p)
	{
		cin>>q;
		gra.AddEdge(p,q);
	}
	*/

	gra.Show();

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

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

 

暂无评论

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