Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
18 / 17 / 4
Регистрация: 22.03.2018
Сообщений: 701
1

Построить минимальное дерево-остов графа пошагово аналитически и реализовать данный алгоритм

10.06.2018, 00:33. Просмотров 1227. Ответов 1
Метки нет (Все метки)

Построить минимальное дерево-остов графа пошагово аналитически и реализовать данный алгоритм на Pascal.
Построить минимальное дерево-остов графа пошагово аналитически и реализовать данный алгоритм
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.06.2018, 00:33
Ответы с готовыми решениями:

Построить для заданного графа минимальное основное дерево
Построить для заданного графа минимальное основное дерево. Помогите на С++ написать задачку)...

Найти минимальное дерево-остов
Неориентированный граф G содержит 10 вершин. Расстояния между вершинами заданы таблицей 4. Найти...

Для заданного графа найдите минимальный остов (алгоритм Краскала)
Для заданного графа найдите минимальный остов с помощью алгоритма Краскала.

Найти двумя методами (Краскала и Прима) минимальное остовное дерево графа
Найти двумя методами (Краскала и Прима) минимальное остовное дерево графа.

1
18 / 17 / 4
Регистрация: 22.03.2018
Сообщений: 701
10.06.2018, 11:44  [ТС] 2
Лучший ответ Сообщение было отмечено Nikita110001 как решение

Решение

Построить минимальное дерево-остов графа пошагово аналитически и реализовать данный алгоритм на Pascal.
Вложение 945460
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const
  maxn = 10;
  maxm = 50;
type
  TEdge = record          //структура, необходимая для хранения
    u,v,w:longint;        // информации о ребре - соединяемые вершины, вес
 
  end;
var
  n,m,i,mid:longint;
  p,rank:array[1..maxn]of longint;  //структуры, необходимые для реализации системы
                                    // непересекающихся множеств
                                    //p[i] - номер вершины-родителя множества,
                                    // в которое входит i-ая вершина
                                    // rank[i] - оценка сверху глубины поддерева
                                    // с корнем в i-ой вершине
  e:array[1..maxm]of TEdge;
  buf:TEdge;
 
procedure qsort(l,r:Longint); //быстрая сортировка
var
  j:longint;
begin
  i:=l; j:=r; mid:=e[(i+j)div 2].w;
  repeat
    while e[i].w<mid do inc(i);
    while e[j].w>mid do dec(j);
    if i<=j then begin
      buf:=e[i]; e[i]:=e[j]; e[j]:=buf;
      inc(i); dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;
 
//две процедуры для работы с системой непересекающихся множеств
function findset(x:longint):longint;
begin
  if x<>p[x] then p[x]:=findset(p[x]);
  findset:=p[x];
end;
 
procedure union(x,y:longint);
begin
  x:=findset(x); y:=findset(y);
  if rank[x]>rank[y] then p[y]:=x else p[x]:=y;
  if rank[x]=rank[y] then inc(rank[y]);
end;
 
begin
  read(n,m);
  for i:=1 to m do read(e[i].u,e[i].v,e[i].w);
  qsort(1,m);
  for i:=1 to n do
  begin 
    p[i]:=i; rank[i]:=0;
  end;
  for i:=1 to m do
       if findset(e[i].u)<>findset(e[i].v) then
       begin
           union(e[i].u,e[i].v);
           writeln(e[i].u,' ',e[i].v);
       end;
end.
Добавлено через 11 часов 9 минут
Помогите пожалуйста мне ?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.06.2018, 11:44

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Остов графа
Ребят, кто-нибудь объясните пожалуйста как прога работает. И возможно ли её реализовать без...

Остов не ориентированного графа
Здравствуйте, подскажите, пожалуйста. Дан неориентированный взвешенный граф, нужно построить остов....

Выделить остов графа
Граф Выделяю остов: 1. Удаляю по ребру из каждого цикла, состоящего из трёх вершин. 2. После у...

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


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.