【数据结构】图的存储(邻接矩阵与邻接表)

图的存储结构

因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和边关系即可。

节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？

1. 邻接矩阵

第一种存储结构---->邻接矩阵

邻接矩阵如何保存图的顶点和边呢？

因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：

先用一个数组将顶点保存，然后采用矩阵来表示节点与节点之间的关系（边）

比如：

值为1就表示对应的这两个顶点是连通的，为0就表示两个顶点不连通

那其实观察上面的图我们可以发现：

无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度（边没有权值，只存0/1的情况下，元素和就是度）

有向图的邻接矩阵则不一定是对称的，第i行(列)元素之和就是顶点i 的出(入)度（边没有权值，只存0/1的情况下）

另外呢：

1. 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系（1/0）就用权值代替，如果两个顶点不通，可以使用无穷大代替（后面我们实现的时候就要增加一个表示无穷大的模板参数）

2. 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通，取到权值

3. 缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间；所以邻接矩阵比较适合存储稠密图（边比较多的图），不适合存储稀疏图（边比较少的图） 而且要求两个节点之间的路径不好求； 还有求一个顶点相连的顶点有哪些也不好求（O(N)，这个用后面的邻接表结构存储的话就很好求）。

 在写邻接矩阵存储的代码时遇到了一个值得学习的bug，下面的bug怎么修改

template<class V, class W, W MAX_W = INT_MAX, bool Direction>
//                          参数3有默认值 ↗      ↗ 参数4无默认值

参数 3 (MAX_W) 有默认值，但参数 4 (Direction) 没有。这违反了 C++ 标准。

所以我们把bool Direction移到 这个  W MAX_W = INT_MAX前面就好了，或者添加在后面添加一下默认参数。

接下来我实现一下，下图中这个例子： 

namespace Adjacency_matrix
{// V接受顶点(vertex)的类型，W接受权值的类型，Direction(false无向图，true有向图)template<class V, class W, bool Direction, W MAX_W = INT_MAX>// 有权值的情况下不连通的边权值存INT_MAXclass Graph{public:// "0123" 4 Graph(const V* ver, size_t n){// 存储顶点与下标建立映射_vertexs.reserve(n);for (int i = 0; i < n; i++){_vertexs.push_back(ver[i]);_indexMap[ver[i]] = i;}//给邻接矩阵开空间_matrix.resize(n); // 外向量n大小for (auto& e : _matrix){e.resize(n, MAX_W); // 内向量n大小}}size_t GetVertexIndex(const V& v){auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{cout << "顶点不存在" << endl;return -1;}}void AddEdge(const V& src, const V& dst, const W& w) // src起始顶点，dst终止顶点，w权值{size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);// 添加一条边为A->B,B->A_matrix[srci][dsti] = w;if (Direction == false) // 无向图{_matrix[dsti][srci] = w;}}void DellEdge(const V& src, const V& dst){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);// 删除一条边为A->B,B->A;_matrix[srci][dsti] = 0;if (Direction == false) // 无向图{_matrix[dsti][srci] = 0;}}void Print(){// 打印顶点和下标映射关系for (size_t i = 0; i < _vertexs.size(); ++i){cout << _vertexs[i] << "--" << i << "  ";}cout << endl << endl;// 打印矩阵for (size_t i = 0; i < _matrix.size(); ++i){cout << i << " ";for (size_t j = 0; j < _matrix[i].size(); ++j){if (_matrix[i][j] != MAX_W)cout << _matrix[i][j] << " ";elsecout << "#" << " ";}cout << endl;}cout << endl << endl;}private:vector<V> _vertexs; // 顶点集合vector<vector<W>> _matrix;//存储边的矩阵map<V, int> _indexMap; //顶点和下标建立映射};void test(){Graph<char, int, false, INT_MAX> g("ABCD", 4);g.AddEdge('A', 'B', 1);g.AddEdge('B', 'C', 2);g.AddEdge('C', 'D', 3);g.AddEdge('D', 'A', 4);g.DellEdge('D', 'A');g.Print();}
}

结果展示： 

 

 2. 邻接表 

使用数组存储顶点的集合，使用链表存储顶点的关系（边）。

比如

无向图邻接表存储

一个顶点与哪些顶点相连，相连的顶点就存到这个顶点对应的链表中，当然如果带权的话也要存上对应边的权值。 （每个顶点都有一个对应的链表，多条链表用一个指针数组就可以维护起来）

注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点vi 对应链表集合中结点的数目即可

有向图邻接表存储：

那通过上面的了解其实我们可以得出，对于邻接表的存储方式 

1. 适合存储稀疏图（边比较少的图），因为邻接表的话有多少边链表里面就存几个对应的顶点，不需要额外的空间；而上面邻接矩阵不论边多边少都要开一个N*N的矩阵（二维数组），边少的时候那就大部分位置都存的是0

2. 方便查找从一个顶点连接出去的边有哪些，因为它对应的边链表里面存的就是与这个顶点相连的顶点

3. 但是不方便确定两个顶点是否相连和获取权值（要遍历其中一个顶点的边链表查找O(N)）

代码实现方式： 

namespace link_table
{template<class W>struct Edge{size_t _dsti; // 边的终止顶点下标W _w;	   // 权值Edge<W>* _next;Edge(const size_t& dsti, const W& w):_dsti(dsti),_w(w),_next(nullptr){}};// V接受顶点(vertex)的类型，W接受权值的类型，Direction(false无向图，true有向图)template<class V, class W, bool Direction = false>class Graph{typedef Edge<W> Edge;public:// "0123"  4Graph(const V* ver, size_t n){//存储顶点并与下标建立映射_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(ver[i]);_indexMap[ver[i]] = i;}// 给邻接表开空间_tables.resize(n, nullptr);}~Graph(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){Edge* cur = _tables[i];Edge* next = cur;while (cur){next = cur->_next;delete cur;cur = next;}}}}size_t GetVertexIndex(const V& v){auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{cout << "顶点不存在" << endl;return -1;}}void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);// src -> dst  A -> BEdge* eg = new Edge(dsti, w);eg->_next = _tables[srci];_tables[srci] = eg;// 如果是无向图，再添加反向边dst->srcif (Direction == false){Edge* eg = new Edge(srci, w);eg->_next = _tables[dsti];_tables[dsti] = eg;}}void DelEdge(const V& src, const V& dst){del(src, dst);// 如果是无向图，再添加反向边dst->srcif (Direction == false){del(dst, src);}}void Print(){// 打印顶点for (size_t i = 0; i < _vertexs.size(); ++i){cout << "[" << i << "]" << "->" << _vertexs[i] << endl;}cout << endl;// 遍历打印每个顶点的边链表for (size_t i = 0; i < _tables.size(); ++i){cout << _vertexs[i] << "[" << i << "]->";Edge* cur = _tables[i];while (cur){cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";cur = cur->_next;}cout << "nullptr" << endl;}}private:void del(const V& src, const V& dst){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);// A -> B -> C 删除A->B// 1.先判断这个边在不在，如果在就删除，不在就返回Edge* cur = _tables[srci];Edge* per = cur;while (cur){// 如果找到了if (cur->_dsti == dsti){// 如果在头if (per == cur){_tables[srci] = per->_next;delete cur;break;}else{// 如果在尾和中间per->_next = cur->_next;delete cur;break;}}// 如果没找到per = cur;cur = cur->_next;}}private:vector<V> _vertexs;		// 顶点集合map<V, size_t> _indexMap;	// 顶点和下标建立映射vector<Edge*> _tables;	// 邻接表};void Test2(){string a[] = {"张三","李四","王五","赵六"};Graph<string, size_t> g1(a, 4);g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 100);g1.AddEdge("张三", "赵六", 100);g1.AddEdge("王五", "赵六", 100);g1.Print();}
}

结果展示：