【笔记】基于链式前向星的图论算法（一） 搜索

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;
}