Планирование уроков на учебный год (по учебнику Н.Д. Угриновича, профильный уровень)



Уроки 31 - 34
§1.10. Графы и их исследование с использованием языков объектно-ориентированного программирования Visual Basic и Turbo Delphi




Содержание урока

1.10.1. Введение в теорию графов
1.10.2. Изучение графов на языке Visual Basic

Проект «Построение основного связного дерева графа» на языке Visual Basic

Обработчик события вывода в графическое поле вершин графа

Обработчик события вывода элементов матрицы смежности взвешенного ориентированного графа

Обработчик события вывода элементов матрицы смежности взвешенного неориентированного графа

Обработчик события построения остовного связного дерева минимального веса

Контрольные вопросы

1.10.3. Изучение графов на языке Turbo Delphi

1.10.2. Изучение графов на языке Visual Basic


Обработчик события построения остовного связного дерева минимального веса


В этой процедуре пользователь строит остовное связное дерево минимального веса. Ребро минимального веса выбирается с использованием матрицы смежности неориентированного графа. Ввод номеров вершин ребра минимального веса осуществляется с помощью функции ввода данных InputBox(). Включение или невключение выбранного ребра в остовное дерево производится на основании пункта 3 алгоритма Крускала, который реализуется с использованием функции вывода сообщений MsgBox () и оператора условного перехода в сокращенной форме.

В результате остовное связное дерево минимального веса будет нарисовано в графическом поле, номера его вершин и веса ребер будут выведены в поля списков, суммарный вес ребер будет выведен на надпись.

10. Щелкнуть по кнопке Button4 и в заготовку обработчика события ввести программный код:


Private Sub Button4_Click (...)
'Ввод номера первой вершины и ее рисование
'в графическом поле
N=InputBox("Введите номер первой вершины:" "Выбор ребра минимального веса")
Graph2.DrawEllipse(Pen2, P(N).X, P(N).Y, 2, 2)
Graph2.DrawString(N, drawFont, drawBrush, P (N) .X, P (N) .Y)
'Ввод номера второй вершины и ее рисование
'в графическом поле
K=InputBox ("Введите номер второй вершины: "Выбор ребра минимального веса")
Graph2.DrawEllipse(Pen2, Р(К).X, Р(К).У, 2, 2)
Graph2.DrawString(К, drawFont, drawBrush, Р (К) .X, Р(К) . Y)
'Реализация пункта 3 алгоритма Крускала
A=MsgBox("Ребро с вершинами " + Str(N) +
" и " + Str (К) + " включить в состав
остовного дерева, если выполняется хотя
бы одно из условий: (Обе вершины не
входят в остовное дерево) или (Одна из
вершин не входит в остовное дерево) или
(Вершины входят в различные подмножества
остовного дерева).", 32 +4, "Включить
ребро в остовное дерево?")
If А=6 Then
Graph2.DrawLine(Pen1, P(N).X, P(N).Y, P(K).X, P(K).Y)
R2 (N,K)=Math.Sqrt((P(N).X-P(K).X)ˆ2 + (P(N).Y-P(K).Y)ˆ2)
ListBox11.Items.Add(N)
ListBox12.Items.Add(K)
ListBox13.Items.Add(R2(N, K) )
Label1.Text=R2(N,K)+Val(Label1.Text)
End If
End Sub

На основе анализа матрицы смежности неориентированного графа выберем ребро минимального веса.

11. Осуществить щелчок по кнопке Построение остовного связного дерева минимального веса.

В появившемся диалоговом окне Выбор ребра минимального веса ввести номер первой точки и щелкнуть по кнопке ОK (рис. 1.67).

Рис. 1.67. Ввод первой вершины

12. В появившемся диалоговом окне Выбор ребра минимального веса ввести номер второй точки и щелкнуть по кнопке ОK (рис. 1.68).

Рис. 1.68. Ввод второй вершины

На основе анализа остовного связного дерева в графическом поле выполним пункт 3 алгоритма Крускала и решим вопрос о включении или невключении выбранного ребра в остовное дерево.

13. В появившемся диалоговом окне Включить ребро в остовное дерево? подтвердить или опровергнуть истинность условий щелчком по кнопке Да или по кнопке Нет (рис. 1.69).

Рис.1.69. Включение ребра в остовное дерево

14. Выполнять пункты 11-13 до тех пор, пока остовное связное дерево с минимальным весом не будет построено, т. е. пока все вершины не войдут в связное множество.

В результате (рис. 1.70):

• в графическом поле будет построено остовное связное дерево;
• в полях списка появятся номера вершин и веса соответствующих ребер остовного дерева;
• на надпись будет выведена сумма весов ребер остовного связного дерева минимального веса.

Рис. 1.70. Минимальный вес остовного дерева



Следующая страница Контрольные вопросы



Cкачать материалы урока





Наверх