Назначение серого узла в графе поиска в глубину

Во многих реализациях поиска в глубину, который я видел (например: здесь ), код различает серую вершину (обнаружена, но не все ее соседи были посещены) и черную вершину (обнаружена и все ее соседи посещены) , Какова цель этого различия? Кажется, что алгоритм DFS никогда не посещает посещенную вершину, независимо от того, является ли она серой или черной.

При выполнении DFS любой узел находится в одном из трех состояний - до посещения, во время рекурсивного посещения его потомков и после посещения всех его потомков (возврат к своему родителю, т. Е. Фаза завершения). Три цвета соответствуют каждому из трех состояний. Одна из причин упоминания цветов и времени посещения и возвращения заключается в том, чтобы четко определить эти различия для лучшего понимания.

Конечно, есть фактическое использование этих цветов. Рассмотрим ориентированный граф . Предположим, вы хотите проверить на наличие циклов. В неориентированном графе, если рассматриваемый узел имеет черного или серого соседа, он указывает цикл (и DFS не посещает его, как вы упомянули). Однако в случае ориентированного графа черный сосед не означает цикл. Например, рассмотрим граф с вершинами 3 - и , с ориентированными ребрами , как , , . Предположим , что начинается DFS на , а затем посещена , то . Когда он вернулся в$G$$G$$A, B,$$C$$A \to B$$B \to C$$A \to C$$A$$B$$C$$A$ он проверяет, что уже посещен и является черным. Но на графике нет цикла.$C$

На ориентированном графе цикл присутствует тогда и только тогда, когда узел снова виден до посещения всех его потомков. Другими словами, если у узла есть сосед, который является серым, то существует цикл (а не когда сосед является черным). Серый узел означает, что мы в настоящее время исследуем его потомков - и если один такой потомок имеет ребро к этому серому узлу, то существует цикл. Итак, для обнаружения цикла в ориентированных графах вам нужно иметь 3 цвета. Могут быть и другие примеры, но вы должны понять.

В CLRS это упражнение, в котором вы можете удалить серый или черный цвет, и алгоритм отлично работает только с двумя цветами, другими словами, он на самом деле не нужен. Основная цель маркировки вершин - убедиться, что мы не сталкиваемся с бесконечным циклом, повторно посещая уже посещенные вершины.

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

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

Скажем Vertex А имеет двух соседей B и C и B имеет один сосед D .

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

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

Затем посещение D белого -> серого D -> больше нет соседей. следовательно помечает D-> черный .

Теперь вернемся к B в сером и больше не nieghbors. Отсюда отметки B-> черные .

AG снова возвращает A в сером цвете и посещает c, отмечая c-> Grey, соседи больше не отмечают C как черный

наконец, вернемся к A и пометим вершину A черным, поскольку белых вершин больше нет и все будет черным.

В DFS мы классифицируем ребра как передний край, задний край, поперечный край и край дерева.

Мы используем 3 цвета, чтобы классифицировать края. и эти цвета представляют состояние вершины, т.е. v. white: вершина v еще не обнаружена.

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

черный: v уже выпал из стека. обнаружен и закончен.

При выполнении DFS, если вы сталкиваетесь с серой вершиной через ребро e, то это задний край. Если вы сталкиваетесь с черной вершиной через ребро e, то это перекрестная кромка / передняя кромка. если вы встретите белую вершину, то вы будете вызывать DFS рекурсивно.