@Davidaa_WoW

Как реализовать алгоритм Прима для графа в виде списка смежных вершин?

В сети видел много различных алгоритмов Прима для графа, который реализован в виде матрицы смежности. Однако у меня он сделан в виде списка смежных вершин. Структура следующая:
struct list {
    int data;
    int firstPeak;
    int secondPeak;
    list* next = 0;
};

struct graph {
    int data;
    list* List = new list;
};


При этом структура graph у меня в виде одномерного массива.
Как сделать для такой структуры алгоритм Прима?
  • Вопрос задан
  • 35 просмотров
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Никакой принципиальной разницы не будет. Отличается только способ перебора рёбер в поисках минимального веса.
Ответ написан
Комментировать
@User700
1) Полагаю оптимально предварительно отсортиоровать рёбра по весу от минимума.
2) Нужно еще хранить множество вершин. Хорошо подойдёт для этого храниние в виде "битовой карты", т.е. массива бит (массива bool): std::vector от bool, назовём массив IN(n), т.к. всё равно придётся их добавить все. n это кол-во вершин (и размер массива).
3) Также результат представится в виде множества рёбер. Можно также использовать список рёбер для представления оставного дерева.
4) Алгоритм.
Если n == 0, то возврат.
IN[0] = true; v_count = 1.
Пока v_count меньше n
Ищем первое ребро из списка, которое соединяет вершины i и j (или наоборот!), при условии IN[i] & !IN[j]: добавляем его в список-ответ, IN[j] = true, ++v_count.

ПС
А это для чего такое?
list* List = new list;

Используйте std::forward_list
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы