Вопрос 21. Графы. Алгоритм поиска достижимых вершин графа.

Графы-способ формализовать всевозможные схемы.

Математики считают, что граф состоит из двух связанных между собой множеств. Первое-множество вершин (чаще всего изображается в виде кружочков с цифрами). Вершина: технологическая установка города на атласе автомобильных дорог, станция метрополитена и т.д.

Второе-множество дуг (чаще всего изображается в виде стрелочек).

Дуга: трубы, дороги, туннели.

Графы бывают направленные и ненаправленные. Если граф направленный, дуги обозначаются стрелочками (транспортная схема с односторонним движением).

Один из способов представления графа в памяти компьютера называется матрицей смежности.

Задача: граф задан матрицей смежности; необходимо назвать все вершины графа, в которые можно попасть по стрелочкам (дугам) из заданной вершины.

Схематичное описание алгоритма поиска достижимых вершин.

Алгоритм поиска достижимых вершин графа является рекурсивным. Схематично его можно описать как:

Шаг 1: найти все вершины непосредственно связанные со стартовой вершиной (идём по стрелочкам);

Шаг 2(рекурсивный): для каждой найденной вершины рекурсивно выполнить алгоритм поиска достижимых вершин, рассматривая уже найденную вершину как стартовую.

В процессе работы все найденные вершины нужно объединять вместе.

Примитивный алгоритм должен быть снабжён проверками, предотвращающий бесконечную рекурсию.

←Бесконечная рекурсия.

Sub click()

Dim n As Integer, i As Integer, j As Integer, count As Integer

n=cells(2,1) ‘ n – это количество вершин (ячеек)

ReDim A(n,h) As Integer ‘ двумерный массив А

For i=1 To n:for j=1 To n двойной цикл перебираются строки, столбцы, ячейки

A(i,j)=cells(1+i,2+j)

Next j,i

i=cells(2,2):count=0 ‘ счётчик считает найденные вершины начиная с 0

call spisok(n,i,count,A()) ‘ i – стартовая величина, Call – вызов подпрограммы, А() –матрица смежности.

End Sub

Подпрограмма (процедура), вызывает сама себя, (рекурсивная):

Sub spisok (n As Integer, i_start As Integer, count As Integer, A() As Integer)

Dim i As Integer, j As Integer, k As Integer ‘ дополнительные переменные

For j=1 to n

If A(i_start,j)=1 then

count=count+1’увеличивает счётчик на единицу

cells(3+count,2)=j ‘ записывает в свободную ячейку

For k=1 To n:A(k,j)=-Abs(A(k,j)):Next k ‘Отвечает за то, чтобы мы не могли попасть в найденную вершину из другой вершины

call spisok (n,j,count,A()) ‘ программа вызывает сама себя, i- стартовая величина,не исходная,а которую мы нашли

End If

Next j

End Sub

for k=1 To n:A(k,j)=-Abs(A(k,j)):Next k

1 соответствует разорванной стрелке => больше в найденную вершину не попадём.

Дата добавления: 2015-11-13