深入搜索。数字文件系统


DFS DFS
深度优先搜索 (DFS) 是图上的主要算法之一。该算法在 O(N + M) 中运行。
 
算法
首先,我们从顶部开始,考虑这个顶部的子项,如果我们从未输入过它们,那么我们从它们开始DFS


DFS DFS
深度优先搜索 (DFS) 是图上的主要算法之一。该算法在 O(N + M) 中运行。
 
算法
首先,我们从顶部开始,考虑这个顶部的子项,如果我们从未输入过它们,那么我们从它们开始DFS


二分图
 
二分图 - 一种图,其顶点可以分为两组,因此每条边连接来自不同集合的顶点。


通常在二分图的上下文中,会使用 颜色 顶点的概念。将图形分成两部分称为 着色 其顶点具有两种不同的颜色。每条边必须连接不同颜色的顶点。

DFS
 

算法

我们从任意顶点开始绘制,我们用任意颜色绘制。
当沿着每条边通过时,用相反的颜色绘制下一个顶点。
如果在迭代相邻顶点时,我们发现一个顶点已经被涂上了与当前顶点相同的颜色,那么图中存在一个奇数循环,这意味着它不是二分的。

算法可以描述如下:
给定一个有 n 个顶点和 m 条边的有向图。需要对其顶点重新编号,使每条边从编号较小的顶点指向编号较大的顶点。
换句话说,就是要找到一个顶点的排列(拓扑序)对应于图中所有边给定的顺序。
我们将使用深度优先搜索 (dfs(v))
如果我们在退出时将顶点添加到列表的开头 \(dfs(v)\) ,那么最后在此列表中,您将获得拓扑排序。
因此,所需的拓扑排序 —这是按退出时间降序排列的。