加权有向图(EdgesWeightDirectionGraph) -- C++实现


实现代码

// EdgesWeightDirectionGraph.h

#ifndef EdgesWeightDirectionGraph_H
#define EdgesWeightDirectionGraph_H

#include "QuickUnionUF_T.h"
#include "Component.h"
#include "PriorityQueueMin.h"

namespace jay{

	template<typename T>
	class EdgesWeightDirectionGraph
	{
	private:

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

		hash_map<T,int> m_indegree;// 入度

	public:

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

		void ResetMarkTag(bool mark = false);

		int VertexCount();

		EdgesWeightDirectionGraph();
		~EdgesWeightDirectionGraph();

	};

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

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

	template<typename T>
	void EdgesWeightDirectionGraph<T>::AddEdge(T v,T w,double weight)
	{
		DirectionEdges<T> edges(v,w,weight);
		m_mapList[v].push_front(edges);

		m_indegree[w]++;
		m_E++;
	}

	template<typename T>
	int EdgesWeightDirectionGraph<T>::VertexCount()
	{
		return m_mapList.size();
	}

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

			for (it2 = it->second.begin(); it2!=it->second.end();it2++)
			{
				cout << it2->To() << "(" << it2->Weight() << ") ";
			}

			cout << endl;

		}
	}
};

#endif

测试代码

//main.cpp

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

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


using namespace jay;



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

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

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

//	gra.Kruskal();
	
//	gra.KosarajuCC();
	

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

 

暂无评论

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