Задача теории сетей и графов

Question

У вас N компьютеров, и [Ca, Cb] означает, что a подключен к b, и эта связь симметрична и транзитивна. Проблема состоит в том, чтобы написать программу, которая проверяет, все ли компьютеры связаны и общаются друг с другом.

Предпочтителен эффективный по времени алгоритм.

Answer 1

Это называется Graph Connectivity . Прочтите об этом, и вы сможете решить свою проблему.

Answer 2

Любого поиска графа, который не пересекает узел несколько раз, должно быть достаточно. Есть много вариантов: http://www.algorithmist.com/index.php/Graph_Connectivity Я бы, наверное, выбрал DFS или BFS.

Answer 3

потому что вы говорите, что эффективный по времени алгоритм предпочтителен. Таким образом, DFS - лучший алгоритм для U .. обратите внимание, что размер вашего преимущества в сетевом компьютере невелик DFS: http://en.wikipedia.org/wiki/Depth-first_search