图的基本概念及其存储结构（邻接矩阵和邻接表）
2024年8月15日 | 分类: 【编程】这篇文章开始，我们来学习一种高阶数据结构——图
1. 图的基本概念
1.1 什么是图
图是由顶点集合及顶点间的关系（边）组成的一种数据结构：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>。
1.2 有向图和无向图
图分为有向图和无向图
有向图中，顶点对<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>。
简单总结一下：
图是一种非线性的数据结构，用于表示元素之间的关系。它由节点（也称为顶点）和连接节点的边组成。每个节点可以与其他节点直接或间接连接，这些连接关系可以具有方向性（有向图）或无方向性（无向图）。因此，图可用于表示各种关系，如网络、社交关系、地图等，并且在计算机科学和现实生活中有广泛的应用。
1.3 完全图
在有n个顶点的无向图中，若有
n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，比如上图G1
在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有两条方向相反的边，则称此图为有向完全图，比如上图G4
1.4 邻接顶点
在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；
在有向图G中，若<u, v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。
1.5 顶点的度
顶点v的度是指与它相关联的边的条数，记作deg(v)。
在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记作indev(v)；顶点v的出度是以v为起始点的有向边的条数，记作outdev(v)。因此：dev(v) = indev(v) + outdev(v)。
注意：对于无向图，顶点的度等于该顶点的入度和出度，即dev(v) = indev(v) = outdev(v)。
1.6 路径
在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。
比如，在上面这个有向图中，顶点1到顶点7的路径有：
1，3，6，7
1，4，7
可能有多条
1.7 路径长度
对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和
1.8 简单路径与回路
若路径上各顶点v1，v2，v3，…，vm均不重复，则称这样的路径为简单路径。
若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。
1.9 子图
设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图（即G1的顶点和边都是原图的一部分，当然这些顶点和边必须构成一个图）
1.10 连通图
在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的；
如果图中任意一对顶点都是连通的，则称此图为连通图。
1.11 强连通图
在有向图中，若每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的路径，则称此图是强连通图
1.12 生成树
无向图中，一个连通图的最小连通子图称作该图的生成树。
有n个顶点的连通图的生成树有n个顶点和n-1条边。
比如：
2. 图的存储结构
因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和边关系即可。
节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？
2.1 邻接矩阵
首先我们来学习图的第一种存储结构——邻接矩阵
那邻接矩阵是如何保存图的顶点和边呢？
因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将顶点保存，然后采用矩阵来表示节点与节点之间的关系（边）
比如：
值为1就表示对应的这两个顶点是连通的，为0就表示两个顶点不连通
那其实观察上面的图我们可以发现：
无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度（边没有权值，只存0/1的情况下，元素和就是度）
有向图的邻接矩阵则不一定是对称的，第i行(列)元素之和就是顶点i 的出(入)度（边没有权值，只存0/1的情况下）
另外呢：
1. 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系（1/0）就用权值代替，如果两个顶点不通，可以使用无穷大代替（后面我们实现的时候就要增加一个表示无穷大的模板参数）
2. 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通，取到权值
3. 缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为稀疏矩阵，比较浪费空间；所以邻接矩阵比较适合存储稠密图（边比较多的图），不适合存储稀疏图（边比较少的图）
而且要求两个节点之间的路径不好求；
还有求一个顶点相连的顶点有哪些也不好求（O(N)，这个用后面的邻接表结构存储的话就很好求）。
2.2 邻接矩阵代码实现
那下面我们就来实现一下邻接矩阵：
结构定义
那我们这里呢还是搞成模板，因为顶点的值可以是任意类型，那我们的模板都需要给哪些参数呢？
这里我们先给了3个模板参数，解释一下：
V接收顶点（vertex）的类型，W接收权值的类型（权值不一定非得是整数）,然后我们再给一个非类型模板参数来决定我们要定义的图是有向图还是无向图(比如Direction==false就是无向图，等于true就是有向图)，一般用无向图居多，所以可以给个缺省值false，我们不传默认就是无向图。
那现在图里面要存顶点和边：
顶点呢我们就可以用一个vector来存储。
那边我们要如何存呢？
上面有提到邻接矩阵是用一个二维数组（即矩阵）来存储边（顶点之间的关系）的，我们可以再来看一下图
那这里就涉及到一个问题：
这里面二维数组的每一个下标是不是都要跟一个顶点进行映射啊。
比如二维数组中某一个元素_vertexs[i][j]是1，那就表示下标i和j对应的两个顶点是连通的。
那怎么建立顶点和数组下标的映射呢？
🆗，我们上一篇文章并查集里面其实就讲了一种方法，我们当时说了图里面也会用到。
用一个map就搞定了嘛。
构造函数
然后我们来想一下构造函数可以怎么写?
那我们可以这样搞:
创建一个图对象的时候可以先把顶点存一下，给一个顶点的数组就可以，然后后面我们可以再增加一个增加边的接口，我们可以手动创建边和赋权值。
所以，构造函数
就可以这样写
添加边
然后我们来增加一个添加边的接口：
那首先我们要获取一下顶点的下标，因为我们添加边其实就是在邻接矩阵里面改这两个顶点对应位置的值嘛
可以再封装一个接口
然后AddEdge里面我们就可以获取两个顶点对应的下标然后在邻接矩阵里面添加边
然后添加边这里有一个问题
我们的代码是要同时针对有向图和无向图的，如果是无向图的话我们添加一条边比如AB，那就完了；但是如果是有向图添加AB就是AB，如果要添加BA的就需要再添加一次。
所以我们这样写：
打印图
然后我们再写一个打印，搞些数据测试一波：
测试
来测试一下
我们就以这个为例
运行一下
没问题，只不过上面图中ij相等的位置打印的是0
2.3 邻接表
邻接表：
使用数组存储顶点的集合，使用链表存储顶点的关系（边）。
比如
无向图邻接表存储：
一个顶点与哪些顶点相连，相连的顶点就存到这个顶点对应的链表中，当然如果带权的话也要存上对应边的权值。
（每个顶点都有一个对应的链表，多条链表用一个指针数组就可以维护起来）
注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点vi 对应链表集合中结点的数目即可
有向图邻接表存储：
那通过上面的了解其实我们可以得出，对于邻接表的存储方式
1. 适合存储稀疏图（边比较少的图），因为邻接表的话有多少边链表里面就存几个对应的顶点，不需要额外的空间；而上面邻接矩阵不论边多边少都要开一个N*N的矩阵（二维数组），边少的时候那就大部分位置都存的是0
2. 方便查找从一个顶点连接出去的边有哪些，因为它对应的边链表里面存的就是与这个顶点相连的顶点
3. 但是不方便确定两个顶点是否相连和获取权值（要遍历其中一个顶点的边链表查找O(N)）
2.4 邻接表代码实现
那我们再来实现一下邻接表。
结构定义
首先来定义一下邻接表的结构：
首先对于邻接表来说，模板参数这里就不需要MAX_W这个非类型模板参数了。
因为上面邻接矩阵之所以需要是因为矩阵不相连的边矩阵里面对应得位置要存这个值来标识一下，但是邻接表我们上面了解了，每个顶点连接的边有多少，就存多少个顶点，不相连的顶点直接是不存的。
然后呢顶点我们还是用一个vector来存，还要建立顶点跟下标的映射（每个顶点要跟指针数组的下标一一对应），与邻接矩阵不同的在于这里的边要用链表来存，一个顶点与哪些顶点相连，相连的顶点就存到这个顶点对应的边链表中。
如果带权的话还要存上权值，所以我们可以把边链表封装成一个类：
其实就是一个链表的结构，因为我们要用链表来存储边嘛
然后，图的结构里面
邻接表其实就是一个指针数组嘛，每个位置存一个指针，指针指向一个链表，该位置的下标就映射对应的顶点，对应的链表里面存的就是与之相连的顶点以及对应边的权值
构造函数
那下面我们来写一下邻接表结构图的构造函数：
逻辑其实根上面邻接矩阵是一样的
添加边
然后添加边：
首先还是获取一下边的起始顶点和终止顶点映射的下标
然后添加边的时候：
如果是无向图，比如添加一个边AB，那要在A的链表里面挂B顶点，也要在B的链表里面挂A顶点；
如果是有向图，只在A的链表里面挂B就行了（当然有向图的话我们看到上面还分为出边表和入边表，但是入边表一般不需要搞，我们这里就只存一个出边表，有需要的话可以再添加）
所以呢，添加的逻辑我们这样写：
打印图
那我们再来写个打印的函数，然后测试一下
这个函数没什么难度，就不解释了
测试
然后我们来搞一组数据测试一下：
我们这里不传第三个模板参数，默认是无向图
看一下结果
没问题！
我们也可以试一下有向图
也没问题！
3. 源码
3.1 Graph.h
#pragma once
//邻接矩阵
namespace matrix
{
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:
Graph(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;
}
//给邻接矩阵开空间
_matrix.resize(n);
for (auto& e : _matrix)
{
e.resize(n, MAX_W);
}
}
size_t GetVertexIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
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()
{
// 打印顶点和下标映射关系
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << _vertexs[i] << "-" << i << " ";
}
cout << endl << endl;
cout << " ";
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << 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_W)
cout << _matrix[i][j] << " ";
else
cout << "#" << " ";
}
cout << endl;
}
cout << endl << endl;
// 打印所有的边
//for (size_t i = 0; i < _matrix.size(); ++i)
//{
// for (size_t j = 0; j < _matrix[i].size(); ++j)
// {
// if (i < j && _matrix[i][j] != MAX_W)
// {
// cout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
// }
// }
//}
}
private:
vector<V> _vertexs;//顶点集合
map<V, int> _indexMap;//顶点和下标建立映射
vector<vector<W>> _matrix;//存储边的矩阵
};
void TestGraph()
{
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();
}
}
//邻接表
namespace link_table
{
template<class W>
struct Edge
{
int _dsti;//边的终止顶点下标
W _w; //权值
Edge<W>* _next;
Edge(const int& dsti, const W& w)
:_dsti(dsti)
,_w(w)
,_next(nullptr)
{}
};
template<class V, class W, bool Direction = false>
class Graph
{
typedef Edge<W> Edge;
public:
Graph(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);
}
size_t GetVertexIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
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);
//src->dst
Edge* eg = new Edge(dsti, w);
eg->_next = _tables[srci];
_tables[srci] = eg;
//如果是无向图，再添加反向边dst->src
if (Direction == false)
{
Edge* eg = new Edge(srci, w);
eg->_next = _tables[dsti];
_tables[dsti] = 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* cur = _tables[i];
while (cur)
{
cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
private:
vector<V> _vertexs;//顶点集合
map<V, int> _indexMap;//顶点和下标建立映射
vector<Edge*> _tables; // 邻接表
};
void TestGraph()
{
string a[] = { "张三", "李四", "王五", "赵六" };
Graph<string, int, true> g1(a, 4);
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.Print();
}
}
3.2 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <map>
#include <string>
#include "Graph.h"
int main()
{
//matrix::TestGraph();
link_table::TestGraph();
return 0;
}