Реализация алгоритма Краскала для графа, который задается матрицей смежности

@EchoesArina · Регистрация: 27.10.2017

Студворк — интернет-сервис помощи студентам

Доброго времени! Начала изучать Python и очень срочно необходимо реализовать алгоритм Краскала для графа, который задается матрицей смежности. Кто может помочь? Или хотя бы по пунктам объяснить, как написать этот код

Спасибо за помощь!

@ТабуретY · 15.09.2018, 02:54

Вот например https://github.com/israelst/Al... kruskal.py

@EchoesArina · 15.09.2018, 22:20 **[ТС]**

ТабуретY, а как понять, что там происходит ?

@IRIP · 15.09.2018, 23:38

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

Алгоритм Крускала (или алгоритм Краскала) — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, m = map(int, input('Введите два числа (через пробел): \n').split())
edges = []
for i in range(m):
    start, end, weight = map(int, input('Введите три числа (через пробел): '
                                        '\n').split())
    edges.append([weight, start, end])
edges.sort()
comp = [i for i in range(n)]
ans = 0
for weight, start, end in edges:
    if comp[start] != comp[end]:
        ans += weight
        a = comp[start]
        b = comp[end]
        for i in range(n):
            if comp[i] == b:
                comp[i] = a

в сети пишут, вот это работает

@EchoesArina · 16.09.2018, 00:02 **[ТС]**

IRIP, я вставила этот код в программу, а он выдал ошибку

@IRIP · 16.09.2018, 00:24

EchoesArina, там нужно играть с числами

в первом ряду, нужно вводить, например

1 2 (через пробел)

во-втором ряду:

100 200 300

но цифры могут быть другие, я не знаю какие

Добавлено через 1 минуту
у меня, например, выдало такую ошибку:

Python
1
2
3
4
5
6
7
8
9
10
Введите два числа (через пробел): 
1 2
Введите три числа (через пробел): 
100 200 300
Введите три числа (через пробел): 
10 20 30 
Traceback (most recent call last):
  File "/home/irip/pycharm/pyget/test.py", line 11, in <module>
    if comp[start] != comp[end]:
IndexError: list index out of range

Добавлено через 9 минут
EchoesArina, нужны ВХОДНЫЕ данные для тестов.

@EchoesArina · 16.09.2018, 01:06 **[ТС]**

IRIP, у меня есть граф и матрицы для него

@IRIP · 16.09.2018, 08:08

EchoesArina, данные есть, для ввода? Можете выложить входные данные?

@Бард · 16.09.2018, 09:39

Сообщение от IRIP

но цифры могут быть другие, я не знаю какие

В первой строке надо указать число вершин и число дуг.
Во второй и далее указываются дуги в формате:
вес дуги номер начальной вершины номер конечной вершины

@EchoesArina · 16.09.2018, 14:36 **[ТС]**

IRIP, Матрица весов графа. Всего там 11 вершин и 18 дуг
[[0,7,0,0,0,0,0,5,3,0,0]
[7,0,5,0,0,0,0,0,0,3,0]
[0,5,0,3,0,0,0,0,0,0,0]
[0,0,3,0,5,0,0,0,0,1,0]
[0,0,0,5,0,4,0,0,0,0,8]
[0,0,0,0,4,0,1,0,0,3,0]
[0,0,0,0,0,1,0,6,2,0,4]
[5,0,0,0,0,0,6,0,0,2,0]
[3,0,0,0,0,0,2,0,0,5,0]
[0,3,0,1,0,3,0,2,5,0,4]
[0,0,0,0,8,0,4,0,0,4,0]]

@IRIP · 16.09.2018, 16:33

Сообщение от Бард

В первой строке надо указать число вершин и число дуг.
Во второй и далее указываются дуги в формате:
вес дуги номер начальной вершины номер конечной вершины

а как же тогда?

start, end, weight = начало, конец, вес

...

EchoesArina,

это выходные данные
а входные?

@Бард · 16.09.2018, 16:47

Сообщение от IRIP

а как же тогда?
start, end, weight = начало, конец, вес

, извиняюсь, перепутал, посмотрел в следующую строчку.

@EchoesArina · 16.09.2018, 16:48 **[ТС]**

IRIP, принимаем как неориентированный граф. Начальную точку можно выбрать произвольно, главное чтобы он по всем вершинам прошелся и миним. вес был

@IRIP · 16.09.2018, 17:32

EchoesArina, в целом, представленный выше код, рабочий

Вот так, будет, с расшифровкой:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n, m = map(int, input('Введите кол-во вершин и дуг (через пробел): \n').split())
edges = []
for i in range(m):
    start, end, weight = map(int, input('Введите start/end/weight (через пробел): '
                                        '\n').split())
    edges.append([weight, start, end])
edges.sort()
comp = [i for i in range(n)]
ans = 0
for weight, start, end in edges:
    if comp[start] != comp[end]:
        ans += weight
        a = comp[start]
        b = comp[end]
        for i in range(n):
            if comp[i] == b:
                comp[i] = a
 
print(ans, comp, edges)

только почему-то возникает ошибка

File "/home/irip/pycharm/pyget/test.py", line 11, in <module>
if comp[start] != comp[end]:
IndexError: list index out of range

видимо, я входные данные неправильно ввожу

@EchoesArina · 16.09.2018, 17:41 **[ТС]**

IRIP, как правильно вообще ввести данные ? Я вот так делала и он все равно не хочет работать

@Бард · 16.09.2018, 17:46

Сообщение от IRIP

видимо, я входные данные неправильно ввожу

Забил в программу тестовый граф в виде треугольника

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = 3
edges = []
edges.append([10, 0, 1])
edges.append([10, 1, 2])
edges.append([10, 2, 0])
 
edges.sort()
comp = [i for i in range(n)]
ans = 0
for weight, start, end in edges:
    if comp[start] != comp[end]:
        ans += weight
        a = comp[start]
        b = comp[end]
        for i in range(n):
            if comp[i] == b:
                comp[i] = a
 
print(ans, comp, edges)

На выходе что-то странное: 20 [0, 0, 0]

@IRIP · 16.09.2018, 19:06

Бард, потому что, в первой строчке вводится только

n, m
а дальше, программа спрашивает строчки, в зависимости от количества (m)

и в них, нужно вводить

10 0 1
10 1 2
10 2 0

Добавлено через 25 секунд
m == 3 должно быть

@Бард · 16.09.2018, 19:54

Сообщение от IRIP

m == 3 должно быть

Если данные находятся в программе, а не вводятся, то m вообще не нужeн, т.к. цикл алгоритма идёт по всем рёбрам

Python
1
for weight, start, end in edges:

а рёбер именно столько, сколько было бы введено в цикле по m

Python
1
for i in range(m):

Похоже, что код неправильный, т.к. в нём вообще нет формирования списка рёбер остовного дерева.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123

	Реализация алгоритма Краскала для графа, который задается матрицей смежности 15.09.2018, 00:38. Показов 13843. Ответов 17 Метки алгоритм, графы, матрица смежности (Все метки) Доброго времени! Начала изучать Python и очень срочно необходимо реализовать алгоритм Краскала для графа, который задается матрицей смежности. Кто может помочь? Или хотя бы по пунктам объяснить, как написать этот код Спасибо за помощь! 0

@ТабуретY 1741 / 913 / 480 Регистрация: 05.12.2013 Сообщений: 3,074
	15.09.2018, 02:54
	Вот например https://github.com/israelst/Al... kruskal.py 0

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	15.09.2018, 22:20 [ТС]
	ТабуретY, а как понять, что там происходит ? 0

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	16.09.2018, 00:02 [ТС]
	IRIP, я вставила этот код в программу, а он выдал ошибку 0

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	16.09.2018, 01:06 [ТС]
	IRIP, у меня есть граф и матрицы для него 0

@IRIP 514 / 146 / 28 Регистрация: 18.04.2015 Сообщений: 1,904 Записей в блоге: 16
	16.09.2018, 08:08
	EchoesArina, данные есть, для ввода? Можете выложить входные данные? 0

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	16.09.2018, 14:36 [ТС]
	IRIP, Матрица весов графа. Всего там 11 вершин и 18 дуг [[0,7,0,0,0,0,0,5,3,0,0] [7,0,5,0,0,0,0,0,0,3,0] [0,5,0,3,0,0,0,0,0,0,0] [0,0,3,0,5,0,0,0,0,1,0] [0,0,0,5,0,4,0,0,0,0,8] [0,0,0,0,4,0,1,0,0,3,0] [0,0,0,0,0,1,0,6,2,0,4] [5,0,0,0,0,0,6,0,0,2,0] [3,0,0,0,0,0,2,0,0,5,0] [0,3,0,1,0,3,0,2,5,0,4] [0,0,0,0,8,0,4,0,0,4,0]] 0

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	16.09.2018, 16:48 [ТС]
	IRIP, принимаем как неориентированный граф. Начальную точку можно выбрать произвольно, главное чтобы он по всем вершинам прошелся и миним. вес был Миниатюры 0

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	16.09.2018, 17:41 [ТС]
	IRIP, как правильно вообще ввести данные ? Я вот так делала и он все равно не хочет работать Миниатюры 0

@IRIP 514 / 146 / 28 Регистрация: 18.04.2015 Сообщений: 1,904 Записей в блоге: 16
	16.09.2018, 19:06
	Бард, потому что, в первой строчке вводится только n, m а дальше, программа спрашивает строчки, в зависимости от количества (m) и в них, нужно вводить 10 0 1 10 1 2 10 2 0 Добавлено через 25 секунд m == 3 должно быть 0