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

@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):

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

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

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

	Реализация алгоритма Краскала для графа, который задается матрицей смежности 15.09.2018, 00:38. Показов 14229. Ответов 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