Алгоритм поиска корня ориентированного графа

Question

Я легко могу определить, какой узел является корнем ориентированного графа, посмотрев на него, но если я хочу использовать алгоритм, чтобы найти его, мне начинать с DFS?

Answer 1

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

Еще один способ думать об этом - использовать DFS для проверки всех ребер.графика.Любая вершина, которая никогда не появляется на приемном конце ребра, будет «корнем».