深入搜索。数字文件系统


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


Training problem

DFS：开始 (C++)

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


Training problem

DFS：开始（Python）

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


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

DFS. 
 

算法

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

Training problem

二分图

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

Training problem

拓扑排序