图论
1.什么是图（Graph）？
图（Graph）是离散数学（Discrete mathematics）的一个分支，也是算法中的一个重要内容。
序言
基本上，图是表明主体（物品）（objects）之间的关系（relationships）的。我们用一个比较浅显的例子来表明什么是图：
这是一张人和人之间的关系图，我们说每个点代表一个人（也就是Object），每条线代表他们是朋友关系（也就是relationships）。
这个图片很像【图】了，从一般性推断，我们可以这样说：
图 = 点 + 线
这句话对，但是不完全对
让我们看看下面这个图
你会发现图中的线多了箭头，我们可以认为是谁关注了谁。它并不像刚才那样是双向的，而是单向的。
这两种图将会成我们在我们学习算法中遇到的接近90%的图
图的定义
接下来我们给图一个标准的定义：
图 (Graph) 是一个二元组 \(G=(V(G), E(G))\)。其中 \(V(G)\) 是非空集，称为 点集 (Vertex set)，对于 \(V\) 中的每个元素，我们称其为 顶点 (Vertex) 或 节点 (Node)，简称 点；\(E(G)\) 为 \(V(G)\) 各结点之间边的集合，称为 边集 (Edge set)。
我们来逐句理解一下这段话：
-
图 (Graph) 是一个二元组 \(G=(V(G), E(G))\)
- 图是点和边组成的集合
- \(V(G)\) 是非空集
- 在图中，边可以没有，但是点不能没有（至少有一个）。也就是说最小的图是一个点。
-
\(V(G)\) (点集)
- 点的集合
-
\(E(G)\) 为 \(V(G)\) 各结点之间边的集合
- 边是两个点才能形成的
我们说，常用 \(G=(V,E)\) 表示图。
当 \(V,E\) 都是有限集合时，称 \(G\) 为 有限图。当 \(V\) 或 \(E\) 是无限集合时，称 \(G\) 为 无限图。
在做题中遇到的，全部都是有限图，因为计算机只解决有限集合的问题
图的边权
若 \(G\) 的每条边 \(e_k=(u_k,v_k)\) 都被赋予一个数作为该边的 权，则称 \(G\) 为 赋权图。如果这些权都是正实数，就称 \(G\) 为 正权图。
权值是非常重要的一个概念，他们总是在题目中成为最关键的条件。权可能以这样的形式出现：
- 从A到B要t小时时间
- 从A到B需要花费x元钱
- A到B之间你会付出q点法力值
2.无向图和有向图(Undirected graph & Directed graph)
无向图和有向图是我们学习图论中的最重要的初始概念，搞清无向图和有向图，对我们的做题有非常大的好处。
无向图的概念比有向图简单，所以我们先学习一下无向图。
无向图的定义
若 \(G\) 为无向图，则 \(E\) 中的每个元素为一个无序二元组 \((u, v)\)，称作 无向边 (Undirected edge)，简称 边 (Edge)，其中 \(u, v \in V\)。设 \(e = (u, v)\)，则 \(u\) 和 \(v\) 称为 \(e\) 的 端点 (Endpoint)。
解释如下：
- 则 \(E\) 中的每个元素为一个无序二元组 \((u, v)\)，称作 无向边 (Undirected edge)，简称 边 (Edge)
- E是边的集合。这句话指任意一条边可以用两个顶点（u，v）相连表示。
- 因为(u, v)和(v, u)表示的含义是完全一样的，所以是无序的
- 其中 \(u, v \in V\)。设 \(e = (u, v)\)，则 \(u\) 和 \(v\) 称为 \(e\) 的 端点 (Endpoint)。
- 顶点（Vertex）在无向图中有了新名字，u和v连成了边e，那么u和v被称为e的端点
有向图的定义
若 \(G\) 为有向图，则 \(E\) 中的每一个元素为一个有序二元组 \((u, v)\)，有时也写作 \(u \to v\)，称作 有向边 (Directed edge) 或 弧 (Arc)，在不引起混淆的情况下也可以称作 边 (Edge)。设 \(e = u \to v\)，则此时 \(u\) 称为 \(e\) 的 起点 (Tail)，\(v\) 称为 \(e\) 的 终点 (Head)，起点和终点也称为 \(e\) 的 端点 (Endpoint)。并称 \(u\) 是 \(v\) 的直接前驱，\(v\) 是 \(u\) 的直接后继。
解释如下：
- 则 \(E\) 中的每一个元素为一个有序二元组 \((u, v)\)，有时也写作 \(u \to v\)，称作 有向边 (Directed edge) 或 弧 (Arc)。
- 由于有向图是有方向的，(u, v)和(v, u)表示的含义是不一样的，所以说是有序二元组，前后顺序影响结果。
- 边在有向图中被称为弧（Arc）
- 设 \(e = u \to v\)，则此时 \(u\) 称为 \(e\) 的 起点 (Tail)，\(v\) 称为 \(e\) 的 终点 (Head)。起点和终点也称为 \(e\) 的 端点 (Endpoint)。
- 由于向量的概念，尾巴是起点，头是终点。但是我们一般不会这么麻烦的去称呼它。
- 并称 \(u\) 是 \(v\) 的直接前驱，\(v\) 是 \(u\) 的直接后继。
- 尾巴是头的前驱，头是尾巴的后继
3.存储图的方式（一）——邻接矩阵
使用一个二维数组 e 来存边，其中 e[u][v] 为 1 表示存在 \(u\) 到 \(v\) 的边，为 0 表示不存在。
如果是带边权的图，可以在 e[u][v] 中存储 \(u\) 到 \(v\) 的边的边权。
邻接矩阵是最基础的存图方式，数组的下标表示了两个点，数组的值代表了边。
无向图用邻接矩阵存图
无向图存图的特点是：对于每个(u,v)对来说，在相反的位置(v,u)得到的值是一样的。
通过标绿的值可以看出来，无向图的存储是根据斜对角线对称的。
并且还可以发现，对角线（0,0),(1,1),(2,2)等的值全部都是0。这体现了一个概念：自己到自己走不通。
有向图用邻接矩阵存图
有向图存图的特点是：对于每个(u,v)对来说，矩阵中只有一个格子会对应。
图论DFS/BFS：查找文献
小K 喜欢翻看博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设博客里面一共有 n篇文章（编号为 1 到 n）以及 m条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
4
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
样例输入：
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
样例输出：
1 2 5 6 3 7 8 4
1 2 3 4 5 6 7 8
DFS实现说明
DFS是深度优先搜索的英文缩写（Depth First Search）。深度优先搜索基本上会采用递归的方式进行。
DFS“法”如其名，我们总是先往深处进行搜索，在深度无法更加深时，会进行回溯。回溯，顾名思义，回到原来的位置。
当一个点通过后，我们一般都不会重复进入，所以我们会对其进行“标记”，使其无法再次进入。
【思路说明】：
-
每一个点只需要走一次，所以和普通DFS搜索一样，走过一个节点就需要将其给标记，使其下次不能再走。
0表示未标记，1表示已经标记了。 -
一个点可能有n条边，但是这个DFS需要先选择点较小的那个边。所以我们在dfs多条路径时需要选择通往点最小的那条边。
-
需要输出从小到大的每个节点，我们在深搜的时候可以一边搜一边输出。
【代码模拟实现】
-
选定起始点s，由题意可得起始点是st = 1。
初始化vis数组，让每一个点都没有被标记。memset(vis, 0, sizeof(vis))； -
从1开始dfs，在每一层dfs中，我们将当前的点设为
x-
我们标记1，并进行输出。循环查找从1点到n点每个点，也就是
e[x][i]void dfs(int x) { vis[x] = 1; cout << x << " "; for(int i = 1; i <= n; i++) { if(e[x][i] == 1 && !vis[i]) { dfs(i); } } } -
由于我们是从小到大对数组进行遍历的，所以肯定是最小的。我们找到第一个可以和x连的点，这里是2
-
接着我们从2节点开始往下深搜，还是一样的操作，标记2并输出，循环查找从1点到n点每个点
-
找到第一个和2相连的点5。
-
接着我们从5节点开始往下深搜，还是一样的操作，标记5并输出，循环查找从1点到n点每个点
-
我们发现5下面并没有可以连接的节点，所以我们返回递归的上一层，也就是2节点这一层，在2节点中重新寻找
-
接着我们从6节点开始往下深搜，标记6并输出，但是6下面并没有节点。
-
所以我们继续回溯到根的位置
-
我们选择3这个点进行搜索
-
接着我们从3节点开始往下深搜，标记3并输出
-
接下来是7，标记7并输出
-
接着回溯后标记4并输出
-
值得注意的是，4 -> 7这条路径由于7这个点被标记了，所以是走不通的
-
最后到8以后输出，最后7到8也是无法实现的。程序结束
-
DFS代码实现：
#include <bits/stdc++.h>
using namespace std;
int e[1005][1005];
int vis[1005];
int n, m, a, b, c;
void dfs(int x) {
vis[x] = 1;
cout << x << " ";
for(int i = 1; i <= n; i++) {
if(e[x][i] == 1 && !vis[i]) {
dfs(i);
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> a >> b;
e[a][b] = 1;
}
dfs(1);
}
BFS实现说明
【代码模拟实现】
BFS是广度优先搜索的英语缩写（Breadth First Search），要实现BFS，需要使用队列（queue）。队列有先进先出（FIFO First In First Out）的特点。
【思路说明】：
-
每一个点只需要走一次，所以和普通BFS搜索一样，走过一个节点就需要将其给标记，使其下次不能再走。
0表示未标记，1表示已经标记了。 -
一个点可能有n条边，但是这个DFS需要先选择点较小的那个边。所以我们在搜索的时候，要将连着的边按从小到大的顺序放入。
-
队列里面需要顺序存放后面应该有的数
-
需要输出从小到大的每个节点，在广搜时一边搜索一边输出
【代码模拟实现】
-
对于整个代码，我们需要重置vis数组，并且将队列生成。
memset(vis, 0, sizeof(vis)); queue<int> Q; -
和DFS不同，我们开始就需要对1号节点进行vis的记录，并且压入队列（push)
Q.push(1); vis[1] = 1; -
循环至队列中没有元素为止：注意这里的操作，拿到队列头的数据后，立即弹出。
（因为数据拿到以后这个头就没有任何意义了，先弹出有助于代码的连贯性，非常推荐这种写法）while(!Q.empty()) { int u = Q.front(); Q.pop(); } -
弹出队头后输出
循环塞入在矩阵中相连的所有没有被标记过的点（当然需要从小到大循环）
假如这个点没有标记，那么标记它while(!Q.empty()) { int u = Q.front(); Q.pop(); cout << u << " "; for(int i = 1; i <= n; i++) { if(e[u][i] == 1 && !vis[i]) { Q.push(i); vis[i] = 1; } } } -
接着进入下一轮循环，我们将2得到后弹出队列，标记与2相连的矩阵元素
-
接着我们将3弹出队列，标记与3相连的矩阵元素
-
接着我们将4弹出队列，标记与4相连的矩阵元素：
但是注意，这里7被标记过了，因此不能再加 -
最后顺序输出队列中的剩余元素
BFS代码：
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(1);
vis[1] = 1;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
cout << u << " ";
for(int i = 1; i <= n; i++) {
if(e[u][i] == 1 && !vis[i]) {
Q.push(i);
vis[i] = 1;
}
}
}
重要拓展：BFS的标记方式
我们刚才使用的BFS标记方式是常规的标记方式。思路实现和DFS基本一致。
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(1);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
if(vis[u]) continue; //注意这两行
vis[u] = 1; //注意这两行
cout << u << " ";
for(int i = 1; i <= n; i++) {
if(e[u][i] == 1 && !vis[i]) {
Q.push(i);
}
}
}
通过代码比较可以直观的看出，这两份代码的不同之处就是标记的位置不同。如果一开始对起始点进行标记，再继续通过内循环标记，这样的方法会导致代码的紊乱。但是我们一开始不得不用这种方法来标记BFS。
这里牵扯到一个比较细致的问题：
为什么我们从DFS的for循环外标记，变成了for循环内标记呢？
因为DFS每次向下一层，只会拿到一个点，但是BFS却需要在一个循环中搜到多个点。
但是这里有一个新的方法，在队列弹出时标记，也就是我们新的写法。这个写法是通用写法，可以减少你的思考量级
这个写法的唯一坏处就是：队列内的点可能会重复出现
就像这张图一样，1，2，3，4都会使5加入队列中，但是由于5号点并没有标记，所以会持续加入队列中。
虽然看上去慢了，但是实际问题中不可能有如此多的边，所以我们认为这种写法是常量偏大，但是不会影响总体速度
全部代码：
#include <bits/stdc++.h>
using namespace std;
int e[1005][1005];
int vis[1005];
int n, m, a, b, c;
void dfs(int x) {
cout << x << " ";
for(int i = 1; i <= n; i++) {
if(e[x][i] == 1 && !vis[i]) {
vis[i] = 1;
dfs(i);
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> a >> b;
e[a][b] = 1;
}
dfs(1);
cout << endl;
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(1);
vis[1] = 1;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
cout << u << " ";
for(int i = 1; i <= n; i++) {
if(e[u][i] == 1 && !vis[i]) {
Q.push(i);
vis[i] = 1;
}
}
}
}
4.单源最短路径Dijkstra的邻接矩阵实现
松弛
"松弛"是一个非常理论性的概念，但总得说来就是三个字：
抄近道
譬如你要从杭州上城区去往绍兴北站，你可以选择直接坐大巴直达，需要2个小时的路程。但是如果你选择地铁转高铁，那可能只需要40分钟。
在图论中，如果不指出点权的话，那么默认换乘这种操作是不需要时间的，也就是说我们如果可以通过一个中转站到达指定地点，但是比原来快的话，我们就会选择换乘的这条路线。形式如下：
在这张图中，我们会选择20 + 40 分钟的这条路
原理说明
单源最短路径是什么意思？
表示从一个点出发到除这个点外的距离
代码实现
5.存储图的方式（二）——邻接表
什么是邻接表？
邻接表长这样，我们一般分为Head（头）和Node(节点)
头和节点用一句话概况就是：
头连向节点中的每一个点。
有向图用邻接表存图
与邻接矩阵相反，我们先来看有向图的实现方式。
如何理解头连向节点中的每一个点。这句话呢？我们用两幅图看看
0连向2和5两个点。0作为头（Head），而节点（Node）跟在后面。默认，邻接表是由链表构成的。
邻接表的一个特性是：节点值(Node)是不能随意读取的，譬如0到5是否能连上，你只能遍历所有节点。
无向图用邻接表存图
STL库：vector的用法
vector是可变数组
我们都知道c++中的数组是不能变化容量的，那么也就导致了空间上你无从知晓该开多大
但是vector可以随意的进行插入，容量随即变大。对vector的尾部插入一个数，就是push_back();
读取方式与数组完全一样。
size()可以拿到当前vector的容量。
vector<int> v;
v.push_back(12);
int c = v[0];
int sz = v.size();
vector数组实现邻接表
我们用vector的数组形式实现邻接表
每一个Head后的Node，都是一组vector
vector<int> e[3];
e[0].push_back(7);
e[1].push_back(9)
e[0].push_back(12);
遍历从i点出发的邻接表
邻接表不能任意读取，一般邻接表用来遍历找出从i点出发能通往的所有点。
int i = st;
for(int j = 0; j < e[i].size(); j++) {
int v = e[i][j];
}