数据结构之图论初识

图的基本概念

图是由顶点集合和边的集合组成的一种数据结构，记作 G=(V,E) 。

• 有向图：顶点对<x, y>是有序的，顶点对<x，y>称为顶点x到顶点y的一条边(弧)，<x, y>和<y, x>是两条不同的边
• 无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)是同一条边

图的相关知识点

完全图

• n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图
• n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图

邻接顶点

• 若顶点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)

路径

• 从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶
  点序列为从顶点vi到顶点vj的路径

简单路径与回路

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

图的存储结构

在图的存储中，只需要保存：节点和边关系

• 邻接矩阵
• 邻接表

邻接矩阵

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

• 数组下标(i,j)位置存储的值代表,顶点i到j是否有边,用0/1表示
• 对于无向图, 邻接矩阵是对称矩阵的,因为a<->b
• 对于有向图, 邻接矩阵是不对称的,因为a->b

如果边有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替

邻接矩阵优点：

• 适合稠密图的存储
• O（1）即可判断两点的连接关系，并拿到权值
• 相对来说，查找一个顶点与之相连的顶点个数比较麻烦，需要遍历数组O（N），所以引出了邻接表

邻接表

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

无向图邻接表存储

有向图邻接表存储

邻接表优点：

• 适合稀疏图的存储
• 方便查找一个顶点与之相连的顶点个数
• 不容易查找边的权值

图的模拟实现

邻接矩阵

#pragma once
#include <vector>
#include <map>using namespace std;namespace matrix
{template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>class Graph{public:// 图的创建：1. IO输入(不方便测试) 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]);_index[a[i]] = i;}_edge.resize(n);for (size_t i = 0; i < n; i++){_edge[i].resize(n, MAX_W);}}//找到顶点对应的下标size_t GetVertexIndex(const V& v){if (_index.find(v) == _index.end()){cout << "要添加的边的顶点不存在" << endl;return -1;}return _index[v];}void AddEdge(const V& src, const V& dest, const W& w)//向图中添加边(源点,目标点,以及权值){int srci = GetVertexIndex(src);int desti = GetVertexIndex(dest);_edge[srci][desti] = w;if (Direction == false)_edge[desti][srci] = w;}void Print(){//打印顶点for (int i = 0; i < _edge[0].size(); i++)cout << "[" << i << "]" << "->" << _vertexs[i] << endl;cout << endl;//打印矩阵for (int i = 0; i < _edge[0].size(); i++){for (int j = 0; j < _edge[0].size(); j++){if (_edge[i][j] == MAX_W)cout << "* ";else cout << _edge[i][j] << " ";}cout << endl;}cout << endl;}private:vector<V> _vertexs;         // 图的顶点集合vector<vector<W>> _edge;    // 图的边的集合map<V, int> _index;         // 顶点映射下标};void TestGraph(){Graph<char, int, -1, 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();}}