Part 0 缘起
近日整理笔记时发现，初学时的图论算法都是基于邻接矩阵储存的，使用时非常不方便。所以就写了这篇博文，聊作图论学习的回顾。
Part 1 图的链式前向星表示
链式前向星又称为邻接表的静态建表方式，其最开始确实是基于前向星，是以提高前向星的构造效率为目的设计的存储方式，最终演变成了一个变形的邻接表这一数据结构。
链式前向星采用数组模拟链表的方式实现邻接表的功能。（为方便使用，以下代码使用vector实现链式前向星）
无权图的链式前向星表示
vector<int> G[MAX_N]; //表示有MAX_N个顶点的图的链式前向星
: :
G[u].push_back(v); //从顶点u向顶点v连边
//G[v].push_back(u); //无向图时再从顶点v向顶点u连边
: :
//搜索与顶点u相邻的顶点v
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
: :
}加权图的链式前向星表示
vector<pair<int, int> > G[MAX_N]; //表示有MAX_N个顶点的图的链式前向星
: :
G[u].push_back(make_pair(v, c)); //从顶点u向顶点v连权值为c的边
//G[v].push_back(make_pair(u, c)); //无向图时再从顶点v向顶点u连权值为c的边
: :
for(int i = 0; i < G[u].size(); i++)
{
//搜索与顶点u相邻的顶点v
int v = G[u][i].first;
: :
//顶点u与顶点v之间的边权
int d = G[u][i].second;
: :
}Part 2 图的深度优先搜索
在图的搜索算法中，深度优先搜索采取的思路是尽可能地访问相邻顶点。
设仍存在未搜索邻接边的顶点中最后一个被发现的顶点为v，那么深度优先搜索就是对顶点v的邻接边递归地进行搜索, 当v的边全部搜索完毕后，程序沿发现v时所经过的边回归，继续搜索前一顶点。
搜索一直持续到发现当前起点可到达的所有顶点为止。如果仍有顶点未被发现，则选择其中编号最小的一个作为新起点继续搜索。
深度优先搜索中，对各顶点记录以下两个时间戳：
- 时间戳d[v]: 记录第一次访问v的时刻（发现时刻）
- 时间戳f[v]: 记录调查完v的相邻顶点的时刻（结束时刻）
该算法通常的时间复杂度为$O(|V| + |E|)$
使用栈的深度优先搜索
将最初访问的顶点压入栈。
只要栈中仍有顶点，就循环进行下述操作：
访问栈顶部的顶点u
从当前访问的顶点u移动至顶点v时，将v压入栈。如果当前顶点不存在末访问的相邻顶点，则将u从栈中删除
dfs_init() //顶点编号为 0 起点
将所有顶点的 color 设置为 WHITE
dfs(0) //以顶点0为起点进行深度优先搜索
dfs(u)
S.push(u) //将起点u压入栈
color[u] = GRAY
d[u] = ++time
while S 不为空
u = S.top()
v = next(u) //依次获取与 u 相邻的顶点
if v != NIL
if color[v] == WHITE
color[v] = GRAY
d[v] = ++time
S.push(v)
else
s.pop()
color[u] = BLACK
f[u] = ++time使用递归的深度优先搜索
dfs_init() //顶点编号为 0 起点
将所有顶点的 color 设置为 WHITE
dfs(0)
dfs(u)
color[u] = GRAY
d[u] = ++time
for 顶点 v 从 0 到|V|-1
if M[u][v] && color[v] == WHITE
dfs(v)
color[u] = BLACK
f[u] = ++time#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
int n;
int color[MAX_N], d[MAX_N], f[MAX_N], tt;
vector<int> G[MAX_N];
void dfs_visit(int u) {
color[u] = GRAY;
d[u] = ++tt;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (color[v] == WHITE)
dfs_visit(v);
}
color[u] = BLACK;
f[u] = ++tt;
}
void dfs() {
//init
for (int i = 0; i < n; i++)
color[i] = WHITE;
tt = 0;
for (int i = 0; i < n; i++)
if (color[i] == WHITE)
dfs_visit(i);
for (int i = 0; i < n; i++)
printf("%d %d %d\n", i + 1, d[i], f[i]);
}
int main() {
int u, v, k;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &u, &k);
u--;
for (int j = 0; j < k; j++) {
scanf("%d", &v);
v--;
G[u].push_back(v);
G[v].push_back(u);
}
}
dfs();
return 0;
}在某些语言或环境下，对规模较大的图使用递归思路的深度优先搜索算法会导致栈溢出。
目前大部分算法竞赛（包括CSPNOIP、大部分省选以及 CCF 举办的各项赛事）都支持无限栈空间 ，即：栈空间不单独限制，但总内存空间仍然受题面限制。
Part 3 图的广度优先搜索
将最初访问的顶点压入队列。
只要队列中仍有顶点，就循环进行下述操作：
访问队首的顶点u
从当前访问的顶点u移动至顶点v时，将v压入队列
该算法通常的时间复杂度为$O(|V| + |E|)$
bfs() //顶点编号为 0 起点
将所有顶点的 color 设置为 WHITE
将所有顶点的 d[u] 设置为 INFTY
color[s] = GRAY
d[s] = 0
Q.enqueue(s)
while Q不为空
u = Q.dequeue()
for v 为 0 到|V|-1
if M[u][v] && color[v]
color[v] = GRAY
d[v] = d[u] + 1
Q.enqueue(v)
color[u] = BLACK#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define MAX_N 110
int n;
vector<int> G[MAX_N];
int num, u, v;
int flag[MAX_N];
int d[MAX_N];
void bfs() {
queue<int> q;
q.push(1);
d[1] = 0;
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++) {
int j = G[t][i];
if (flag[j] == 0) {
// 标记为已经访问
flag[j] = 1;
// 更新长度
d[j] = d[t] + 1;
// 压入栈内
q.push(j);
}
}
}
}
int main() {
scanf("%d", &n);
memset(d, 0, sizeof(d));
for (int i = 0; i < n; i++) {
scanf("%d %d", &u, &num);
u--;
// 初始化
flag[i] = 0;
d[i] = -1;
for (int j = 0; j < num; j++) {
scanf("%d", &v);
v--;
G[u].push_back(v);
G[v].push_back(u);
}
}
bfs();
for (int i = 0; i < n; i++) {
printf("%d %d\n", i + 1, d[i]);
}
return 0;
}
