Рубрика «минимальное остовное дерево»

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

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

  • Граф — это структура данных в которой хранятся вершины и связи между ними. Удобнее всего представлять графы в виде матрицы смежности.

  • Матрица смежности — эта квадратная матрица, размер матрицы равен количеству вершин в графе. В ней хранится информация о соседях вершин графа.

  • Минимальное остовное деревоЧитать полностью »

В данной статье для реализации алгоритма будут рассмотрены:

  1. Система хранения графа на основе List<>

  2. Сортировка рёбер графа по весу

  3. Система непересекающихся множеств


Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.

О чём речь?

Если прочитав предложение выше вы невольно задались этим вопросом, то вам следует изучить пару книг по теории графов информацию, представленную в этом блоке.

Читать полностью »

https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js