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

Question

[David Gegiya]

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

struct list {
    int data;
    int firstPeak;
    int secondPeak;
    list* next = 0;
};

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

При этом структура graph у меня в виде одномерного массива.
Как сделать для такой структуры алгоритм Прима?

Comments

[User700]

Существует алгоритм Краскала.
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...
Для данной структуры данных, думаю, он оптимальный.
Или имеете в виду этот: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...
Они аналогичные. Нужен только обязательно второй?

[David Gegiya]

User700, Нужен именно второй

Answer 1

[Rsa97]

Никакой принципиальной разницы не будет. Отличается только способ перебора рёбер в поисках минимального веса.

Answer 2

[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

Comments

[User700]

Хотя предварителльная сортировка может быть особо сложность алгоритмическую не уменьшит. Т.к. без неё не "ищем первое ребро...", а "ищем минимальное ребро..."; что так, что иначе, это один проход списка, но в первом случае найдём конечно раньше.

[User700]

Еще вопрос ориентированный ли граф