Построение дерева по алгоритму - VB
Формулировка задачи:
Задание следующее: нужно написать программу, которая строила бы дерево по такому алгоритму
1. Выбираем на графе произвольную вершину и к ней еще одну вершину, к которой у нее кратчайший путь
2. К этим двум вершинам выбираем третью, к которой кратчайший путь и т.д. до конца.
Я начал с того, что задал динамические массивы, вводятся длины путей и нач. точка (в массиве обозначается длиной -1) . Например R(1,1) нужно ввести -1 и будет это нач. точкой. Сгенерировался массив с 1 - связь есть, 0 - связи нет и 2 - нач. точка. Как теперь построить дерево - не пойму...Заранее благодарен за помощь новичку)
Решение задачи: «Построение дерева по алгоритму»
textual
Листинг программы
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
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д