YURIY KOZLOV, я собираюсь реализовать алгоритм Краскала. Первым делом надо отсортировать список ребер. Но я хочу перед этим просто вывести на экран не сортированный список ребер. Изучаю алгоритмы и питон. Вот и пытаюсь понять как он функционирует. Изучить синтаксис. Практиковаться. Надо ведь с чего-то начинать новичку.
Если отдельно взятый элемент матрицы смежности не является вершиной, то чем он является?
Алгоритм Краскала:
1. Сначала упорядочиваем все ребра по возрастанию весов.
2. Заводим таблицу: в левой колонке список ребер, в правой компоненты связности.
3. В первой строчке список ребер пустой и все компоненты связности одновершинные. Берем минимальное по стоимости (по весу) ребро и включаем его в список ребер. Соответствующие две вершины объединяем в одну компоненту связности.
4. Берем следующее по стоимости ( весу) ребро, добавляем к содержимому предыдущей строчки левого столбца; объединяем компоненты связности. Если концы ребра уже принадлежат одной и той же компоненте связности, то данное ребро в состав минимального остова не включается.
5. Повторяем эти операции до тех пор, пока все вершины не окажутся в одной единственной компоненте связности (для этого потребуется включить в состав остова ровно n–1 ребро).
---------
пытаюсь выполнить пункт 1. но чтоб ребра отсортировать, нужно сначала вывести на экран список ребер и посмотреть что там
Любой один отдельный элемент матрицы - это вершина.
Ребро соединяет начальную вершину u и конечную вершину v.
индексы этого элемента - узлы связанные данным ребром
- не понятная мне фраза
Значение (не нулевое) - это вес ребра.
Меня интересует - как вывести список ребер. В прямом смысле слова.
Так как сначала их нужно вывести, а потом отсортировать.
Как сортировать знаю, функцией sort.
Но в конечном счете пытаюсь реализовать алгоритм Краскала, то есть найти минимальный остов. Но в рамках этого кода не буду об этом спрашивать. Для начала нужно вывести список ребер матрицы.
