Я пытаюсь написать алгоритм, чтобы определить, является ли данный граф односвязным.Определение домашней работы говорит, что односвязный граф означает, что между двумя узлами существует не более одного простого пути.
Здесь я вижу много ответов, которые говорят, что для каждого узла используется DFS-посещение, и если есть черный узелпосетили, значит, есть два простых пути.В результате данный граф не просто связан.
Я переписываю алгоритм DFS, чтобы достичь этого, но проблема в том, что он может решить весь данный граф, кроме одного частного случая.Я уже рассмотрел ситуацию, когда есть несколько ребер между двумя узлами, но это не работает.
Так что мой вопрос в том, есть ли какой-то особый случай, который не может быть решен с помощью DFS-посещения для каждого узла?
def dsf(self, source):
source.color = 'g'
for node in source.next:
if node.color == 'w':
if not self.dsf(node):
return False
elif node.color == 'b':
return False
source.color = 'b'
return True
, если dsf встретится с черным узлом, он вернет False изавершить функцию.
def singly(self):
for node in self.nodes:
if not self.dsf(node):
return False
self.__clear()
return True
И затем с помощью этой функции проверить каждый узел на графике.Self .__ clear может сбросить весь цвет узла обратно на белый.
Алгоритмы работают для всех случаев, кроме одного особого случая.