[Appolinariya_]

Текст задачи: В текстовом файле содержится список инциденций неориентированного несвязного граф, содержащего n вершин и m ребер. Составить процедуру ввода данных списков и формирования их в виде массива линейных односвязных списков. Описать процедуру, определяющую наименьшее количество ребер, которое необходимо добавить, чтобы граф стал связанным.

Интересует, нужно ли использовать какой-нибудь обход (мне кажется, что здесь можно использовать обход в глубину)?
Подскажите,пожалуйста,алгоритм задачи. Код попробую написать сама

[lmikle]

Сообщение от wiki

Граф G называется связным, если для любой пары различных вершин этого графа существует цепь, соединяющая эти вершины.

Если для графа G можно указать пару различных вершин, которые не соединяются простой цепью, то граф называется несвязным.

Соответственно, если проблемы с загрузкой, то нужен пример файла.

По кол-ву ребер. Как видно из определений сверху и того, что граф неориентированный, то в данном случае достаточно проанализировать списки и выяснить, какие из них не имеют общих вершин. Точнее надо их сгруппировать так, что бы списки с общими вершинами были в одной группе. кол-во полученных групп будет на 1 больше, чем нужное тебе кол-во ребер. По поводу группировки. После загрузки списков у тебя есть массив этих списков. пытайся их объединить по общим вершинам. Как только ты пройдешь весь массив и не сможешь объединить ни одного списка, то оставщиеся списки - это кол-во несвзанных между собой подграфов. Т.к. граф неориентированный, то достаточно просто соединить любую вершину такого подграфа с любой другой вершиной другого подграфа, что бы связать их, т.е. "организовать" путь между любыми 2мя вершинами в полученном общем графе.

ЗЫ. Не готов так с налета строго доказать, что эта эвристика правильная, но по ощущениям - должно работать. Т.е. полный обход графа тут не нужен. Даже, вроде, в результате задача перестает быть NP-полной. Особенно, если верщины сортировать и использовать двусвязные списки для более быстрого поиска.