Поиск максимума прямого графика

Question

Мне присвоен Directed Graph, который не взвешен. Если вы путешествуете только с направлением ребер, если мне задана вершина, я хочу знать, доступна ли любая другая вершина. Если график равен Complete Graph, это очевидно. Меня интересует случай, когда график неполный.

Что касается реализации, я сохраняю каждое соединение в multimap. multimap Ключ кромки ключа multimap Значение - краевая головка. Так сказать, что у меня есть следующие пары:

• (1, 2)
• (2, 3)
• (1, 4)

В этом графике, если 1 была данная узла, каждый узел может быть прямо или косвенно достигнут. Если бы другая пара была добавлена ​​к multimap: (5, 3) 5 не было бы прямо или косвенно достижимо от 1, и ни один узел, кроме 3, не был бы доступен с 5, поэтому никакой узел на этом графике не смог бы достичь всех других узлы.

Мой вопрос заключается в следующем: если все, что я делаю с этим графом, проверяет, может ли один узел достигать всех других узлов, следует добавить ребра к multimap, чтобы сделать все косвенные соединения прямыми, а затем проверить, подключен к данному узлу? Или есть лучший способ сделать это?

Answer 1

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

Если вам действительно нужно запомнить эту информацию, используйте отдельную структуру для достижимости.