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


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>

#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[u] = WHITE;
    tt = 0;

    for(int i = 0; i < n; i++)
        if(color[u] == 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>
using namespace std;
const int MAX_N = 110;
int n;
vector<int> G[MAX_N];
int u, num, v;
int flag[MAX_N];
int d[MAX_N];

void bfs()
{
    queue<int> q;

    q.push(1);
    d[1] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = 0; i < G[u].size(); i++)
        {
            int j = G[u][i];
            if(flag[j] == 0)
            {
                // 标记为已经访问
                flag[j] = 1;
                // 更新长度
                d[j] = d[u] + 1;
                // 压入栈内
                q.push(j);
            }
        }
    }
}
int main() {

    scanf("%d", &n);
    memset(m, 0, sizeof(m));
    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;
}

Author: thyzzs
Reprint policy: All articles in this blog are used except for special statements CC BY-NC-SA 4.0 reprint policy. If reproduced, please indicate source thyzzs !
评论
  TOC