Как поиск в глубину выполняет поиск графа?

задняя часть алгоритм обратный

Идея: Для вновь обнаруженной вершины v, если у нее есть ребро, которое еще не исследовано, исследовать вдоль этого ребра. Если все ребра v были исследованы, вернитесь к тем ребрам, где v имеет начальную точку. Пока не будут исследованы все вершины, достижимые из исходного источника. Если есть еще неисследованные вершины, определите их как новую исходную вершину и продолжите описанный выше процесс.

Как лабиринт, попробуйте все возможные результаты, не рискуйте, просто до пересечения первой бифуркации, продолжайте исследовать

Исследуйте весь график

DFS(V,Adj):
    parent={}
    for s in V: //遍历图中所有的点
        if s not in parent: //点没有遍历过就继续探索
            parent[s]=None //源点不设置父节点
            DFS-Visit(Adj,s) //探索当前源顶点能够到达的所有的点

Для исходной вершины s реализация DFS

DFS-Visit(Adj,s):
   for v in Adj[s]: //遍历所有的边
       if v not in parent: //当前边没有遍历过
           parent[v]=s //记录已经遍历
           DFS-Visit(adj,v) //优先探索当前节点的边,完成之后，再执行回溯（通过循环实现）

Возьмем ориентированный граф в качестве примера
Предполагая, что все вершины пройдены в алфавитном порядке, то есть V=[a,b,c,d,e,f], исходный граф имеет вид

  1. Первый шаг — исследовать ребро от a до b и найти, что у b все еще есть ребро, и продолжать движение вниз до тех пор, пока d, d не будет иметь ребра, которое идет вниз, и первое выполнение DFS-Visit не завершится.

2. Начните обратно, сначала обратный откат к родительскому узлу E d, также нет, до A, другой край a - это d, но D был исследован и больше не работает

3. Для выполнения исследовательского источника, в данном случае b, но исследовали b, c, а затем исследовали только одну найденную неисследованную сторону, соответствующую f.

  1. Продолжайте заменять исходную точку до тех пор, пока f не останется новых неисследованных ребер, и, наконец, исследование DFS сгенерирует два дерева в глубину.

Дерево поиска в глубину относится к дереву, сгенерированному DFS, и результатом являются две части, на которые указывают оранжевые стрелки на рисунке 3.

временная сложность

O(V+E); Его правила обхода по-прежнему должны проходить все узлы один раз. При каждом изменении только те, которые не были пройдены, будут пройдены один раз.

Какова цель поиска в глубину?

1. Классификация краев

  • край дерева. Если вершина v найдена первой при поиске ребра (u,v), то (u,v) является ребром дерева, например (a,b) в графе
  • положительный край. Недревесное ребро от u до v, такое как (a, d) в графе, ребро от a до d есть, но оно не входит в дерево
  • противоположная сторона. Ребро, соединяющее u с вершиной-предком v, например (d,b) в графе
  • поперечный край. В результирующем дереве между двумя вершинами нет отношения родитель-потомок. Например (g,d) на рисунке

В алгоритме оценку края дерева можно увидеть через родителя, а противоположностью родителя является ребро дерева, которое можно идентифицировать;

Чтобы судить об обратном ребре, можно начать метку в исходной точке и сложить все проходящие узлы в стек, если вершина, полученная в следующий раз, окажется в стеке, то это ребро будет обратным ребром;

Как узнать, есть ли цикл в графе?

Граф G имеет цикл тогда и только тогда, когда в графе есть обратное ребро. Доказательство следующее:

  • Существование цикла доказывает, что существует обратное ребро. Предположим, что точка выбрана из кольцаv_0, как первая вершина обхода DFS, докажите (v_k,v_0) является обратной стороной: известный факт,v_1Перед посещением,v_0Должно быть, чтобы быть посещены,v_kПеред посещением,v_0должны быть доступны, когда доступ кv_kследующий просмотрv_0когда,v_0уже находится в стеке, то (v_k,v_0) это обратная сторона

  • Есть и обратная сторона, которая доказывает, что цикл есть. Сначала должно быть ребро дерева от s до t, а затем от t до s — обратное ребро, которое должно быть циклом

2. Планирование работы

Джоб сам по себе является ациклическим ориентированным графом, и между вершинами должен быть определенный порядок.

Алгоритм, который он использует, называется топологической сортировкой. Топологическая сортировка использует DFS внутренне. На выходе получается обратный порядок вершин на момент завершения, и он сортируется (указатель родителя был записан раньше, а реальное выполнение — это родительский указатель). первый)

Результатом этого упорядочения является то, что, если предположить, что все вершины в графе расположены на одной горизонтальной линии, все направления слева направо.

Доказывать

Нужно только доказать, что для любого ребра e=(u, v) после выполнения v выполняется u

  • Доступ к u происходит до v: поскольку между u и v есть ребро, это должен быть доступ к v до выполнения u, а u может быть завершено после завершения v.
  • Доступ к v предшествует u: так как между u и v есть ребро, если доступ к v осуществляется первым, если есть путь от v к u, будет цикл, поэтому u вообще не будет выполняться, что то есть v будет выполняться первым

приложение

Введение в алгоритмы (MIT 6.006, лекция 14)

Категории