【数据结构】图的概念和存储结构

快乐的流畅：个人主页

个人专栏：《C游记》《进击的C++》《Linux迷航》

远方有一堆篝火，在为久候之人燃烧！

---

引言

数据结构世界——图（Graph）

一、图的概念

图是一种非线性结构，由顶点（vertex）和边（edge）组成。

---

有向图（directed graph）与无向图（undirected graph）：在有向图中，<x,y>和<y,x>是两条不同的有向边；在无向图中，(x,y)和(y,x)指的是同一条边。

完全图（complete graph）：在无向图中，任意两点有边相连，则为无向完全图；在有向图中，任意两点有两条方向相反的边相连，则为有向完全图。

度（degree）：与顶点关联的边数。在有向图中，度 = 入度 + 出度；在无向图中，度 = 入度 = 出度。

权（weight）：边具有的属性。带权图又称为网络（network）。

路径长度：在无权图中，路径长度是指此路径上边的条数；在有权图中，路径长度是指此路径上边的权值之和。

简单路径与回路（cycle）：一条路径上各顶点均不重复，则为简单路径；一条路径上首尾顶点重合，则为回路或环。

子图（subgraph）：一个图的顶点集和边集都属于另一个图，那么这个图便称为另一个图的子图。

连通图（connected graph）与连通分量（connected component）：连通图是一种无向图，要求任意两点都有路径可达。连通分量是非连通图的极大连通子图。

强连通图与强连通分量：强连通图是一种有向图，要求任意两点都有双向路径可达。强连通分量是非强连通图的极大连通子图。

生成树（spanning tree）：连通图的极小连通子图称为该图的生成树。

二、图的存储结构

图由顶点和边构成，而顶点用数组存储即可，唯一值得讨论的便是边的存储方式。以下介绍两种最常见的边存储方式。

2.1 邻接矩阵

2.1.1 成员变量与默认成员函数

template<class V, class W, W W_MAX = INT_MAX, bool Direction = false>
class Graph
{
public:Graph(){}Graph(const V* v, int n){_vertexs.reserve(n);for (int i = 0; i < n; ++i){_vertexs.push_back(v[i]);_indexMap[v[i]] = i;}_edges.resize(n, vector<W>(n, W_MAX));}
private:vector<V> _vertexs;map<V, int> _indexMap;vector<vector<W>> _edges;
};

细节：

1. V代表顶点类型，W代表权值类型，W_MAX代表权值的正无穷，Direction代表图是否有向。
2. _vertexs存储顶点，_indexMap存储顶点与下标的映射，_edges存储每两个顶点所对应边的权值。

图的创建方式：
1、IO输入——在线oj常用
2、文件写入
3、手动添加边——便于调试

2.1.2 GetIndex

int GetIndex(const V& v)
{auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{throw invalid_argument("顶点不存在");return -1;}
}

细节：获取下标额外设计一个函数，防止传入不存在的顶点，增强程序的健壮性。

2.1.3 AddEdge

void _AddEdge(int srci, int dsti, const W& w)
{_edges[srci][dsti] = w;//若为无向图if (!Direction){_edges[dsti][srci] = w;}
}void AddEdge(const V& src, const V& dst, const W& w)
{int srci = GetIndex(src);int dsti = GetIndex(dst);_AddEdge(srci, dsti, w);
}

细节：

1. 添加边，便是在矩阵对应位置赋上权值，若为无向图则反方向也要添加。
2. 这里拆出一个子函数，是方便后续直接通过顶点下标进行添加边。

2.1.4 Print

void Print()
{for (int i = 0; i < _vertexs.size(); ++i){cout << "[" << i << "]" << ":" << _vertexs[i] << endl;}cout << endl;for (int i = 0; i < _edges.size(); ++i){for (int j = 0; j < _edges[0].size(); ++j){if (_edges[i][j] == W_MAX){printf("%4c", '*');}else{printf("%4d", _edges[i][j]);}}cout << endl;}
}

细节：为了美观性，将W_MAX表示为*，同时用printf进行对齐控制。

2.2 邻接表

2.2.1 结点

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

细节：

1. _dsti表示目标点的下标，_w表示到达目标点的边的权值。
2. 目标点是与当前点直接相连的。

2.2.2 成员变量与默认成员函数

template<class V, class W, bool Direction = false>
class Graph
{typedef EdgeNode<W> Node;
public:Graph(const V* v, int n){_vertexs.reserve(n);for (int i = 0; i < n; ++i){_vertexs.push_back(v[i]);_indexMap[v[i]] = i;}_edges.resize(n, nullptr);}
private:vector<V> _vertexs;map<V, int> _indexMap;vector<Node*> _edges;
};

细节：

1. V代表顶点类型，W代表权值类型，Direction代表图是否有向。
2. _vertexs存储顶点，_indexMap存储顶点与下标的映射，_edges存储每个顶点所连的边的信息。

2.2.3 GetIndex

int GetIndex(const V& v)
{auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{throw invalid_argument("顶点不存在");return -1;}
}

细节：获取下标额外设计一个函数，防止传入不存在的顶点，增强程序的健壮性。

2.2.4 AddEdge

void AddEdge(const V& src, const V& dst, const W& w)
{int srci = GetIndex(src);int dsti = GetIndex(dst);Node* node1 = new Node(dsti, w);node1->_next = _edges[srci];_edges[srci] = node1;//若为无向图if (!Direction){Node* node2 = new Node(srci, w);node2->_next = _edges[dsti];_edges[dsti] = node2;}
}

细节：添加边，便是在矩阵对应位置赋上权值，若为无向图则反方向也要添加。

2.2.5 Print

void Print()
{for (int i = 0; i < _vertexs.size(); ++i){cout << "[" << i << "]" << ":" << _vertexs[i] << endl;}cout << endl;for (int i = 0; i < _edges.size(); ++i){cout << "[" << i << "]" << "->";Node* cur = _edges[i];while (cur){cout << cur->_dsti << "->";cur = cur->_next;}cout << "nullptr" << endl;}
}

总结

邻接矩阵：适合处理稠密图，空间换时间

• 查询边关系非常快速
• 但空间效率低

邻接表：适合处理稀疏图，空间使用高效

• 插入删除操作高效
• 但查询性能相对较慢

真诚点赞，手有余香