数据结构:图的代码-创新互联

直接上代码：代码里面有注释

#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 < _vertexSize; ++i)
		{
			// 初始化矩阵
			_matrix[i] = new W[_vertexSize];
			memset(_matrix[i], 0, sizeof(W)*_vertexSize);

			// 初始化边集
			_vertexs[i] = vertexs[i];
		}
	}

	int GetVertexIndex(const V& vtx)
	{
		for (int i = 0; i < _vertexSize; ++i)
		{
			if (_vertexs[i] == vtx)
			{
				return i;
			}
		}

		return -1;
	}

	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)
		{
			_matrix[srcIndex][dstIndex] = weight;
		}
		else
		{
			_matrix[srcIndex][dstIndex] = weight;
			_matrix[dstIndex][srcIndex] = weight;
		}
	}

	void Display()
	{
		for (int i = 0; i < _vertexSize; ++i)
		{
			cout<<_vertexs[i]<<" ";
		}
		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();
}

// 有向图
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 < rhs->_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 < size; ++i)
		{
			_vertexs[i] = ar[i];
		}
	}

public:
	int GetVertexIndex(const V& vertex)
	{
		for (int i = 0; i < _vertexs.size(); ++i)
		{
			if(_vertexs[i] == vertex)
				return i;
		}

		return -1;
	}

	void _AddEdge(int srcIndex, int dstIndex, const W& weight)
	{
		LinkEdge* 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 < _vertexs.size(); ++i)
		{
			cout<<_vertexs[i]<<"["<";
			LinkEdge* begin = _linkTables[0];
			while (begin)
			{
				cout<_weight<<"["<_dstIndex<<"]""->";
				begin = begin->_next;
			}

			cout<<"NULL"<* _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<<"DFS:";

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

		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			if (visited[i] == false)
			{
				// 1.访问当前节点
				cout<<_vertexs[i]<<" ";
				visited[i] = true;

				_DFS(i, visited);
			}
		}

		delete[] visited;

		cout<* edge = _linkTables[src];

		// 3.依次获取临接表后面的顶点进行深度优先遍历
		while (edge)
		{
			if (visited[edge->_dstIndex] == false)
			{
				cout<<_vertexs[edge->_dstIndex]<<" ";
				visited[edge->_dstIndex] = true;

				_DFS(edge->_dstIndex, visited);
			}

			edge = edge->_next;
		}
	}

	void BFS()
	{
		cout<<"BFS:";
		bool* visited = new bool[_vertexs.size()];
		memset(visited, false, sizeof(bool)*_vertexs.size());

		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			if (visited[i] == false)
			{
				_BFS(i, visited);
			}
		}

		delete[] visited;

		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[edge->_dstIndex]<<" ";

					visited[edge->_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 < _vertexs.size(); ++i)
		{
			LinkEdge* begin = _linkTables[i];
			while (begin)
			{
				// 无向图的边需要进行过滤
				if (begin->_srcIndex < begin->_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 < _vertexs.size())
			{
				edge = minHeap.Top();
				minHeap.Pop();
				if (visitedSet[edge->_dstIndex] == false)
				{
					minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex,edge->_weight);
					visitedSet[edge->_dstIndex] = true;
					src = edge->_dstIndex;
					++count;

					break;
				}  
			}
		}while (count < _vertexs.size());

		return true;
	}

	W _GetWeight(int src, int dst, const W& maxValue)
	{
		if (src == dst)
			return maxValue;

		LinkEdge* 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 < size; ++i)
		{
			dist[i] = _GetWeight(src, i, maxValue);
			path[i] = src;
			vSet[i] = false;
		}

		// 将src加入集合
		vSet[src] = true;

		int count = size;
		while(count--)
		{
			//
			// 选出与src顶点连接的边中最小的边
			// src->min
			W min = maxValue;
			int minIndex = src;
			for (int j = 0; j < size; ++j)
			{
				if (vSet[j] == false && dist[j] < min)
				{
					minIndex = j;
					min = dist[j];
				}
			}

			vSet[minIndex] = true;
			for (int k = 0; k < size; ++k)
			{
				if(k == src)
					continue;

				//  
				// 更新src->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 < dist[k])
				{
					dist[k] = dist[minIndex] + w;
					path[k] = minIndex;
				}
			}
		}
	}

	void _Dijkstra_OP(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 < size; ++i)
		{
			dist[i] = _GetWeight(src, i, maxValue);
			path[i] = src;
			vSet[i] = false;
		}

		struct Compare
		{
			bool operator()(const pair& lhs, const pair& rhs)
			{
				return lhs.first < rhs.first;
			}
		};

		Heap, Compare> minHeap;
		for (int i = 0; i < size; ++i)
		{
			if (dist[i] < maxValue)
			{
				minHeap.Push(make_pair(dist[i], i));
			}
		}

		// 将src加入集合
		vSet[src] = true;

		int count = size;
		while(count--)
		{
			//
			// 选出与src顶点连接的边中最小的边
			// src->min

			if (minHeap.Empty())
				continue;

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

			vSet[minIndex] = true;
			for (int k = 0; k < size; ++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 < dist[k])
				{
					dist[k] = dist[minIndex] + w;
					path[k] = minIndex;

					minHeap.Push(make_pair(dist[k], k));
				}
			}
		}
	}

	void PrintPath(int src, W* dist, int* path, int size)
	{
		int* vPath = new int[size];
		for (int i = 0; i < size; ++i)
		{
			if (i != src)
			{
				int index = i, count = 0;
				do{
					vPath[count++] = index;
					index = path[index];
				}while (index != src);

				vPath[count++] = src;

				//cout<<"顶点："<<_linkTable[src]._vertex\
				<<"->顶点："<<_linkTable[i]._vertex<<"的路径为：";
				cout<";
					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);
}

以上

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。