Поиск в глубину: различия между версиями
Debnatkh (обсуждение | вклад) (Init copy) |
Debnatkh (обсуждение | вклад) |
||
Строка 8: | Строка 8: | ||
Как их заполнить: давайте заведем таймер, отвечающий за время на текущий момент программы и будем обновлять информацию, когда заходим/выходим из вершины: | Как их заполнить: давайте заведем таймер, отвечающий за время на текущий момент программы и будем обновлять информацию, когда заходим/выходим из вершины: | ||
− | |||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
int tin[maxn], tout[maxn]; | int tin[maxn], tout[maxn]; | ||
int timer = 0; | int timer = 0; | ||
− | |||
void dfs(int v) { | void dfs(int v) { | ||
Строка 23: | Строка 23: | ||
tout[v] = timer++; | tout[v] = timer++; | ||
} | } | ||
− | </ | + | </syntaxhighlight> |
+ | |||
− | Время входа или выхода пригождается во многих алгоритмах, | + | Время входа или выхода пригождается во многих алгоритмах, например, при [[Поиск мостов|поиске мостов]], [[Поиск точек сочленения|поиске точек сочленения]]. |
Текущая версия на 00:29, 14 сентября 2019
Поиском в глубину (англ. depth-first search, DFS) называется рекурсивный алгоритм обхода дерева или графа, начинающий в корневой вершине (в случае графа её может быть выбрана произвольная вершина) Он рекурсивно обходит весь граф, и посещает каждую вершину ровно один раз. Посещенные вершины при этом отмечаются в массиве used.
Давайте его немного модифицируем, а именно, давайте сохраним в какой-нибудь массив, в каком порядке мы посещали вершины. Есть два способа это сделать - посчитать время входа DFS-а в каждую вершину и время выхода.
Давайте назовем массивы
tin
и tout
, где tin
— время входа, а tout
— время выхода из вершины.
Как их заполнить: давайте заведем таймер, отвечающий за время на текущий момент программы и будем обновлять информацию, когда заходим/выходим из вершины:
int tin[maxn], tout[maxn];
int timer = 0;
void dfs(int v) {
tin[v] = timer++;
for (int i = 0; i < g[v].size(); ++i) {
if (!used[g[v][i]]) {
dfs(g[v][i]);
}
}
tout[v] = timer++;
}
Время входа или выхода пригождается во многих алгоритмах, например, при поиске мостов, поиске точек сочленения.