почему увеличение порядка сообщения не дает приемник (узел в сильно связанном компоненте приемника соответствующего DAG графа) узел в графе?

Читая о графах... говорят, что каждый граф является DAG-ориентированным ациклическим графом своих сильно связных компонентов. Следовательно, чтобы найти эти сильно связанные компоненты, нужно найти узел в стоковой части графа.

pre no :- Предварительный порядок — это список вершин в том порядке, в котором они были впервые посещены алгоритмом поиска в глубину. поэтому его соответствующий предварительно нет.

Точно так же сообщение № :- Поступорядочение представляет собой список вершин в том порядке, в котором они были в последний раз посещены алгоритмом DFS. соответствующий пост нет

теперь самый высокий пост дает исходный узел (правда понимаете), но почему не возрастающий порядок поста не дает часть приемника?

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

Зачем нам переворачивать график?


graph algorithm graph-algorithm depth-first-search
person user770914    schedule 21.10.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Это из-за характеристики сильно связанных компонентов. в нем говорится, что каждый узел компонента должен достигать всех остальных узлов компонента. с первой DFS вы найдете все узлы, до которых может добраться узел. dfs обратного графа дает вам все узлы, из которых можно получить доступ к узлу.

чтобы найти полный компонент, важно полагаться на временные метки первой dfs.

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

надеюсь, я вас правильно понял, и это помогло :)

person Matthias Kricke    schedule 10.11.2012

arrow_upward
0
arrow_downward

Потому что самый низкий номер сообщения может быть даже в исходном SCC. Представьте, что исходный SCC (SCC1) представляет собой кольцо/петлю из 3 узлов, a, b и c, где ребро соединяет a с другим SCC (SCC2), детали которого нам не нужны. a,b,c не имеют других ребер. Если DFS идет от a к b и c, то пересекает ребро от a до SCC2. В этом случае наименьший порядковый номер на графике соответствует номеру c, который явно является исходным узлом SCC, а не узлом SCC приемника.

person Bhavika Khare    schedule 13.01.2021