BFS DFS 判断DAG(有向无环图)

Posted on Edited on

BFS DFS 判断DAG(有向无环图)

前几天美团笔试 ，笔试里有一个单源最短路问题（直接弃了，完全没想到会考图论的问题，Dijkstra算法也完全想不起来），最近看了下leetcode上一道图论的问题，AOV的拓扑排序问题。

[TOC]

一、DAG 和 Topological sorting

以下基本都是一些本科数据结构的知识，不过因为本科听课不太认真，几乎都是现查现学的。

DAG

DAG（Directed acyclic graph）即有向无环图，维基上的介绍: Directed acyclic graph

简单的介绍DAG，是一个图且是一个有向图，而且整个图没有回路，不会构成环。据说目前比较热门的区块链技术好像也有应用这种数据结构，文章: 解释有向无环图（达格），真正的区块链3.0。

DAG 具有 拓扑顺序（Topological ordering）关于拓扑顺序，引用维基上的一段话：

Every directed acyclic graph has a topological ordering, an ordering of the vertices such that the starting endpoint of every edge occurs earlier in the ordering than the ending endpoint of the edge. The existence of such an ordering can be used to characterize DAGs: a directed graph is a DAG if and only if it has a topological ordering. In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.[[9]

The family of topological orderings of a DAG is the same as the family of linear extensions of the reachability relation for the DAG,[10] so any two graphs representing the same partial order have the same set of topological orders.

大概意思就是 Graph中顶点之间有顺序上的约束关系，这种约束关系用边表示。即：如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序。（维基里涉及到族的概念，由于不是科班的,也没有学过拓扑学，搞不懂）

Topological sorting

维基的解释：

Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time.[16] Kahn’s algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way.[17] Alternatively, a topological ordering may be constructed by reversing a postorder numbering of a depth-first search graph traversal.[16]

简单而言，拓扑排序：获得一个拓扑序的过程就是拓扑排序

AOV

AOV (Activity On Vertex) 网络：把活动作为顶点（Vertex），时间的约束关系作为边（Edge），一个AOV网络一定是一个DAG。浙大陈越老师的数据结构里的一个例子：

image-20200326193703485

二、判断DAG

判断一个图是否为一个DAG，即合法的AOV网络。主要有两种方法，基于BFS（广度优先搜索）的拓扑排序，和DFS（深度优先搜索）

python构建图

图有两种实现方式，一种是邻接矩阵，一种是邻接表，由于邻接矩阵不太适合稀疏图的情况，故选用邻接表。邻接表不一定非要使用链表的数据结构，这里二维数组即可，例如v指向w1, w2,…,wn，则graph[v]=[w1, w2, …, wn];

关于python建图，推荐这篇文章Graphs in Python

BFS

基于BFS的拓扑排序，通过不断的遍历入度为0的顶点实现，遍历方式是广度优先搜索，每次遍历入度为0的顶点，同时每遍历过一个顶点，就将其指向顶点的入度减一, 如果我们能够遍历图的所有顶点，则表示这是个DAG，如果未能遍历玩所有顶点，则表示图有环。

算法框架是陈越老师的ppt里的：

image-20200326194155423

Python3实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # create graph
        graph = [[] for _ in range(numCourses)]
        indegree = [0]*numCourses
        for end, start in prerequisites:
            graph[start].append(end)
            indegree[end]+=1     
        # topological sorting
        queue = []
        cnt = 0
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        while queue:
            v = queue.pop(0)
            cnt += 1
            for w in graph[v]:
                indegree[w] -= 1
                if indegree[w] == 0:
                    queue.append(w)
        return (cnt==numCourses)

DFS

DFS算法：在深度优先搜索时，如果正在搜索某一顶点(还未退出该顶点的递归深度搜索)，又回到了该顶点，即证明图有环。(图片来自小象学院ppt)

image-20200326195653054

算法思路：

image-20200326195757463

Python3实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # create graph
        graph = [[] for _ in range(numCourses)]
        visited = [-1]*numCourses
        # Adjacency list
        for x,y in prerequisites:
            graph[y].append(x)
        # dfs
        def dfs(start, graph, visited):
            visited[start]=0
            for w in graph[start]:
                if visited[w]==-1:
                    if not dfs(w, graph, visited):
                        return False
                elif visited[w]==0:
                    return False
            visited[start]=1
            return True
        for x, y in prerequisites:
            if visited[y]==-1:
                if not dfs(y, graph, visited):
                    return False
        return True

BFS和DFS对比

时间复杂度上区别不是很大，空间上DFS略大。

三、总结

图论的问题面试时考的不多，且比较套路，基本都是BFS，DFS，最短路、最小生成树、拓扑排序之类的，python建图也不是太难。

推荐公众号文章：从拓扑排序到 Carthage 依赖校验算法

同时这道题在2018年阿里校招时真的出现了,上面公众号大神做的一个线上oj: DissCode