Цель серого узла в поиске глубины графика

Question

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

Скажем В Vertex A есть два соседи B и C, а B имеет один сосед D.

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

Скажем, выбрав алфавитный заказ Посещает вершину б который в белом цвете и отметках как серый.

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

В настоящее время, отслеживание Б в сером и не больше Нигбарса. Следовательно, отметки B-> черный.

Снова возвращается в серой и посещает C, отмечает, чтобы c-> grey Больше нет соседних отметок C как черные

Наконец вернемся к и отметкам вершина A как черный Поскольку больше нет белых вершин и все как черное.

Answer 4

В DFS мы классифицируем края как вперед, на заднем, перекрестном краю и крах деревьев.

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

Грей: V уже обнаружен, но все вершины, которые доступны из V, еще не обнаружены. Таким образом, вершина V все еще в стеке.

Черный: V уже выпадает из стека. Раскрывается и закончен.

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