Глубина первого поиска края дерева классификации
У меня есть основной вопрос о классификации ребер DFS: у меня есть ориентированный граф с ребрами: 1-> 2, 2-> 3 и 1-> 3. Классификация ребер для 1-> 2 — ребро дерева, 2-> 3 — ребро дерева. Я запутался относительно того, что классификация 1-> 3 будет: передний край, задний край или край дерева?
Решение
Согласно определению классификации краев (см. http://en.wikipedia.org/wiki/Depth-first_search например), 1-> 3 будет передним краем.
Это было бы потому, что:
1-> 2: край дерева, потому что 2 является потомком 1, а 2 еще не обнаружена.
2-> 3: край дерева, потому что 3 является потомком 2, а 3 еще не обнаружен.
1-> 3: передний край, потому что 3 является потомком 1 и уже был обнаружен.
3 является потомком 1 как напрямую, так и через 2.
Другие решения
Других решений пока нет …