Форум программистов, компьютерный форум, киберфорум
PascalABC.NET
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 02.04.2016
Сообщений: 14
1

Алгоритм Прима: как вывести порядок выбранных ребер? И как быть с вершиной 2?

24.04.2016, 12:30. Просмотров 312. Ответов 0
Метки нет (Все метки)

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
66
67
68
69
70
71
72
73
74
75
76
77
const
  n = 6;
  inf = 100000;
 
type
  mas1 = array[1..n, 1..n] of integer;
  mas2 = array[1..n] of boolean;
  mas3 = array[1..n] of integer;
 
 
const
  GM: mas1 = //матрица смежности графа
  (
  (0, 9, 1, 4, 0, 0), //1
  
  (0, 0, 0, 0, 0, 0), //2
  
  (1, 0, 0, 3, 2, 4), //3
  
  (4, 0, 3, 0, 0, 1), //4
  
  (0, 0, 2, 0, 0, 2), //5
  
  (0, 0, 4, 1, 2, 0)  //6
  );
 
 
 
 
procedure Prim(s: integer);
var
  path: mas3;   //порядок выбранных вершин/ребер
  labels: set of integer;  //помеченные вершины
  str, sto, sum: integer;//вес дерева
begin
  path[1] := s;
  labels := [s] + labels;
  for var i := 2 to n do 
  begin
    foreach j: integer in labels do 
    begin
      var tmp := 0;
      for var k := 1 to n do //заменить
        if (not (k in labels)) and (GM[j, k] <> 0) then
          if tmp = 0 then 
            tmp := k
          else if GM[j, k] < GM[j, tmp] then //row=номер строки,в которой ищем min (j)
            tmp := k;
      if (tmp <> 0) and ((str = 0) or ((str <> 0) and (GM[str, sto] > GM[j, tmp]))) then begin
        str := j;
        sto := tmp;
      end;
    end;
    labels := [sto] + labels;
    path[i] := sto;
    sum := GM[str, sto] + sum; 
    str := 0;
    sto := 0;
  end;
  writeln('Вес минимального остовного дерева: ', sum);
  write('Порядок выбранных вершин: ');
  foreach i: integer in path do
    write(i, ' ');
  writeln();
end;
 
 
 
begin
  begin
        writeln();
        write('Начальная вершина: ');
        var s1: integer;
        readln(s1);
        prim(s1);
      end;
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.04.2016, 12:30
Ответы с готовыми решениями:

Алгоритм Дейкстры - Вывести не только вес ребер, но и сам путь
Необходимо вывести не только вес ребер, но и сам путь, например: 1-3-5. Помогите, пожалуйста. ...

Как вывести на экран список ребер, считанных из файла?
Используя ООП. Тема - графы. А в файле in.txt хранится матрица смежности. from dataclasses...

А как мне вывести количество выбранных пользователем дат, чтобы посчитать скидку при публикации в > 3 номерах ?
В форме публикации объявления в газете указываются даты публикации в текстовом виде...

Алгоритм Прима
Здравствуйте, у меня программа на С# в Windows Forms на тему &quot;Алгоритм Прима&quot;. Я все реализовала, и...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.04.2016, 12:30

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

Алгоритм Прима
Доброго времени суток. Имеется алгоритм Прима, собственно код elem(X, ).(X, ) :- elem(X,HS)....

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

Алгоритм Прима
Есть класс GraphEdge, отвечающий за ребро class GraphEdge { public int v1, v2; ...

Алгоритм Прима!
И снова здравствуйте! Ознакомился с алгоритмом прима, видел псевдокод, решал примеры, но вот...

Алгоритм Прима
Доброго времени суток. Мне нужно перевести программу написанную в Pascal, в Delphi. Вот...

Алгоритм прима
Всем привет! Помогите пожалуйста реализовать алгоритм Прима, для нахождения минимального остового...


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

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

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