Алгоритм Прима

В данной статье я бы хотел объяснить работу алгоритма Прима. Алгоритм используется для нахождения минимального остовного дерева. Сам алгоритм очень прост, в статье хотел бы поделиться своей реализации на языке Go.

Граф — это структура данных в которой хранятся вершины и связи между ними. Удобнее всего представлять графы в виде матрицы смежности.
Матрица смежности — эта квадратная матрица, размер матрицы равен количеству вершин в графе. В ней хранится информация о соседях вершин графа.
Минимальное остовное дерево — это поиск минимального количества ребер, чтобы из одной любой вершины графа попасть в любую другую вершину графа. Не стоит забывать про отсутствие циклов в дереве.
Приоритетная очередь — по структура данных, внутри которой, в отличие от обычной очереди элементы отсортирированы по приоритету (в нашем случае по весу). Элементы с наивысшим приоритетом извлекаются первыми.

Структура Graph: Структура содержит внутри себя двумерный срез (матрица смежности).
NewGraph: Конструктор для создания Graph.
AddEdge: Функция для добавления соседей вершины.

// Graph представляет граф с матрицей смежности type Graph struct { adjacencyMatrix [][]int } // NewGraph создает новый граф func NewGraph(vertexCount int) *Graph { matrix := make([][]int, vertexCount) for i := range matrix { matrix[i] = make([]int, vertexCount) } return &Graph{adjacencyMatrix: matrix} } // AddEdge добавляет ребро в граф func (g *Graph) AddEdge(from, to, weight int) { g.adjacencyMatrix[from][to] = weight }

Для реализации приоритетной очереди мы используем структуру данных под названием куча (heap) из пакета стандартной библиотеки container/heap. Для этого нам нужно реализовать методы Len(), Less(), Swap(), Push(), Pop().

// Item представляет элемент с приоритетом type Item struct { value int weight int index int } // PriorityQueue для хранения рёбер с приоритетом type PriorityQueue []*Item // Len возвращает количество элементов в приоритетной очереди. func (pq PriorityQueue) Len() int { return len(pq) } // Less сравнивает два элемента очереди по их весу. func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight } // Swap меняет местами два элемента в очереди по их индексам i и j. func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] } // Push добавляет новый элемент в приоритетную очередь. func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Item)) } // Pop удаляет и возвращает элемент с наивысшим приоритетом (наименьшим весом). func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] old[n-1] = nil // избегаем утечек памяти item.index = -1 // для безопасности *pq = old[0 : n-1] return item }

Начальные условия:

Срез вершин unvisited, в котором хранятся все вершины.
Приоритетная очередь, которая отвечает за поиск соседа с минимальным весом.
Матрица смежности, в которой мы записываем получившееся минимальное остовное дерево.

Шаг 1: Из слайса unvisited выбираем случайную вершину. У этой вершины просматриваем всех соседей и выбираем соседа с минимальным весом ребра. Добавляем выбранную вершину в слайс visited.

Шаг 2 и последующие: У вершин из слайса unvisited просматриваем всех соседей и выбираем соседа с минимальным весом ребра. Добавляем выбранную вершину в слайс visited.Проделываем шаги до тех пор, пока слайс unvisited не окажется пустым.

Результатом работы алгоритма является остовное дерево минимальной стоимости, а точнее её матрица смежности.

// Prim реализует алгоритм Прима func (g *Graph) Prim() (adjacencyMatrix [][]int) { n := len(g.adjacencyMatrix) // количество вершин в графе visited := make([]bool, n) pq := &PriorityQueue{} heap.Init(pq) // Создание матрицы смежности для минимального остовного дерева adjacencyMatrix = make([][]int, n) for i := range adjacencyMatrix { adjacencyMatrix[i] = make([]int, n) } start := generateAndPrintRandomNumber(len(g.adjacencyMatrix)) // выбираем случайную вершину // Добавляем начальные рёбра у стартовой вершины for i, weight := range g.adjacencyMatrix[start] { if weight > 0 { // Проверяем, есть ли ребро heap.Push(pq, &Item{value: i, weight: weight}) } } visited[start] = true // отмечаем стартовую вершину посещенной fmt.Println("Минимальное остовное дерево:") for pq.Len() > 0 { // Извлекаем рёбра с минимальным весом edge := heap.Pop(pq).(*Item) if visited[edge.value] { // пропусукаем вершину, если она уже песещенная continue } visited[edge.value] = true // отмечаем вершину посещенной fmt.Printf("Ребро: %d - %d, вес: %d\n", start, edge.value, edge.weight) adjacencyMatrix[start][edge.value] = edge.weight // Добавляем новые рёбра для вершины с минимальным весом for i, weight := range g.adjacencyMatrix[edge.value] { if !visited[i] && weight > 0 { // Проверяем, есть ли ребро heap.Push(pq, &Item{value: i, weight: weight}) } } start = edge.value } return adjacencyMatrix // возврат матрицы смежности для минимального остовного дерева } // Функция для генерации и вывода случайного числа func generateAndPrintRandomNumber(max int) int { // Создание нового генератора случайных чисел r := rand.New(rand.NewSource(time.Now().UnixNano())) // Генерация случайного числа randomNumber := r.Intn(max) fmt.Println("Случайное число:", randomNumber) return randomNumber }

Полное и подробное описание работы алгоритма можно найти в моем GitHub.

Если вам нравится, как и о чем я пишу – то буду благодарен за подписку на мой ТГ-канал Go Alive (так вы точно не пропустите новые статьи).

Начальные термины

Описание работы алгоритма

Структура Graph

Реализация PriorityQueue

Алгоритм Прима