Обход в глубину графа, представленного матрицей инцидентности

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

Матрица инцидентности - это булева матрица, элемент которой равен единице, если вершина инцидентна ребру, и равен нулю, если вершина не инцидентна ребру.

Вообще, о графах как математических объектах и структурах данных, о моделировании жизненных ситуаций с помощью графов можно узнать многое в блоке "Теория графов".

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

Его матрица инцидентности дана в коде ниже:

Код C++

const int n = 12; const int m = 14; int iArr[n][m] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1 };

Обход графа в глубину (Depth-first search, DFS) описывается следующим алгоритмом.

1) Выбрать из непройденных вершин вершину с наименьшим номером. Если непройденных вершин нет, закончить работу – конец алгоритма.

2) Пройти выбранную вершину и отметить её в массиве пометок как пройденную (реализуется циклом по столбцу).

3) Просмотреть список инцидентности только что пройденной вершины и к каждой непройденной вершине из списка применить рекурсивно пункты 2 и 3 данного алгоритма (реализуется циклом по строке, вложенным в первый цикл по столбцу, и ещё одним циклом по столбцу, вложенным в цикл по строке).

4) Перейти к пункту 1.

Ниже приведён код, в котором создаётся массив пройденных вершин и присваиваются значения переменным, являющимся параметрами циклов.

Код C++

bool used[n]; int j = 0; int r = 0; int i = 0; int k = 0; void dfs(int t) { used[t] = true; int p; for (i = k; i < n; i++) { j = r; if ((iArr[i][j] != 0) && (!used[i])) { used[i] = true; p = i; cout << i << " "; for (j = 0; j < m; j++) { i == p; if (iArr[i][j] != 0) { r = j; for (k = 0; k < n; k++) { j == r; if ((iArr[k][j] != 0) && (!used[k])) { dfs(i); } } } } } } }

И, наконец, полный листинг всей программы, в которой содержится уже приведённый массив, функция обхода графа в глубину и главная функция с вызовом этой функции. Чтобы на экран выводился весь маршрут обхода, начиная с первой вершины, следует ввести значение переменной from (стартовая точка), на единицу меньшее номера первой вершины (в данном примере это " - 1 ").

Код C++

#include <iostream> using namespace std; const int n = 12; const int m = 14; int iArr[n][m] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1 }; bool used[n]; int j = 0; int r = 0; int i = 0; int k = 0; void dfs(int t) { used[t] = true; int p; for (i = k; i < n; i++) { j = r; if ((iArr[i][j] != 0) && (!used[i])) { used[i] = true; p = i; cout << i << " "; for (j = 0; j < m; j++) { i == p; if (iArr[i][j] != 0) { r = j; for (k = 0; k < n; k++) { j == r; if ((iArr[k][j] != 0) && (!used[k])) { dfs(i); } } } } } } } int main() { for (int i = 0; i < n; i++) { used[i] = false; for (int j = 0; j < m; j++) cout << " " << iArr[i][j]; cout << endl; } int from; cout << "From >> "; cin >> from; cout << "Order: " << endl; dfs(from); cout << endl; return 0; }

В результате обхода графа, приведённого в этом примере, выводится следующая последовательность вершин: 0, 4, 1, 6, 11, 7, 3, 2, 5, 10, 9, 8.

Весь блок Программирование C++

К началу страницы

Поделиться с друзьями