图算法(一)遍历,拓扑排序

本文介绍图的几种基本操作:BFS,DFS,求有向图连通分量的Tarjan算法以及拓扑排序。

图的表示

一张图是由若干顶点和顶点之间的边组成的,可以形式化为G(V, E),V代表顶点集合,E代表边集,本文中为了书写方便,定义顶点数|V|=n,边数|E|=m。根据边是否有方向,可以分为有向图和无向图,本文讨论的内容都是有向图。下面是一个无向图的示例。

graph.png

在编码中,图的存储方式常见的有两种:邻接表和邻解矩阵,在C++中的写法是:

// adjacency matrix
const int MAXV = 1e5;
int G1[MAXV][MAXV];

//adjacency lists
struct Edge1 {
    int dst, dis;
};
std::vector<std::vector<Edge1> > G2;

这两种存储方法对应的基本操作时间复杂度如下:

空间复杂度 查看u,v之间边的权值 遍历所有的边
邻接表 O(m+n) O(degree(u)) O(m + n)
邻接矩阵 O(n^2) O(1) O(n^2)

一般来说,邻接表的方式使用的多一些,因为稠密图并不是很常见,在图的遍历上邻接表有优势。但也有特定场景邻接矩阵会更方便,如Floyd算法的实现。

图的遍历(BFS & DFS)

图算法中最基础的就是图的遍历了,基本方法有两种:广度优先搜索(BFS)和深度优先搜索(DFS)。为了方便描述,我们定义图上从顶点i到顶点j的一条简单路径为一系列的点i, k1, k2, ..., j,其中没有重复出现的顶点,连续出现的点之间有边相连,路径上点的个数减1代表路径的长度。

BFS的大致思想就是先遍历和起点最短路径长度为0的点(起点本身),再遍历长度为1的点(从起点出发1步可达的点),再遍历长度为2的点....直到所有点都被访问过。时间复杂度O(m+n),下图是一个更形式化的描述:

bfs.png

在C++中,BFS常配合队列(queue)这一数据结构实现:

std::vector<std::vector<Edge> > g;
bool vis[MAXV];

// implementation of breath-first search
std::vector<int> bfs(int s) {
    std::vector<int> seq;
    std::queue<int> q;
    memset(vis, 0, sizeof(vis));  // initialize data
    q.push(s); vis[s] = true;   // insert starting node into queue
    while(!q.empty()) {
        int hd = q.front();
        q.pop();
        seq.push_back(hd);
        for(int i = 0; i < g[hd].size(); i++) {
            int next = g[hd][i];
            if(vis[next]) continue;
            q.push(next); vis[next] = true;
        }
    }
    return seq;
}

DFS的大致思想是从当前点出发,沿着一条简单路径走到没有点可以访问,再回溯到之前访问过的节点,沿着另一条简单路径走下去。直到所有点都被访问一遍,时间复杂度同样是O(m+n)。DFS通常通过递归实现。

std::vector<std::vector<Edge> > g;
std::vector<int> seq;   // store the visiting order
bool vis[MAXV];

// implementation of depth-first search
void dfs(int s) {
    if(vis[s]) return;
    seq.push_back(s); vis[s] = true;
    for(int i = 0; i < g[s].size(); i++)
        dfs(g[s][i]);
}

回顾BFS/DFS的搜索过程,除了起点,每个点都是通过父节点指向它的一条边被引入的,如果把这个过程建图,那么这个图中一共有n个节点和n-1条边,且整个图是连通的(假设图中的边是无向的),满足这两条性质的无向图称之为,通过BFS/DFS得到的树被称为搜索树。

最后补充一点,在状态数很多的搜索问题中,BFS被认为是完备的,即解如果存在,一定可以搜到,DFS则不是,可能需要和迭代加深这些策略配合。

Tarjan算法

在一次BFS或DFS中,我们其实并不能保证一定访问到图中的所有节点,因为有些图可能是不连通的。我们把从一个点出发,所有可达点的集合称为这个点所在的连通分量。给定一个无向图,我们找所有连通分量的方法叫做灌水法(Flood Fill),其实就是对当前未访问过的点做BFS/DFS,直到所有的点都被访问过1次。
Tarjan算法是为了解决有向图中类似的问题提出的。只不过有向图中我们可以定义强连通分量,有向图中一个强连通分量中的任意两个点u,v都是强连通的,即存在从u到v的路径,也存在从v到u的路径。

strong-connected.png

很明显,Flood Fill并不能用来求强连通分量。但只使用BFS/DFS,我们可以给出一个求给定点所在强连通分量的方法:1) 从该点出发做一次BFS/DFS;2) 把所有边反向,再从这个点做一次BFS/DFS;3) 把两次搜索访问的顶点集合做一次交,就可以得到该点所在的极大强连通分量。如果用这种方法求所有强连通分量的话,需要对每个点做两次BFS/DFS,时间复杂度为O(n^2)。更好的方法是Kosaraju算法或Tarjan算法,这里只介绍Tarjan。

Tarjan算法中,图中每个节点维护两个属性:

  1. dfu(i):节点i在DFS中第dfu(i)个被访问到(时间戳);
  2. low(i):DFS搜索树中,以节点i为根节点的子树中的节点集合记为T(i)。T(i)中的点在原图中所指向的点的集合记为S(i)。S(i)中最小的时间戳就是low(i),low(i)可以用下面的递归式表示:
    low(i) = min(dfn(i), dfn(j), low(j)) (j为i的子节点)

Tarjan算法的描述如下:

  1. 初始化一个空的栈和一个每访问一个节点加1的计时器
  2. 对图做DFS,每次访问新的顶点时,设定dfn(i)为当前时间,把该节点压栈,接着求low(i):对于还没被访问的后继节点j,递归访问j,low(i) = min(dfn(i), low(j)),对于已经访问过的后继节点k,low(i) = min(low(i), dfn(j))。如果最终得到的low(i) = dfn(i),就把栈中当前节点以上的节点全部弹出,这些节点就是一个极大强连通分量

Tarjan算法只需要做一遍DFS,所以一定会终止,时间复杂度O(m+n)

C++实现:

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    st[++top] = u;
    instack[u] = true;

    for(Edge *p = e[u]; p; p = p->next) {
        int v = p->dst;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        }
        else if(instack[v])
            low[u] = std::min(low[u], dfn[v]);
    }
    
    if(dfn[u] == low[u]) {
        cluster++;
        int hd;
        do {
            hd = st[top--];
            instack[hd] = false;
            belong[hd] = cluster;
        }
        while(hd != u);
    }
}

(PS:一道经典的求强连通分量的题 Networks of School

拓扑排序

在图论中,我们经常讨论有向无环图DAG(Directed Acyclic Graph),这类图常用来描述节点之间的依赖关系(先修课程、软件包的安装依赖)。对于DAG,我们可以对其进行拓扑排序。
一个DAG的拓扑排序是图中所有顶点的一个排列:v1, v2, ..., vn,对于原图中每条边(vi, vj)都有i < j。下图就展示了一个拓扑排序的例子:

topological.png

拓扑排序可以通过一个很直观的策略求得:选取当前所有入度为0的点,把它们加入拓扑序列中,再把这些点的出边删去,反复这两个操作,直到所有的点都加入拓扑序列中。对应的C++实现如下:

std::vector<int> topsort(const std::vector<std::vector<int> > &g) {
    int n = g.size();
    std::vector<int> d(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < g[i].size(); j++)
            d[g[i][j]]++;
    
    std::queue<int> q;
    std::vector<int> seq;
    for(int i = 0; i < n; i++)
        if(!d[i]) q.push(i);
    while(!q.empty()) {
        int hd = q.front();
        q.pop();
        seq.push_back(hd);
        for(int i = 0; i < g[hd].size(); i++) {
            int dst = g[hd][i];
            d[dst]--;
            if(!d[dst]) q.push(dst);
        }
    }
    return seq;
}

正确性证明:
结论1:算法一定会终结。队列中最多会压入n个顶点,每次循环都会取出第一个元素,因此最多循环n次,同时,每次循环内会访问当前队列第一个点的所有出边,这个点不会再加入队列,因此每条边最多被访问一次,算法总的复杂度O(m+n)。
结论2:对于连通的DAG,算法一定会返回一个长度为n的序列。如果当前序列长度不足n,说明连通图中还有点没有被加入序列,而此时如果队列为空,则说明没有入度为0的点了,这在无环图是不可能的。这同时提醒我们,对于没有保证连通性的图,需要多次的拓扑排序已确保每个连通分量中的点都加入了序列。同时,如果考虑所有连通分量后,最终返回序列的长度小于n,那么说明原图中有环。
结论3:对于返回的序列v1, v2, ..., vn,原图中不存在边(vi, vj)使得i > j。假如有这样一条边从vi指向vj,且在拓扑序列中vj在vi之前。算法中vj在被删除时,vi还没被删除,因此vj的入度不会为0,矛盾!

(PS:一道不错的拓扑排序的题 All Discs Considered

本文图片来自 Lecture Slides for Alogorithm Design by Jon Kleinberg and Éva Tardos.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容

  • 课程介绍 先修课:概率统计,程序设计实习,集合论与图论 后续课:算法分析与设计,编译原理,操作系统,数据库概论,人...
    ShellyWhen阅读 2,249评论 0 3
  • 归去来兮。 1.1 说明 本篇为《挑战程序设计竞赛(第2版)》[http://www.ituring.com.cn...
    尤汐Yogy阅读 14,267评论 0 160
  • https://zh.visualgo.net/graphds 浅谈图形结构https://zh.visualgo...
    狼之独步阅读 4,113评论 0 0
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,071评论 0 12
  • 【我的感悟】 11 酒店的硬件设施还算不错。本打算第二天起来看日出,在手机上定了凌晨4点的闹钟,当听到聒噪的闹铃响...
    刘旭晖阅读 223评论 0 1