Как найти минимальное количество дополнительных ребер, необходимых для завершения соединения?

Допустим, нам дано количество узлов и ребер, N и M соответственно. И затем нам дается, какие из узлов связаны. Как нам найти минимальное количество дополнительных ребер, необходимых для завершения соединения, чтобы вы могли посетить каждый узел? Найдя ответ, вы сможете пройти к каждому узлу либо напрямую, либо через другой узел, чтобы добраться до цели.

Пример ввода:

4 2 (Узлы и ребра)

0 1 (узел 0 и узел 1 соединены)

2 3 (узел 2 и узел 3 соединены)

Что тогда должно дать нам ответ 1, нам нужно одно дополнительное ребро для завершения соединения.


graph algorithm traversal
person Geir    schedule 14.01.2016    source источник
comment
Вы имеете в виду ребра (соединения, которые вы их называете), потому что добавление дополнительных вершин не имеет смысла.   -  person Selçuk Cihan    schedule 14.01.2016
comment
Да, извините, я имею в виду края.   -  person Geir    schedule 14.01.2016

Ответы (2)


arrow_upward
3
arrow_downward

Все, что вам нужно, это:

1) Найдите связные компоненты. Это можно сделать с помощью dfs или bfs. В вашем примере это компоненты 0, 1 и 2, 3 соответственно.

2) Затем вам нужно перебрать все компоненты и соединить любые две вершины для каждых двух последовательных компонентов. Таким образом вы соединяете первую и вторую компоненты, затем вторую и третью компоненты и так далее... В вашем примере вы можете соединить любую из вершин 0, 1 с любой из вершин 2, 3. Например, вы можете соединить вершины 0 и 2.

Легко видеть, что если общее количество компонентов равно C, то ответом будет C - 1 дополнительных ребер.

person Edgar Rokjān    schedule 14.01.2016
comment
Зачем мне нужно использовать BFS/DFS? Разве мы уже по входным данным не знаем, какие компоненты соединены? - person Geir; 14.01.2016
comment
@Geir Как я понимаю, у нас есть произвольный входной график. Так что мы ничего не знаем о его связных компонентах. Вот почему нам нужен какой-то поиск, например dfs. - person Edgar Rokjān; 14.01.2016
comment
Ах хорошо! Теперь я понимаю. Однако я не могу правильно выполнить все тестовые примеры с моим кодом для решения, которое вы дали... Вы видите что-то, что можно улучшить? pastebin.com/NMEUdswV . - person Geir; 14.01.2016
comment
Я просмотрел ваш код, не проверяя деталей. Главное, что я хочу отметить, это то, что этот код является избыточным. На самом деле вам не нужно заставлять dfs возвращать bool. Вы можете проверить все вершины, как вы это делаете сейчас, начать dfs с тех, которые еще не посещались, и пометить все достижимые вершины как посещенные. Таким образом, если вы начинаете dfs с непосещенной вершины, вы отмечаете один компонент целиком. - person Edgar Rokjān; 14.01.2016
comment
Большое спасибо за помощь! Теперь я обнаружил, что это сделало мой код немного медленнее, чем должно было быть: D - person Geir; 14.01.2016
comment
Теперь он проходит все тесты? - person Edgar Rokjān; 14.01.2016

arrow_upward
0
arrow_downward

Минимальное количество подключений, необходимых для подключения вашего графа, равно N-1. Но это справедливо, если нет узлов с 0 соединениями.

Попробуйте представить путь, напоминающий дизайн связанного списка. Каждый узел имеет степень ровно 2, за исключением двух концов. Таким образом (предположим, что ваше соединение не направлено), начиная с любого узла, вы можете достичь своей цели, просто посетив следующий, еще не посещенный узел.

Если M>N-1, вы можете искать узлы, у которых больше соединений, чем необходимо, и продолжать оттуда.

Попробуйте подсчитать дополнительные соединения и сравнить их с минимальным необходимым числом (N-1).

person 0gap    schedule 14.01.2016