Поиск подключенных компонентов

Question

Я хочу найти связанные компоненты прямого ациклического графика с использованием набора узлов. Каким будет наиболее эффективный способ решения этой проблемы?

подсоединенного компонента: Если один из узлов является предшественником или наследников другого узла, они находятся в одной и той же компоненте связности.

Например, у меня есть следующий график и vector = [2,4,5,6,3]. Для этого вектора есть два связанных компонента, как показано ниже.

C1 = [2,4,5,6] 
C2 = [3] 

Мое решение:

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

Как вы думаете?

Answer 1

Я надеюсь, что я понимаю ваше определение подключенного компонента ... Если это так

Я согласен с @anonymous, вы можете просто сделать граф неориентированным и найти связные компоненты с помощью простого ДФСА ...

Я не совсем понимаю вашу оригинальную мысль, по крайней мере, я думаю, что реализация будет немного сложной, скажем, для ребер {1 -> 2, 2 -> 4, 3 -> 4}, Узел # 1 и # 3 будут отсортированы в начале списка, и как вы можете узнать, что {1,2,3,4} - это один подключенный компонент?

Во всяком случае, сложность же с простым методом ДФСА, в лучшем случае, что O (V)

(Если кто-то думают, что этот ответ является правильным, пожалуйста, дайте всем кредитам на @anonymous!)

Answer 2

путь найти связную компоненту нечто вроде следующего:

while(anymore_root_vertex_tostartfrom){ 
 
    vertex v=pick_a_vertex; 
 
    remove vertex from root_vertex_list; 
 
    initialize connected_comp_list_of_vertices; 
 
    do a breadth_first traversal from this vertex 
 
    keep adding the vertex you encounter in bfs to connected_comp_list_of_vertices 
 
    of that root 
 
}

I woul d предложите прочитать дополнительную информацию о обработке графа. Поиск подключенного компонента, BFS, обход DFS имеют довольно стандартные методы. Отличная книга на эту тему: Skiena's Algoritham Design Manual