【数据结构与算法】图——邻接表与邻接矩阵

一、图的基本概念

• 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是顶点的集合，E是边的集合。
• 在图中数据元素，我们则称之为顶点（Vertex）。
• 图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

有上面的定义可以得出树是一个特殊的图，与图的区别是没有环连通。
树关注的是节点（顶点）的值，而图关注的是顶点及边的权值。

• 图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
  

比方说现在想表示社交关系，那么QQ，微信等就是无向图，抖音微博这种就是有向图（你关注的人不一定关注了你）。

• 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
• 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
• 图上的边或弧上带权则称为网。
• 一个图包含了另一个图的部分顶点和部分边，就叫做子图。
  
• 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环（回路），当中不重复叫简单路径。若无向图任意两顶点都是连通的，则图就是连通图，有向则称强连通图。
• 生成树： 在无向图中，一个连通图的最小连通子图称作该图的生成树。有 n 个顶点的连通图的生成树有 n 个顶点和 n-1 条边。
  

二、图的存储结构

一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系 ---- 边或者弧的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两个面的信息。下面介绍两种常用的图的存储结构。这篇介绍两个常见的结构：邻接矩阵和邻接表。

2.1 邻接矩阵

因为节点与节点之间的关系就是联通与否，即为 0 或者 1，因此邻接矩阵（二维数组）即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。

可以看出无向图是对称的，而有向图没有对称关系。
如果边是带权值的且两个顶点不相连，我们可以用INT_MAX或者INT_MIN来表示。

邻接矩阵存储图的优点是能够快速知道图中两个顶点是否连通，缺点是顶点很多且边比较少时，比较浪费空间，并且两个节点之间的路径不好求。若要确定图中有多少条边，需要遍历一遍邻接矩阵，空间复杂度为 O(N^2) 。这是用邻接矩阵来存储图的局限性。

所以邻接矩阵适合存稠密图，适合查找两个顶点是否相连

2.2 邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。

用数组保存顶点，用链表保存连通的顶点。

邻接表适合存稀疏图，适合查找一个顶点连出去的边

2.3 邻接矩阵的实现

邻接矩阵有以下的模板参数：

template <class V, class W, W MAX = INT_MAX, bool DIR = false>

V - 顶点，W - 权值，MAX - 最大值(默认参数给整形的最大值)，DIR - 表示图是否有方向。

template <class V, class W, W MAX = INT_MAX, bool DIR = false>
class Graph
{
public:
private:vector<V> _vertexs;// 顶点集合unordered_map<V, int> _idxMap;// 顶点映射下标vector<vector<W>> _matrix;// 邻接矩阵
};

构造函数
我们传进一个数组和一个size_t型数据，数组里面存放顶点，数据表示数组的大小。
在内部我们首先要把每个顶点存储起来，并初始化邻接矩阵，把权值全部初始化成MAX代表不相连。

Graph(const V* a, size_t n)
{_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);// 将传入数组的值存储到vector中_idxMap[a[i]] = i;// 让数组中的每一个数据映射一个下标}_matrix.resize(n);for (size_t i = 0; i < n; i++){_matrix[i].resize(n, MAX);}
}

添加边

首先要获取两个顶点的下标，然后还要判断是有向图还是无向图，无向图要添加两次。

// 获取顶点下标
size_t GetIdx(const V& v)
{auto it = _idxMap.find(v);if (it == _idxMap.end()){assert(false);return -1;}return it->second;
}void addEdge(const V& src, const V& dst, const W& w)
{size_t si = GetIdx(src);size_t di = GetIdx(dst);_matrix[si][di] = w;if (DIR == false){_matrix[di][si] = w;}
}

打印观察

void Print()
{// 打印矩阵横坐标cout << "  ";for (size_t i = 0; i < _vertexs.size(); ++i){printf("%5d", i);}cout << 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)printf("%5c", '*');elseprintf("%5d", _matrix[i][j]);}cout << endl;}
}

整体代码

template <class V, class W, W MAX = INT_MAX, bool DIR = false>
class Graph
{
public:Graph(const V* a, size_t n){_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);// 将传入数组的值存储到vector中_idxMap[a[i]] = i;// 让数组中的每一个数据映射一个下标}_matrix.resize(n);for (size_t i = 0; i < n; i++){_matrix[i].resize(n, MAX);}}// 获取顶点下标size_t GetIdx(const V& v){auto it = _idxMap.find(v);if (it == _idxMap.end()){assert(false);return -1;}return it->second;}void addEdge(const V& src, const V& dst, const W& w){size_t si = GetIdx(src);size_t di = GetIdx(dst);_matrix[si][di] = w;if (DIR == false){_matrix[di][si] = w;}}void Print(){// 打印顶点和下标间的映射关系for (size_t i = 0; i < _vertexs.size(); ++i){cout << "[" << i << "]" << "->" << _vertexs[i] << endl;}cout << endl;// 打印矩阵横坐标cout << "  ";for (size_t i = 0; i < _vertexs.size(); ++i){printf("%5d", i);}cout << 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)printf("%5c", '*');elseprintf("%5d", _matrix[i][j]);}cout << endl;}}private:vector<V> _vertexs;// 顶点集合unordered_map<V, int> _idxMap;// 顶点映射下标vector<vector<W>> _matrix;// 邻接矩阵
};void TestGraph()
{Graph<char, int, INT_MAX, false> g("ABCDE", 5);g.addEdge('A', 'B', 1);g.addEdge('B', 'D', 4);g.addEdge('A', 'D', 2);g.addEdge('B', 'C', 9);g.addEdge('A', 'C', 8);g.addEdge('E', 'A', 5);g.addEdge('A', 'E', 3);g.addEdge('C', 'D', 6);g.Print();
}

2.4 邻接表的实现

邻接表里面存的是边，所以我们要设计一个边的类。

template <class W>
struct Edge
{Edge(int dsti, const W& w): _dsti(dsti), _w(w), _next(nullptr){}int _dsti;W _w;// 权值Edge<W>* _next;
};

当要加入一个边的时候，直接头插即可。
其他的和邻接矩阵同理。

template <class W>
struct Edge
{Edge(int dsti, const W& w): _dsti(dsti), _w(w), _next(nullptr){}int _dsti;W _w;// 权值Edge<W>* _next;
};template <class V, class W, bool DIR = false>
class Graph
{
public:Graph(const V* a, size_t n){_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);// 将传入数组的值存储到vector中_idxMap[a[i]] = i;// 让数组中的每一个数据映射一个下标}_tables.resize(n, nullptr);}// 获取顶点下标size_t GetIdx(const V& v){auto it = _idxMap.find(v);if (it == _idxMap.end()){assert(false);return -1;}return it->second;}void addEdge(const V& src, const V& dst, const W& w){size_t si = GetIdx(src);size_t di = GetIdx(dst);Edge<W>* eg = new Edge<W>(di, w);eg->_next = _tables[si];_tables[si] = eg;if (DIR == false){Edge<W>* eg = new Edge<W>(si, w);eg->_next = _tables[di];_tables[di] = eg;}}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<W>* cur = _tables[i];while (cur){cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";cur = cur->_next;}cout << "nullptr" << endl;}}private:vector<V> _vertexs;// 顶点集合unordered_map<V, int> _idxMap;// 顶点映射下标vector<Edge<W>*> _tables;// 邻接表
};void TestGraph()
{Graph<char, int, true> g("ABCDE", 5);g.addEdge('A', 'B', 1);g.addEdge('B', 'D', 4);g.addEdge('A', 'D', 2);g.addEdge('B', 'C', 9);g.addEdge('A', 'C', 8);g.addEdge('E', 'A', 5);g.addEdge('A', 'E', 3);g.addEdge('C', 'D', 6);g.Print();
}

三、总结

根据邻接表和邻接矩阵的结构特性可知，当图为稀疏图、顶点较多，即图结构比较大时，更适宜选择邻接表作为存储结构。当图为稠密图、顶点较少时，或者不需要记录图中边的权值时，使用邻接矩阵作为存储结构较为合适。
邻接表和邻接矩阵相辅相成，各有优缺点，是互补的。

---

---