【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表

🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

👉图的基本概念👈

图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：顶点集合V = {x|x属于某个数据对象集}是有穷非空集合；E = {(x,y)|x, y 属于 V}或者E = {<x, y> |x ,y 属于 V && Path(x, y)} 是顶点间关系的有穷集合，也叫做边的集合。注：(x, y) 表示 x 到 y 的一条双向通路，即 (x, y) 是无方向的；Path(x, y) 表示从 x 到 y 的一条单向通路，即 Path(x, y) 是有方向的。

顶点和边：图中结点称为顶点，第 i 个顶点记作 vi。两个顶点 vi 和 vj 相关联称作顶点 vi 和顶点 vj 之间有一条边，图中的第 k 条边记作 ek，ek = (vi，vj) 或 <vi，vj>。

有向图和无向图：在有向图中，顶点对 <x, y> 是有序的，顶点对 <x，y> 称为顶点 x 到顶点 y 的一条边(弧)，<x, y> 和 <y, x> 是两条不同的边，比如下图 G3 和 G4 为有向图。在无向图中，顶点对 (x, y) 是无序的，顶点对 (x,y) 称为顶点 x 和顶点 y 相关联的一条边，这条边没有特定方向，(x, y) 和 (y，x) 是同一条边，比如下图 G1 和 G2 为无向图。注意：无向边 (x, y) 等于有向边 <x, y> 和 <y, x>。

注：数是一种特殊（无环联通）的图，图不一定是树。树关注的是节点（顶点）中存的值，图关注的是顶点及边的权值。

完全图：在有 n 个顶点的无向图中，若有 n * (n - 1) / 2 条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，比如上图 G1；在 n 个顶点的有向图中，若有 n * (n - 1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图（最稠密的图），比如上图 G4。

邻接顶点：在无向图 G 中，若 (u, v) 是 E(G) 中的一条边，则称 u 和 v 互为邻接顶点，并称边 (u,v) 依附于顶点 u 和 v；在有向图 G 中，若 <u, v> 是 E(G) 中的一条边，则称顶点 u 邻接到 v，顶点 v 邻接自顶点 u，并称边 <u, v> 与顶点 u 和顶点 v 相关联。

顶点的度：顶点v的度是指与它相关联的边的条数，记作deg(v)。在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点 v 的入度是以 v 为终点的有向边的条数，记作 indev(v)；顶点 v 的出度是以 v 为起始点的有向边的条数，记作 outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注意：对于无向图，顶点的度等于该顶点的入度和出度，即 dev(v) = indev(v) = outdev(v)。

路径：在图 G = (V， E) 中，若从顶点 vi 出发有一组边使其可到达顶点 vj，则称顶点 vi 到顶点 vj 的顶点序列为从顶点 vi 到顶点 vj 的路径。

路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。

注：在交通网络图中，顶点可以表示城市，边的权值可以表示城市之间的一个关系（高铁距离、高铁价格等）。在社交关系图中，顶点可以表示人，边表示两个人是好友，权值表示亲密度等等。微信和 QQ 上的好友等关系是无向图，是强社交关系；微博和抖音上的博主和粉丝等关系是有向图，是弱社交关系。

简单路径与回路：若路径上各顶点 v1，v2，v3，…，vm 均不重复，则称这样的路径为简单路径。若路径上第一个顶点 v1 和最后一个顶点 vm 重合，则称这样的路径为回路或环。

子图：设图 G = {V, E} 和图 G1 = {V1，E1}，若 V1 属于 V 且 E1 属于 E，则称 G1 是 G 的子图。

连通图：在无向图中，若从顶点 v1 到顶点 v2 有路径，则称顶点 v1 与顶点 v2 是连通的（可以直接相连，也可以间接相连）。如果图中任意一对顶点都是连通的，则称此图为连通图。如果不是连通图，则会存在孤岛。

强连通图：在有向图中，若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从 vj 到 vi的路径，则称此图是强连通图。

生成树：在无向图中，一个连通图的最小连通子图称作该图的生成树。有 n 个顶点的连通图的生成树有 n 个顶点和 n - 1 条边。

👉图的存储结构👈

因为图中既有节点，又有边(节点与节点之间的关系)。因此，在图的存储中，只需要保存节点和边关系即可。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？

邻接矩阵

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

注意：

无向图的邻接矩阵是对称的，第 i 行(列)元素之和，就是顶点 i 的度。有向图的邻接矩阵则不一定是对称的，第 i 行(列)元素之后就是顶点 i 的出(入)度。
如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替。

3. 邻接矩阵的优点：非常适合存储稠密图，用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通并取到权值。缺点：如果顶点比较多，边比较少时，矩阵中存储了大量的 0 成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。相对而言，不适合查找一个顶点的所有边，时间复杂度为 O(顶点个数)。

邻接矩阵的模拟实现

#pragma once
#include <vector>
#include <map>
#include <iostream>
using namespace std;namespace matrix
{// V是顶点,W是权值// 默认权值是INT_MAX,默认是无向图template <class V, class W, W W_MAX = INT_MAX, bool Direction = false>class Graph{public:// 图的创建// 1.IO输入 -- 不方便测试,OJ中更适合// 2.图的结构关系写到文件中,读取文件// 3.手动添加边,方便测试Graph(const V* a, size_t n){// 将顶点集合的空间开好_vertexs.reserve(n);for (size_t i = 0; i < n; ++i){// 建立映射关系_vertexs.push_back(a[i]);_indexMap[a[i]] = i;}// 将邻接矩阵的空间开好_matrix.resize(n);for (size_t i = 0; i < n; ++i){_matrix[i].resize(n, W_MAX);}}// 获得顶点对应的下标size_t GetVertexIndex(const V& v){auto it = _indexMap.find(v);if (it != _indexMap.end())return it->second;else{//assert(false);throw invalid_argument("顶点不存在");return -1;}}void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;// 无向图if (Direction == false)_matrix[dsti][srci] = w;}void Print(){int n = _vertexs.size();// 打印顶点及映射关系for (size_t i = 0; i < n; ++i){cout <<"[" << _vertexs[i] << "]" << "->" << i << endl;}cout << endl;// 打印矩阵列标cout << "  ";for (size_t i = 0; i < _vertexs.size(); ++i){cout << i << " ";}cout << endl;// 打印权值for (size_t i = 0; i < n; ++i){cout << i << " ";	// 打印矩阵行标for (size_t j = 0; j < n; ++j){if (_matrix[i][j] != W_MAX)cout << _matrix[i][j] << " ";elsecout << "*" << " ";}cout << endl;}cout << endl << endl;}private:vector<V> _vertexs;			// 顶点集合map<V, int> _indexMap;		// 顶点映射的下标vector<vector<W>> _matrix;	// 邻接矩阵};void GraphTest(){Graph<char, int, INT_MAX, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();}
}

在这里插入图片描述

邻接表

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

无向图邻接表存储

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

有向图邻接表存储

注意：有向图中每条边在邻接表中只出现一次，与顶点 vi 对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表。想要得到 vi 顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的 dst 取值是 i。

邻接表适合存储稀疏图，适合查找一个顶点连接出去的边，邻接表不适合确定两个顶点是否相连及边的权重。一般情况下，有向图存储出边表即可。

邻接表的实现

#pragma once
#include <vector>
#include <map>
#include <iostream>
#include <string>
using namespace std;namespace linkTable
{template<class W>struct LinkEdge{// 只关心出边//int _srcIndex;	// 起始点下标int _dstIndex;	// 目标点下标W _w;			// 权值LinkEdge<W>* _next;	LinkEdge(int dstIndex, const W& w): _dstIndex(dstIndex), _w(w), _next(nullptr){}};// V是顶点,W是权值// 默认是无向图template <class V, class W, bool Direction = false>class Graph{typedef LinkEdge<W> Edge;public:Graph(const V* a, size_t n){// 将顶点集合的空间开好_vertexs.reserve(n);for (size_t i = 0; i < n; ++i){// 建立映射关系_vertexs.push_back(a[i]);_indexMap[a[i]] = i;}// 将邻接表的空间开好_tables.resize(n, nullptr);}// 获得顶点对应的下标size_t GetVertexIndex(const V& v){auto it = _indexMap.find(v);if (it != _indexMap.end())return it->second;else{//assert(false);throw invalid_argument("顶点不存在");return -1;}}void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);// 头插Edge* eg = new Edge(dsti, w);eg->_next = _tables[srci];_tables[srci] = eg;// 无向图if (Direction == false){eg = new Edge(srci, w);eg->_next = _tables[dsti];_tables[dsti] = eg;}}void Print(){int n = _tables.size();// 顶点for (size_t i = 0; i < n; ++i){cout << "[" << i << "]:" << _vertexs[i] << "->";Edge* cur = _tables[i];while (cur){cout << "[" << cur->_dstIndex << ":" << _vertexs[cur->_dstIndex] << ":" << cur->_w << "]" << "->";cur = cur->_next;}cout << "nullptr" << endl;}cout << endl;}private:vector<V> _vertexs;			// 顶点集合map<V, int> _indexMap;		// 顶点映射的下标vector<Edge*> _tables;		// 邻接表};void GraghTest(){string a[] = { "张三", "李四", "王五", "赵六", "田七" };Graph<string, int, true> g1(a, sizeof(a) / sizeof(string));	// 无向图//Graph<string, int, true> g1(a, sizeof(a) / sizeof(string));	// 有向图g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.AddEdge("王五", "田七", 30);g1.Print();}
}

在这里插入图片描述

👉图的遍历👈

给定一个图 G 和其中任意一个顶点 v0，从 v0 出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。遍历即对结点进行某种操作的意思。

图的广度优先遍历

图的广度优先遍历和树的层序遍历相似，需要借助队列。当前节点出队列，需要将与其相连的节点入队列。如果相连节点已经遍历过了，该节点不能再入队列，所以需要将已遍历过的节点（即入队列的节点）标记一下。

namespace matrix
{// ...class Graph{public:void BFS(const V& src){size_t srci = GetVertexIndex(src);// 队列和标记数组vector<bool> visited(_vertexs.size(), false);queue<int> q;q.push(srci);visited[srci] = true;size_t n = _vertexs.size();while (!q.empty()){int front = q.front();q.pop();cout << "[" << front << ":" << _vertexs[front] << "]" << endl;// front的邻接顶点入队列for (size_t i = front + 1; i < n; ++i){if (_matrix[front][i] != W_MAX){if (visited[i] == false){q.push(i);visited[i] = true;}}}}}}// ...
}

在这里插入图片描述

思路：和二叉树的层序遍历一层一层打印的思路类似，找出一个人的 n 度好友也需要控制一层一层地打印。

namespace matrix
{// ...class Graph{public:void BFS(const V& src){size_t srci = GetVertexIndex(src);// 队列和标记数组vector<bool> visited(_vertexs.size(), false);queue<int> q;q.push(srci);visited[srci] = true;int levelSize = 1;size_t n = _vertexs.size();while (!q.empty()){for (int i = 0; i < levelSize; ++i){int front = q.front();q.pop();cout << "[" << front << ":" << _vertexs[front] << "]" << "  ";// front的邻接顶点入队列for (size_t i = front + 1; i < n; ++i){if (_matrix[front][i] != W_MAX){if (visited[i] == false){q.push(i);visited[i] = true;}}}}cout << endl;levelSize = q.size();}}}// ...
}

在这里插入图片描述

图的深度优先遍历

namespace matrix
{// ...class Graph{public:void DFS(const V& src){size_t srci = GetVertexIndex(src);vector<bool> visited(_vertexs.size(), false);_DFS(srci, visited);}private:void _DFS(size_t srci, vector<bool>& visited){cout << "[" << srci << ":" << _vertexs[srci] << "]" << endl;visited[srci] = true;// 找一个与srci相邻的没有访问过的顶点,进行深度遍历for (size_t i = srci + 1; i < _vertexs.size(); ++i){if (_matrix[srci][i] != W_MAX && visited[i] == false){_DFS(i, visited);}}}// ...
}