ОБХОД ГРАФА ( в глубину ) - помогите, кто в курсе!

← →
Rradion (2003-12-26 14:53) [0]

Есть граф и его матрица инцидентности ( стринг грид - К примеру StringGrid1.Cells[1, 1] := "1"; ) ...

http://www.elena-antimonova.com/BRT/grafi.jpg

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

Нашел такой Алгоритм:

7.3. Алгоритмы работы с графами Обход графа — это некоторое систематическое перечисление его вершин или ребер. Алгоритмы прохождения графа напоминают алгоритмы прохождения дерева (см. п. 8.2) и отличаются от них мерами, препятствующими повторному посещению вершин. Для этого однажды пройденные вершины помечаются, а перед посещением вершины делается проверка отсутствия отметки. Для отметок отводится особый массив пометок, индексами которого служат номера вершин графа. Среди всех обходов наиболее известны способы прохождения графа в ширину и в глубину, которые лежат в основе многих конкретных алгоритмов на графах. В представленных ниже алгоритмах полагается, что граф представлен списком инцидентности; массив пометок обнулен, т. е. пройден вершин нет. АЛГОРИТМ 7.1. Прохождение графа в глубину. 1. Выбрать из непройденных вершину с наименьшим номером. Если непройденных вершин нет, закончить работу - конец алгоритма. 2. Пройти выбранную вершину и отметить ее в массиве пометок как пройденную. 3. Просмотреть список инцидентности только что пройденной вершины и к каждой непройденной вершине из списка применить рекурсивно пункты 2 и 3 данного алгоритма. 4. Перейти к пункту 1. Примечания. 1. Программируя алгоритм 7.1, пункты 2 и 3 целесообразно оформлять в виде рекурсивной процедуры. 2. Алгоритм 7.1 позволяет установить, имеется ли в графе цепь ребер между двумя заданными вершинами. Для этого достаточно применить его пункты 2 и 3 к одной из заданных вершин. Если другая вершина будет пройдена, цепь есть; в противном случае - цепи нет. 3. Если в качестве отметки о прохождении записывать номер предшествующей вершины, то можно проследить путь из одной вершины к другой.

А как его реализовать в код еще не совсем понял. У кого есть соображение, подскажите плиз.

Заранее Благодарю!

← →
Романов Р.В. © (2003-12-26 15:45) [1]

Начинаем из точки V1
1. Отмечаем точку V1 как пройденную
2. Определяем с кем связана точка V1 (цикл по строке)
2.1. Просматриваем строку V1 в матрице
2.2. Видим в столбце E1 единицу
3. Просматриваем столбец E1 (цикл по столбцу)
3.1. В строке V1 видим единицу
3.2. Проверяем пройденна ли точка V1
3.3. Она пройдена.
3.4. В строке V2 видим единицу
3.5. Проверяем пройденна ли точка V2
3.6. Она не пройдена
4. Вызываем рекурсивно пункт 1 для точки V2

5. Отмечаем точку V1 как пройденную
6. Определяем с кем связана точка V2 (цикл по строке)
6.1. Просматриваем строку V2 в матрице
6.2. Видим в столбце E1 единицу
7. Просматриваем столбец E1 (цикл по столбцу)
7.1. В строке V1 видим единицу
7.2. Проверяем пройденна ли точка V1
7.3. Она пройдена.
7.4. В строке V2 видим единицу
7.5. Проверяем пройденна ли точка V2
7.6. Она пройдена
и т.д.

> 5. Отмечаем точку V1 как пройденную

5. Отмечаем точку V2 как пройденную

ОБХОД ГРАФА ( в глубину ) - помогите, кто в курсе! Найти похожие ветки