Вопрос или проблема
Я читаю статью Идентификация циклов с использованием DJ-графов авторов Сридхара и др. В этой статье они представляют следующую классификацию ребер в порядке обхода графа в глубину (в частности DJ-графа, но это различие не так важно для данного вопроса).
- sp-back edge, если y = x или y является предком x в минимальном остовном дереве
- sp-tree edge, если x является родителем y в минимальном остовном дереве
- sp-forward edge, если x является предком, но не родителем y в минимальном остовном дереве
- sp-cross edge, если x и y не имеют отношения предка и потомка.
В статье представлен пример обхода графа в глубину, который я приложил ниже.
В рамках данного вопроса мы можем игнорировать различия между пунктирными и сплошными ребрами.
На основе нумерации DFS, минимальное остовное дерево выглядит следующим образом:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9
+--> 6
Ребра типа sp-back обозначены пузырьками на их конечных узлах. Таким образом, 7->3, 4->3, 5->1 являются сп-back ребрами.
Мой вопрос: почему 9->5 не обозначено как sp-back edge? Оно удовлетворяет критериям сп-back ребра, а именно, узел 5 является предком узла 9 (5->7->8->9 в минимальном остовном дереве).
Я написал немного тестового кода для классификации ребер по критериям, изложенным в этой статье, и он соответствует моему мнению. 9->5 классифицируется как sp-back edge в моем коде.
Буду признателен за любые подсказки.
Текст не совсем ясно объясняет, что значит “y является предком x в минимальном остовном дереве”. В данном случае это не означает, что мы видим y перед тем, как увидеть x. Скорее, это означает, что вы нашли узел x, когда искали всех детей y.
После “5” мы переходим к “6”, и на этом заканчиваем с “5”. Мы не исследуем “1”, потому что уже были там. Поэтому, хотя мы позже посещаем “9”, мы не посещаем его из-за “5”.
Ответ или решение
Вопрос о том, почему между узлами 9 и 5 в графе DJ не указана обратная сквозная (sp-back) граница, требует более глубокого понимания определения предков и их последовательности в контексте прохода в глубину (DFS).
Согласно классификации, приведенной в статье Сридхара и других, узел y считается предком узла x, если x был обнаружен в процессе обхода дочерних узлов y. Это означает, что если во время выполнения DFS мы изначально исследовали узел y и, в процессе поиска его потомков, пришли к узлу x, то x будет потомком y.
В данной ситуации, хотя узел 5 действительно является предком узла 9 по иерархии (через узлы 7 и 8), существует важное замечание относительно порядка обхода: после посещения узла 5 DFS перемещается к следующему узлу, 6, и, завершив исследование этого узла, возвращается к родителю (в данном случае к 5). Однако после того, как мы завершили обход 5, мы не исследуем узел 1 снова, так как он был закончен ранее в процессе обхода.
Таким образом, узел 9 будет обнаружен после завершения узла 5, но не в рамках дочернего обхода узла 5, поскольку все потомки были изучены, и возвращение к узлу 5 не повлечет за собой дальнейшего изучения узла 9. Это означает, что 9 не может классифицироваться как sp-back к 5, поскольку, когда мы изучали узел 5, мы не находимся на пути обратно к 9 через его потомков.
В результате, хотя 9 действительно следует от 5 в порядке обхода, с точки зрения классификации границ DFS, они не имеют отношения “предок-потомок” в контексте данной классификации, и, следовательно, не может быть указана sp-back граница между этими двумя узлами. Таким образом, если ваш код классифицирует 9->5 как sp-back, это указывает на некоторую неполную интерпретацию правил, поскольку это противоречит определению предковой связи, приведенному в статье.
В заключение, данное объяснение подчеркивает важность интуитивного понимания порядка обхода и предков в графах и позволит вам лучше классифицировать граничные условия в соответствии с определениями, приведенными в первоначальном документе.