데이터 구조: 그림 의 코드

#pragma once

#include 
#include 
#include "Heap.hpp"
#include "UnionFindSet.hpp"

//
//          &   
//

template
class GraphMatrix
{
public:
	GraphMatrix(const V* vertexs, int size, bool isDirected)
		:_vertexSize(size)
		,_isDirected(isDirected)
	{
		//        
		_matrix = new W*[_vertexSize];
		_vertexs = new V[_vertexSize];

		for (int i = 0; i  g("ABCDE", 5, false);
	g.AddEdge('A', 'D', 10);
	g.AddEdge('A', 'E', 20);
	g.AddEdge('B', 'C', 10);
	g.AddEdge('B', 'D', 20);
	g.AddEdge('B', 'E', 30);
	g.AddEdge('C', 'E', 40);

	g.Display();
}

//    
void Test2()
{
	GraphMatrix g("ABCDE", 5, true);
	g.AddEdge('A', 'D', 10);
	g.AddEdge('E', 'A', 20);
	g.AddEdge('B', 'C', 10);
	g.AddEdge('D', 'B', 20);
	g.AddEdge('E', 'B', 30);
	g.AddEdge('C', 'E', 40);

	g.Display();
}

//
//    
//

template
struct LinkEdge
{
	int _srcIndex;			//      
	int _dstIndex;			//       
	W _weight;				//   
	LinkEdge* _next;	//            

	LinkEdge(int srcIndex = -1, int dstIndex = -1, const W& weight = W())
		:_srcIndex(srcIndex)
		,_dstIndex(dstIndex)
		,_weight(weight)
		,_next(NULL)
	{}
};

template
struct CompareLinkEdge
{
	bool operator()(LinkEdge* lhs, LinkEdge* rhs)
	{
		return lhs->_weight _weight;
	}
};

template
class GraphLink
{
protected:
	vector _vertexs;						//     
	vector*> _linkTables;		//    
	bool _isDirected;						//       
public:
	GraphLink(bool isDirected = false)
		:_isDirected(isDirected)
	{}

	GraphLink(const V* ar, int size, bool isDirected = false)
		:_isDirected(isDirected)
	{
		_vertexs.resize(size);
		_linkTables.resize(size);
		for (size_t i = 0; i * tmp = new LinkEdge(srcIndex, dstIndex, weight);

		tmp->_next = _linkTables[srcIndex];
		_linkTables[srcIndex] = tmp;
	}

	void AddEdge(const V& src, const V& dst, const W& weight)
	{
		int srcIndex = GetVertexIndex(src);
		int dstIndex = GetVertexIndex(dst);

		assert(srcIndex != -1);
		assert(dstIndex != -1);

		//    
		if(_isDirected)
		{
			_AddEdge(srcIndex, dstIndex, weight);
		}
		else
		{
			_AddEdge(srcIndex, dstIndex, weight);
			_AddEdge(dstIndex, srcIndex, weight);
		}
	}

	void Display()
	{
		for (int i = 0; i ";
			LinkEdge* begin = _linkTables[0];
			while (begin)
			{
				cout<_weight<_dstIndex<";
				begin = begin->_next;
			}

			cout<* _GetNextEdge(int src, int cur)
	{
		LinkEdge* edge = _linkTables[src];
		while (edge)
		{
			if (edge->_dstIndex == cur)
			{
				return edge->_next;
			}
			edge = edge->_next;
		}

		return NULL;
	}

	void DFS()
	{
		cout<* edge = _linkTables[src];

		// 3.                    
		while (edge)
		{
			if (visited[edge->_dstIndex] == false)
			{
				cout<<_vertexs>_dstIndex]<_dstIndex] = true;

				_DFS(edge->_dstIndex, visited);
			}

			edge = edge->_next;
		}
	}

	void BFS()
	{
		cout< q;
		q.push(cur);
		while (!q.empty())
		{
			cur = q.front();
			q.pop();

			LinkEdge* edge = _linkTables[cur];
			while (edge)
			{
				if (visited[edge->_dstIndex] == false)
				{
					cout<<_vertexs>_dstIndex]<_dstIndex] = true;
					q.push(edge->_dstIndex);
				}

				edge = edge->_next;
			}
		}
	}

	bool Kruskal(GraphLink& minSpanTree)
	{
		// 1.        
		minSpanTree._vertexs = _vertexs;
		minSpanTree._linkTables.resize(_vertexs.size());
		minSpanTree._isDirected = _isDirected;

		//
		// 2.            
		//    V   ，E  
		// 
		Heap*, CompareLinkEdge> minHeap;
		for (int i = 0; i * begin = _linkTables[i];
			while (begin)
			{
				//            
				if (begin->_srcIndex _dstIndex)
				{
					minHeap.Push(begin);
				}

				begin = begin->_next;
			}
		}
		
		// 3.                
		UnionFindSet UFSet(_vertexs.size());
		int count = _vertexs.size();
		while (--count)
		{
			if (minHeap.Empty())
			{
				return false;
			}

			LinkEdge* edge = minHeap.Top();
			minHeap.Pop();
			int src = UFSet.FindRoot(edge->_srcIndex);
			int dst = UFSet.FindRoot(edge->_dstIndex);

			if(src != dst)
			{
				UFSet.Union(src, dst);
				minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex, edge->_weight);
			}
		}

		return true;
	}

	bool Prim(GraphLink& minSpanTree)
	{
		// 1.        
		minSpanTree._vertexs = _vertexs;
		minSpanTree._linkTables.resize(_vertexs.size());
		minSpanTree._isDirected = _isDirected;

		bool* visitedSet = new bool[_vertexs.size()];
		memset(visitedSet, false, sizeof(bool)*_vertexs.size());

		int src = 0;
		visitedSet[src] = true;
		Heap*, CompareLinkEdge> minHeap;

		int count = 1;
		do 
		{
			// 2.                         
			LinkEdge* edge = _linkTables[src];
			while(edge)
			{
				if (visitedSet[edge->_dstIndex] == false)
				{
					minHeap.Push(edge);
				}

				edge = _GetNextEdge(src, edge->_dstIndex);
			}

			// 2.             
			while(!minHeap.Empty() && count _dstIndex] == false)
				{
					minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex,edge->_weight);
					visitedSet[edge->_dstIndex] = true;
					src = edge->_dstIndex;
					++count;

					break;
				}  
			}
		}while (count * edge = _linkTables[src];
		while (edge)
		{
			if (edge->_dstIndex == dst)
			{
				return edge->_weight;
			}

			edge = edge->_next;
		}

		return maxValue;
	}

	//         --Dijkstra(    )
	//  src          
	void _Dijkstra(int src, W* dist, int* path, bool* vSet, int size, const W& maxValue)
	{
		//
		// 1.dist   src         
		// 2.path   src        
		// 3.       
		//
		for (int i = 0; i min
			W min = maxValue;
			int minIndex = src;
			for (int j = 0; j k   
				//   dist(src,min)+dist(min, k)     dist(src, k)
				//    dist(src,k) path(src->min->k)
				//
				W w = _GetWeight(minIndex, k, maxValue);
				if (vSet[k] == false && dist[minIndex] + w & lhs, const pair& rhs)
			{
				return lhs.first , Compare> minHeap;
		for (int i = 0; i min

			if (minHeap.Empty())
				continue;

			int minIndex = minHeap.Top().second;
			minHeap.Pop();

			vSet[minIndex] = true;
			for (int k = 0; k min)+dist(min, k)     dist(src, k)
				//    dist(src,k) path(src->min->k)
				//
				W w = _GetWeight(minIndex, k, maxValue);
				if (vSet[k] == false && dist[minIndex] + w   ："<<_linktable cout="" while="">";
					cout<";
				}

				cout< g("ABCDE", 5, false);
	g.AddEdge('A', 'D', 10);
	g.AddEdge('A', 'E', 20);
	g.AddEdge('B', 'C', 10);
	g.AddEdge('B', 'D', 20);
	g.AddEdge('B', 'E', 30);
	g.AddEdge('C', 'E', 40);
	g.Display();

	//        
	GraphLink minSpanTree1(false);
	g.Kruskal(minSpanTree1);

	minSpanTree1.Display();

	//        
	GraphLink minSpanTree2(false);
	g.Prim(minSpanTree2);
	minSpanTree2.Display();

	g.DFS();
	g.BFS();
}

//    
void Test4()
{
	GraphLink g("ABCDE", 5, true);
	g.AddEdge('A', 'D', 10);
	g.AddEdge('E', 'A', 20);
	g.AddEdge('B', 'C', 10);
	g.AddEdge('D', 'B', 20);
	g.AddEdge('E', 'B', 30);
	g.AddEdge('C', 'E', 40);

	g.AddEdge('A', 'C', 50);
	g.AddEdge('A', 'E', 50);

	g.Display();

	g.Dijkstra(0, 10000);
	//g.Dijkstra(1, 10000);
}