алгоритм для проверки того, содержит ли G arborescence

Question

Подсвечивание ориентированного графа G является корневым деревом, так что существует направленный путь от корня до любой другой вершины графа. Дайте эффективный и правильный алгоритм, чтобы проверить, содержит ли G arborescence и его временную сложность.

Я мог думать только о запуске DFS/BFS с каждого узла, пока в одной из DFS все узлы не будут закрыты. Я думал об использовании алгоритма min spanning tree, но это также касается только ненаправленных графиков

Есть ли какой-нибудь другой эффективный алгоритм для этого?

Я нашел следующий вопрос, в котором утверждается, что существует алгоритм O (n + m) для него, может ли кто-нибудь помочь в решении проблемы?

Answer 1

То, что вы ищете, - это так называемый алгоритм Эдмонда. Минимальные алгоритмы остовного дерева не будут работать на ориентированных графах, но это идея. Задача MST стала проблемой предварения, когда график направлен, а преддверия - то, что вы описали выше.

Наивная сложность - это O (EV), как алгоритм Prim для неориентированной проблемы MST, но я уверен, что есть более быстрые ее реализации.

Для получения дополнительной информации вы можете проверить страницу вики:

Edmonds Algorithm

Answer 2

Я думаю, что это намного проще, чем я думал. Что-то в подобных строках уже упоминалось в начале потока. Таким образом, начните обход DFS на любом узле графика, используя BFS, и достигните того, что когда-либо сможете, а затем, как только вы закончите. Просто возьмите следующую невидимую вершину и снова выполните обход BFS, и если вы столкнулись с уже обработанным узлом, это уже обработанное поддерево, и все узлы, достигаемые через этот узел, будут достигнуты узлом через другой узел, поэтому сделайте текущий узел как родительский элемент этого нового дерева.

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

edgeCb() 
{ 
    // Already processed and has no parent means this must a sub tree 
    if (g->par[ y ] == -1 && g->prc[ y ]) 
     g->par[ y ] = x; // Connecting two disconnected BFS/DFS trees 
    return 1; 
} 

graphTraverseDfs(g, i) 
{ 
    // Parent of each vertex is being updated as and when it is visited. 
} 

main() { 
. 
. 
for (i = 0; i < g->nv; i++) 
    if (!g->vis[ i ]) 
     graphTraverseDfs(g, i); 
. 
. 
} 

Answer 3

Прежде всего отметит, что определение для древовидного ориентированного графа, приведенного в приведенном выше вопросе немного отличается от приведенного в, например, Wikipedia: определение вашего вопроса не требует, чтобы путь был уникальным, и не требует, чтобы исходный ориентированный граф G был взвешенным. Таким образом, решение должно быть проще, чем тот, который обрабатывается Edmond's Algorithm.

Как насчет следующего: первая часть должна найти правильный корень. После того как найден правильный корень, запуск простой DFS на графе G, начиная с этого корня, должен позволить нам создать нужное дерево, и мы закончили. Итак, как мы можем найти такой корень?

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

• Если осталось больше одного края, перейдите все оставшиеся края и найдите те, которые имеют нулевую степень. Если найдено более одного - тогда мы не сможем построить нужное дерево, так как они не могут быть достигнуты друг от друга.Если здесь находится только один край, это наш корень.

Сложность - это O (ребра + вершины), например, представление списка смежности графа.