Построить минимальное остовное дерево

17.12.2019, 19:42. Показов 8038. Ответов 0

Метки алгоритм крускала, графы, дерево, матрица, мод (Все метки)

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

Построить минимальное остовное дерево используя минимальный алгоритм Крускала

Wдерева = ∑ wy = 1+1+2+5 = 9
Реализовать – это все:
-Граф связный
-Числа от 1 до 10, Матрица 10×10, число вершин = 10
-Могут повторяться
Wy(Random) {█(i=1,n-1@j=2,n)┤
W*; = Wy – присваиваем.
Wi,i = 0 – заполняем 0

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from random import randint
import pprint
 
b = list()
m, n = 10, 10
A = [[0, 1, 1, 1, 0],
     [1, 0, 0, 0, 1],
     [1, 0, 0, 1, 1],
     [1, 0, 1, 0, 1],
     [0, 1, 1, 1, 0]]
pprint.pprint(A)
E = [[1, 0, 0, 0, 0],
     [0, 1, 0, 0, 0],
     [0, 0, 1, 0, 0],
     [0, 0, 0, 1, 0],
     [0, 0, 0, 0, 1]]
m = matrix_power(A, 2)
print('A^2\n', m,"\n")
k = matrix_power(A, 3)
print('A^3\n', k)
n = matrix_power(A, 4)
print('A^4\n', k)
M = A + m + k + E
print('M = \n', M)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vertices=5
spset=[True]*5
wt=[[1000,1,3,4,1000],[1,1000,5,1000,7],[3,5,1000,6,8],[4,1000,6,1000,2],[1000,7,8,2,1000]]
 
row=[0]
 
for i in xrange(vertices-1):
  row_num,col_num,min_no=-1,-1,1000
  for i in row:
    temp=min(wt[row[i]])
    if(min_no>temp):
      min_no=temp
      row_num=i
      col_num=wt[i].index(temp)
  print str(min_no)+"("+str(row_num)+","+str(col_num)+")"
  spset[col_num]=False
  wt[col_num][row_num]=1000
  for i in xrange(vertices):
    wt[i][col_num]=1000
  row.append(col_num)
 
d=raw_input()

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

17.12.2019, 19:42

Ответы с готовыми решениями:

Построить минимальное остовное дерево
Всем приветик. Помогите пожалуйста построить минимальное остоное дерево по условию:

Минимальное остовное дерево
может кто делал программу? Помогите, если сможете. Телефонная компания обслуживает семь удаленных друг от друга районов связанных...

Минимальное остовное дерево
Помогите пожалуйста !!!:cry: -----Граф задан списками смежности вершин . Построить минимальное остовное дерево------

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

17.12.2019, 19:42

Помогаю со студенческими работами здесь

Минимальное остовное дерево
Всем привет. Я нашел уже готовый алгоритм который уже находит минимальное остовное дерево (на этом сайте). Но есть две проблемы. В этом...

Найти минимальное остовное дерево
Дан полный взвешенный граф, кол-во вершин задается пользователем, вес ребер рандомный от 1 до 100. Найти минимальное остовное дерево при...

Минимальное остовное дерево PASCAL
Написал программу для нахождения минимального остовного дерева, но вместо вывода номеров тех городов, которые он посетил, выводит нули....

Минимальное остовное дерево по алгоритму Прима
Здравствуйте!!! Очень надо написать функцию, которая возвращает минимальное остовное дерево по алгоритму Прима, можете помочь? ...

Минимальное остовное дерево алгоритмом Краскала
Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер. Задача решена!

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

Наверх