图的存储结构(邻接矩阵和邻接表)的实现(C++)

简介

图的存储

邻接矩阵

邻接表

完整代码

简介

        图是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树结构中，数据元素之间有着明显的层次关系，并且每一层中的数据元素可能和下一层中的多个元素 ( 其孩子结点 ) 相关，但只能和上一层中一个元素 ( 其双亲结点 ) 相关；而在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素都可能相关。

        由于图的结构比较复杂，任意两个顶点都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但其可以借助二维数组来表示元素之间的关系，即采用邻接矩阵表示法。另一方面，由于图的任意两个顶点都可能存在关系，因此，用链式存储表示图是很自然的事，图的链式存储有多种，有邻接表、十字链表和邻接多重表，应根据实际需要的不同选择不同的存储结构。

图的存储

图中既有节点，又有边 ( 节点与节点之间的关系 ) ，因此，在图的存储中，要保存结点以及节点和边关系。

这里展示邻接矩阵表示法和邻接表表示法。

如图所示，给定这样一个图，将其存储。

邻接矩阵

首先定义出存储结构：

// 邻接矩阵
namespace Matrix
{
	// 用非类型形参Direction表示无向图或有向图，默认为无向图
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	public:


    private:
	    map<V, int> _indexMap;	    // 顶点对应的下标关系
	    vector<V> _vertexs;		    // 顶点集合
	    vector<vector<W>> _matrix;  // 边的集合--邻接矩阵
    };
}

接着实现初始化：通过存储顶点的字符串构建出图的初始状态。

例如：

Graph<char, int> g("12345678", 8);

 因此，代码实现为：

Graph(const V* a, int n)
{
	_vertexs.reserve(n);

	for (int i = 0; i < n; i++)
	{
		_vertexs.push_back(a[i]);
		_indexMap[a[i]] = i;
	}

	_matrix.resize(n);

	for (auto& e : _matrix)
	{
		e.resize(n, MAX_W);
	}
}

接着实现添加边的操作：通过传入两个顶点及其之间的权值，将其存储在邻接矩阵中。

例如：

g.AddEdge('1', '3', 5);

由于矩阵是根据下标来确定位置的，所以还要实现一个通过顶点找其对应的下标的函数，方便调用。

// 通过顶点找对应的下标
int GetVertexIndex(const V& vertex)
{
	auto it = _indexMap.find(vertex);
	if (it != _indexMap.end())
	{
		return it->second;
	}
	else
	{
		assert(false);
		return -1;
	}
}

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

	_matrix[indexsrc][indexdst] = weight;

	if (Direction == false)
	{
		_matrix[indexdst][indexsrc] = weight;
	}
}

邻接表

邻接表是存储的是结构体指针，用于记录每一个与该位置相连的顶点和边之间的信息。

首先定义出存储边的结构体：

template<class W>
struct Edge
{
	Edge(int dsti, const W& weight)
		:_dsti(dsti)
		,_weight(weight)
		,_next(nullptr)
	{}

	int _dsti;
	W _weight;
	Edge<W>* _next;
};

接着定义存储结构：

namespace LinkTable
{
	template<class W>
	struct Edge
	{
		Edge(int dsti, const W& weight)
			:_dsti(dsti)
			,_weight(weight)
			,_next(nullptr)
		{}

		int _dsti;
		W _weight;
		Edge<W>* _next;
	};

	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:

	private:
		map<V, int> _indexMap;	    // 顶点对应的下标关系
		vector<V> _vertexs;		    // 顶点集合
		vector<Edge*> _linktable;   // 边的集合--邻接表
	};
}

初始化图：

Graph(const V* a, int n)
{
	_vertexs.reserve(n);
	for (int i = 0; i < n; i++)
	{
		_vertexs.push_back(a[i]);
		_indexMap[a[i]] = i;
	}

	_linktable.resize(n, nullptr);
}

添加边：

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

	Edge* edge = new Edge(indexdst, weight);
	edge->_next = _linktable[indexsrc];
	_linktable[indexsrc] = edge;

	if (Direction == false)
	{
		Edge* edge1 = new Edge(indexsrc, weight);
		edge1->_next = _linktable[indexdst];
		_linktable[indexdst] = edge1;
	}
}

完整代码

// 邻接矩阵
namespace Matrix
{
	// 用非类型形参Direction表示无向图或有向图，默认为无向图
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	public:
		Graph(const V* a, int n)
		{
			_vertexs.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
			}

			_matrix.resize(n);
			for (auto& e : _matrix)
			{
				e.resize(n, MAX_W);
			}
		}

		// 通过顶点找对应的下标
		int GetVertexIndex(const V& vertex)
		{
			auto it = _indexMap.find(vertex);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				assert(false);
				return -1;
			}
		}

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

			_matrix[indexsrc][indexdst] = weight;

			if (Direction == false)
			{
				_matrix[indexdst][indexsrc] = weight;
			}
		}

	private:
		map<V, int> _indexMap;	    // 顶点对应的下标关系
		vector<V> _vertexs;		    // 顶点集合
		vector<vector<W>> _matrix;  // 边的集合--邻接矩阵
	};
}

// 邻接表
namespace LinkTable
{
	template<class W>
	struct Edge
	{
		Edge(int dsti, const W& weight)
			:_dsti(dsti)
			,_weight(weight)
			,_next(nullptr)
		{}

		int _dsti;
		W _weight;
		Edge<W>* _next;
	};

	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		Graph(const V* a, int n)
		{
			_vertexs.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
			}

			_linktable.resize(n, nullptr);
		}

		// 通过顶点找对应的下标
		int GetVertexIndex(const V& vertex)
		{
			auto it = _indexMap.find(vertex);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				assert(false);
				return -1;
			}
		}

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

			Edge* edge = new Edge(indexdst, weight);
			edge->_next = _linktable[indexsrc];
			_linktable[indexsrc] = edge;

			if (Direction == false)
			{
				Edge* edge1 = new Edge(indexsrc, weight);
				edge1->_next = _linktable[indexdst];
				_linktable[indexdst] = edge1;
			}
		}

	private:
		map<V, int> _indexMap;	    // 顶点对应的下标关系
		vector<V> _vertexs;		    // 顶点集合
		vector<Edge*> _linktable;   // 边的集合--邻接表
	};
}