В данной статье я бы хотел объяснить работу алгоритма Прима. Алгоритм используется для нахождения минимального остовного дерева. Сам алгоритм очень прост, в статье хотел бы поделиться своей реализации на языке Go.
Начальные термины
-
Граф — это структура данных в которой хранятся вершины и связи между ними. Удобнее всего представлять графы в виде матрицы смежности.
-
Матрица смежности — эта квадратная матрица, размер матрицы равен количеству вершин в графе. В ней хранится информация о соседях вершин графа.
-
Минимальное остовное деревоЧитать полностью »