Форум программистов, компьютерный форум, киберфорум
Наши страницы
Visual Basic
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
strain100
0 / 0 / 0
Регистрация: 03.07.2013
Сообщений: 4
1

Построение дерева по алгоритму

03.07.2013, 17:16. Просмотров 1063. Ответов 8
Метки нет (Все метки)

Задание следующее: нужно написать программу, которая строила бы дерево по такому алгоритму
1. Выбираем на графе произвольную вершину и к ней еще одну вершину, к которой у нее кратчайший путь
2. К этим двум вершинам выбираем третью, к которой кратчайший путь и т.д. до конца.

Я начал с того, что задал динамические массивы, вводятся длины путей и нач. точка (в массиве обозначается длиной -1) . Например R(1,1) нужно ввести -1 и будет это нач. точкой. Сгенерировался массив с 1 - связь есть, 0 - связи нет и 2 - нач. точка. Как теперь построить дерево - не пойму...Заранее благодарен за помощь новичку)

PureBasic
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
Private Sub Form_Load()
Dim n As Integer, R() As Integer, P() As Integer, i As Integer, j As Integer, z As String, s As String, 
 
n = InputBox("Размерность")
s = ""
ReDim P(n, n) 'zadat massiv s rasstoyaniyami
For i = 1 To n
For j = 1 To n
P(i, j) = InputBox("Введите A(" & i & "," & j & ")")
s = s & P(i, j) & " "
Next
Label1 = Label1 & s & vbCrLf 'vyvesti massiv s rasstoyaniyami
s = ""
Next
ReDim R(n, n) 'zadat rabochiy massiv s indexami
For i = 1 To n
For j = 1 To n
If P(i, j) > 0 Then R(i, j) = 1
If P(i, j) = -1 Then R(i, j) = 2
If P(i, j) = 0 Then R(i, j) = 0
z = z & R(i, j) & " "
Next
Label2 = Label2 & z & vbCrLf 'vyvesti rabochiy massiv s indexami
z = ""
Next
End Sub
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2013, 17:16
Ответы с готовыми решениями:

програма по алгоритму
из двойного масива (2*8 значений ) должны вводиться данные. типо (2,8),...

Операции над бинарными деревьями: построение дерева, обход дерева, вставка и удаление элемента дерева
Пожалуйста кто сможет, помогите составить программу: Организация по...

Построение дерева и процедура обхода дерева
написать программу использующую процедуру построения дерева и процедуру обхода...

Построение бинарного дерева. Обход дерева
Построить дерево поиска с элементами – числами. С использованием операций...

Построение списков по алгоритму
Помогите с заданием пожалуйста! Даны два непустых списка целых чисел L1 и L2....

8
strain100
0 / 0 / 0
Регистрация: 03.07.2013
Сообщений: 4
07.07.2013, 12:29  [ТС] 2
Нашел код на С, но я им не владею...кто-нибудь может помочь перевести? Или может у кого есть реалиованный алгоритм приама, коим и является решение этой задачи)
C#
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
// входные данные
int n;
vector < vector<int> > g;
const int INF = 1000000000; // значение "бесконечность"
 
// алгоритм
vector<bool> used (n);
vector<int> min_e (n, INF), sel_e (n, -1);
min_e[0] = 0;
for (int i=0; i<n; ++i) {
    int v = -1;
    for (int j=0; j<n; ++j)
        if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
            v = j;
    if (min_e[v] == INF) {
        cout << "No MST!";
        exit(0);
    }
 
    used[v] = true;
    if (sel_e[v] != -1)
        cout << v << " " << sel_e[v] << endl;
 
    for (int to=0; to<n; ++to)
        if (g[v][to] < min_e[to]) {
            min_e[to] = g[v][to];
            sel_e[to] = v;
        }
}
Добавлено через 10 часов 34 минуты
Люди добрые, подскажите, что не так в коде...Виснет и все тут.
Visual Basic
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
Private Sub Form_Load()
Dim n As Integer, P() As Integer, min() As Integer, _
i As Integer, j As Integer, a() As Integer, perFlag As Integer, _
z As String, s As String, flag() As Boolean  'îáúÿâëÿåì ïåðåìåГ*Г*ûå
End Sub
Private Sub Command1_Click()
n = 25 'Г°Г*çìåðГ*îñòü
ReDim P(n, n)
For i = 1 To n
For j = 1 To n
P(i, j) = 0
P(1, 22) = 118
P(1, 4) = 127
P(1, 23) = 341
P(1, 8) = 310
P(1, 12) = 428
P(1, 13) = 424
P(2, 12) = 319
P(2, 8) = 243
P(2, 23) = 289
P(2, 7) = 449
P(2, 24) = 558
P(2, 14) = 181
P(2, 20) = 226
P(2, 3) = 245
P(2, 5) = 79
P(2, 21) = 325
P(3, 14) = 395
P(3, 16) = 560
P(3, 20) = 301
P(3, 9) = 151
P(3, 5) = 229
P(4, 15) = 192
P(4, 22) = 183
P(4, 7) = 131
P(5, 16) = 388
P(5, 21) = 282
P(5, 8) = 301
P(6, 19) = 273
P(6, 11) = 141
P(6, 18) = 150
P(6, 25) = 139
P(7, 13) = 492
P(7, 8) = 302
P(7, 23) = 186
P(7, 14) = 344
P(7, 17) = 337
P(7, 24) = 143
P(8, 23) = 137
P(8, 14) = 245
P(8, 12) = 181
P(9, 20) = 341
P(10, 11) = 151
P(10, 18) = 166
P(10, 15) = 70
P(11, 15) = 210
P(11, 18) = 133
P(11, 19) = 248
P(12, 13) = 137
P(12, 21) = 63
P(14, 24) = 405
P(14, 17) = 170
P(14, 20) = 149
P(15, 18) = 156
P(15, 22) = 194
P(16, 21) = 268
P(17, 24) = 335
P(17, 23) = 361
P(17, 20) = 187
P(18, 22) = 107
P(18, 25) = 172
P(18, 19) = 337
P(22, 25) = 184
P(23, 24) = 297
Next
Next
For i = 1 To n
For j = 1 To n
If P(i, j) <> 0 Then P(j, i) = P(i, j) 'ñèììåòðè÷Г*îñòü
d = d & P(i, j) & " "
Next
Label1 = Label1 & vbCrLf & d & vbCrLf
d = ""
Next
ReDim flag(n)
For i = 1 To n
flag(i) = False
flag(1) = True 'îáîçГ*Г*Г·Г*ГҐГ¬ ïåðâóþ ñòðîêó ГЄГ*ГЄ Г*Г*Г·. òî÷êó, îñòГ*ëüГ*ûå - ïðîñìГ*òðèâГ*åìûå
Next
ReDim a(n)
For i = 1 To n
a(i) = 1000 'îãðГ*Г*è÷èòåëü
Next
Do Until flag(2) = False Or flag(3) = False Or flag(4) = False Or flag(5) = False Or flag(6) = False Or flag(7) = False Or flag(8) = False Or flag(9) = False Or flag(10) = False Or flag(11) = False Or flag(12) = False Or flag(13) = False Or flag(14) = False Or flag(15) = False Or flag(16) = False Or flag(17) = False Or flag(18) = False Or flag(19) = False Or flag(20) = False Or flag(21) = False Or flag(22) = False Or flag(23) = False Or flag(24) = False Or flag(25) = False
For i = 1 To n
For j = i To 25
If P(i, j) <> 0 And P(i, j) < a(i) And flag(i) = True And flag(j) = False Then a(i) = P(i, j) And flag(j) = True
Next j
Label2 = Label2 & vbCrLf & a(i) & vbCrLf
Next i
Loop
End Sub
0
gaw
6633 / 1500 / 169
Регистрация: 09.01.2010
Сообщений: 4,273
07.07.2013, 15:35 3
К этим двум вершинам выбираем третью, к которой кратчайший путь
вот тут не совсем понятно
0
strain100
0 / 0 / 0
Регистрация: 03.07.2013
Сообщений: 4
07.07.2013, 16:10  [ТС] 4
http://e-maxx.ru/algo/mst_prim
Имеется ввиду, что выбрана вершина 1. От нее кратчайший путь (самое дешевое ребро) к вершине 2. Потом выбираем самое дешевое ребро от вершин 1 и 2 к третьей вершине. Так пока не будут соединены все вершины
0
gaw
6633 / 1500 / 169
Регистрация: 09.01.2010
Сообщений: 4,273
07.07.2013, 16:43 5
не уверен , что правильно понял
на форме Picture1, List1, Combo1
Visual Basic
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
78
79
80
81
82
83
Private Type k
  X As Single
  Y As Single
End Type
Dim a() As k, b() As k
Dim s() As Boolean
Dim r As Single
Dim n%
Const w = 100, h = 100
 
Sub d1(ind%, c%)
Dim L As Single, Lt As Single, ind1%, ind2%
 
If c = n Then Exit Sub
 
s(1, ind) = True
b(ind) = a(ind)
s(2, ind) = True
L = 10 ^ 6
For j = 1 To n
 If s(2, j) = True Then
     For i = 1 To n
       If s(1, i) = False Then
          Lt = Sqr((a(i).X - b(j).X) ^ 2 + (a(i).Y - b(j).Y) ^ 2)
            If L > Lt Then
               L = Lt: ind1 = j: ind2 = i
            End If
       End If
    Next i
  End If
Next j
List1.AddItem c & "  :  " & ind1 & " ---> " & ind2
Picture1.Line (a(ind2).X, a(ind2).Y)-(b(ind1).X, b(ind1).Y)
Call d1(ind2, c + 1)
 
End Sub
 
Private Sub Combo1_Click()
n = Val(Combo1.Text)
Call p
End Sub
 
 
Private Sub Form_Load()
Dim i%
r = 0.02 * w
Picture1.AutoRedraw = True
Picture1.Scale (-0.1 * w, 1.1 * h)-(1.1 * w, -0.1 * h)
Picture1.FontName = "MS Serif"
Picture1.FontSize = 7
For i = 3 To 100
  Combo1.AddItem i
Next i
Combo1.ListIndex = 31
End Sub
Sub p()
ReDim a(n), b(n), s(2, n)
For i = 1 To n
  a(i).X = Int(Rnd * (w + 1))
  a(i).Y = Int(Rnd * (h + 1))
Next i
Call g
End Sub
Sub g()
Picture1.Cls
For k = 1 To n
    s(1, k) = False: s(2, k) = False
    Picture1.Circle (a(k).X, a(k).Y), r
    Picture1.Print k
Next k
End Sub
 
Private Sub Picture1_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)
Dim i%
For i = 1 To n
  If ((X - a(i).X) ^ 2 + (Y - a(i).Y) ^ 2) <= r ^ 2 Then
    List1.Clear
    Call g
    Call d1(i, 1)
    Exit Sub
  End If
Next i
End Sub
0
strain100
0 / 0 / 0
Регистрация: 03.07.2013
Сообщений: 4
07.07.2013, 20:15  [ТС] 6
Благодарю за помощь, но уже сам разобрался чуть более простым методом
0
Laa911
0 / 0 / 0
Регистрация: 02.02.2014
Сообщений: 5
02.02.2014, 03:24 7
сори а нет ли готового инструмента что бы
1. по заданным параметрам строил само дерево (например задаем 7 уровней)
2. указываем минимальный средний и максимальное кол-во подуровней на кажом уровне
3. указываем некую сумму на каждый уровень

И программа
1. сама рисует дерево в виде кружочков например
2. каждый кружочек имеет маштам равный его сумме ( что то типа пузырьковая диаграммама)

Может быть есть что то готовое уже в природе?

что то такое (нашел только квадратики :-))



Добавлено через 44 минуты
Или что то подобное
http://www.weblancer.net/download/327918.png
0
The trick
Модератор
7365 / 2583 / 755
Регистрация: 22.02.2013
Сообщений: 3,799
Записей в блоге: 76
02.02.2014, 10:56 8
Написать процедуру, которая складывает максимальный и минимальный элементы непустого дерева
0
Laa911
0 / 0 / 0
Регистрация: 02.02.2014
Сообщений: 5
02.02.2014, 15:48 9
Эх еще бы где найти в мозге гуманитария программерские скилы :-(((
Если кто подмогнет буду очень рад ;-)))
0
02.02.2014, 15:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2014, 15:48

Построение графика sin из линий по алгоритму Брезенхэма
Прошу помочь с этой непростой задачей! Гуглил весь день, ничего не нашел. Есть...

Построение В*-дерева
Задание: Построение B* дерева, добавление вершин и балансировка в случае...

построение дерева
Здравствуйте! Начала разбираться с алгоритмом Хаффмана для сжатия сообщения...


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

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

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