Главная

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

2024-10-03 в 7:16, admin, рубрики: алгоритм Прима, Алгоритмы, графы, матрица смежности, минимальное остовное дерево

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

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

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

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

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

Структура Graph

// 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().

Реализация PriorityQueue

// 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, вес: %dn", 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.

Автор: alivewel

Источник