Java — односвязные ориентированные графы
Согласно определению, доступному в 3-м издании CLRS, односвязный ориентированный граф — это тот, в котором для каждой пары вершин (u, v) существует не более 1 уникального пути из u-> v. Теперь большинство ответов, которые я прочитал, утверждают, что мы запускаем DFS из каждой вершины графа, и если в любом случае мы находим Поперечный край или Передний край, тогда граф не является односвязным. Я могу понять концепцию для передних ребер, но запустить этот алгоритм на этом графике
1 -> 2 <- 3 даст нам результат, который это НЕ односвязный, тогда как этот граф односвязный. У нас есть перекрестие от 3 -> 2 или 1 -> 2, в зависимости от того, с какого вертикали началась вся эта процедура (1 или 3). Если мы начнем DFS с вершины 2, то у нас есть 2 поперечных ребра
1 -> 2 и 3 -> 2. Может кто-нибудь уточнить, пожалуйста?
Решение
Ответ, который предполагает запуск DFS с каждого узла, означает, что вы должны остановить DFS, если вы не можете продолжить (не осталось исходящих ребер), и не начинать с другого узла.
В этом случае, в вашем примере, вы начнете (w.l.o) с 1, откроете 2, и все готово. Без задних кромок
Далее, это совершенно новый DFS, начните с 3, найдите 2 и сделайте, опять же без задних краев.
Идея в основном заключается в проверке атрибута по определению. Вы делаете DFS с каждого узла u пока вы не найдете это для каждого v есть не более одного пути от u в v (DFS исчерпан) или вы нашли в какой-то момент 2-й путь от u в vи тогда все готово.
Другие решения