Нужна помощь в решении проблемы с использованием графиков в C

Question

Я пишу проект для класса алгоритма, и мне действительно нужна помощь!Вот проблема:

У меня есть набор имен, подобных этому N = (Джеймс, Джон, Роберт, Мэри, Патрисия, Линда Барбара), которые хранятся в дереве RB.Исходя из этого набора имен, формируется серия таких пар:

(Джеймс, Мэри) (Джеймс, Патриция) (Джон, Линда) (Джон, Барбара) (Роберт, Линда) (Роберт,Барбара)

Теперь мне нужно объединить элементы таким образом, чтобы я могла сформировать n подгрупп с условием, что каждая пара соблюдается, и группа имеет наименьшее возможное количество элементов.

С парамив примере они сформируют две группы (Джеймс, Мэри, Патриция) и (Джон, Роберт, Барбара, Линда).

Задача состоит в том, чтобы вернуть максимальное количество сформированных групп и количество мужчин и женщин.в группе с максимальным количеством элементов.

В этом случае это будет 2 2 2

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

Проблема в том, что граф не будет полностью связан.Мне также нужно найти способ сопоставить имена с краями графа и наоборот.Можно ли индексировать края строкой?

Каждая помощь действительно ценится :) Спасибо за совет!

Answer 1

Вам не нужно находить минимальное связующее дерево. Это действительно для того, чтобы найти «лучшие» ребра в графе, которые все еще будут держать граф связанным. Другими словами, вам все равно, как связаны Джон и Роберт, просто они между собой.

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

В вашем примере Джеймс связан с Мэри, а также Джеймс связан с Патрисией. Ни один другой человек не соединяется ни с одной из этих трех вершин (если бы они это сделали, у вас была бы другая пара, которая включала их), поэтому они образуют единую группу (Джеймс, Мэри, Патриция). Точно так же все Джон, Роберт, Барбара и Линда связаны друг с другом.

Ваша задача - сформировать график и найти все связанные подграфы, которые не пересекаются друг с другом.

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

Answer 2

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

Answer 3

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

dfs() {<br> int group 0;<br> for(int i=0;i<num_nodes;i++) {<br> if(nodes[i].visited==false){<br> explore(nodes[i],group);<br> group++;<br> }<br> }

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

(извините за мой плохой английский)!