Обход в глубину графа, представленного матрицей инцидентности
Граф представлен матрицей инцидентности размера nxm, где n – число вершин, m – число рёбер графа. Матрица инцидентности позволяет установить множество вершин, соседних с заданной, не прибегая к полному просмотру всей матрицы. Матрица представлена двумерным массивом. Столбцы матрицы - это вершины, строки матрицы - рёбра
Матрица инцидентности - это булева матрица, элемент которой равен единице, если вершина инцидентна ребру, и равен нулю, если вершина не инцидентна ребру.
Вообще, о графах как математических объектах и структурах данных, о моделировании жизненных ситуаций с помощью графов можно узнать многое в блоке "Теория графов".
В разобранном здесь примере совершается обход в глубину графа, представленного на рисунке ниже.

Его матрица инцидентности дана в коде ниже:
Код C++
Обход графа в глубину (Depth-first search, DFS) описывается следующим алгоритмом.
1) Выбрать из непройденных вершин вершину с наименьшим номером. Если непройденных вершин нет, закончить работу – конец алгоритма.
2) Пройти выбранную вершину и отметить её в массиве пометок как пройденную (реализуется циклом по столбцу).
3) Просмотреть список инцидентности только что пройденной вершины и к каждой непройденной вершине из списка применить рекурсивно пункты 2 и 3 данного алгоритма (реализуется циклом по строке, вложенным в первый цикл по столбцу, и ещё одним циклом по столбцу, вложенным в цикл по строке).
4) Перейти к пункту 1.
Ниже приведён код, в котором создаётся массив пройденных вершин и присваиваются значения переменным, являющимся параметрами циклов.
Код C++
И, наконец, полный листинг всей программы, в которой содержится уже приведённый массив, функция обхода графа в глубину и главная функция с вызовом этой функции. Чтобы на экран выводился весь маршрут обхода, начиная с первой вершины, следует ввести значение переменной from (стартовая точка), на единицу меньшее номера первой вершины (в данном примере это " - 1 ").
Код C++
В результате обхода графа, приведённого в этом примере, выводится следующая последовательность вершин: 0, 4, 1, 6, 11, 7, 3, 2, 5, 10, 9, 8.
Поделиться с друзьями