Описание алгоритма. Постановка решения конкретного примера. Исходный код программы, страница 2

Вместо того, чтобы помечать вершины, мы будем просто приравнивать к нулю соответствующие элементы матрицы смежности рассматриваемого графа, а также приравнивать к нулю элементы, симметричные данному относительно главной диагонали. Иными словами, если мы хотим приравнять к нулю элемент с индексами i и j, то мы так же приравниваем к нулю элемент с индексами j и i. Это обусловлено тем, что в данной работе мы рассматриваем неориентированный граф, в матрице смежности которого все элементы симметричны относительно главной диагонали, и если не удалять элементы симметрично, алгоритм может работать неправильно.

Для выполнения алгоритма вручную рассмотрим следующий неориентированный граф, состоящий из 22 вершин.

Будем следовать возрастанию чисел.

Выполнение алгоритма:

1.  «1» - начальная вершина (п.1)

2.  «1» -> «2» (п.2) («2» - помечена как «были»)

3.  «2» -> «3» (п.2) («3» - помечена как «были»)

4.  «3» -> «7» (п.2) («7» - помечена как «были»)

5.  «7» -> «8» (п.2) («8» - помечена как «были»)

6.  «8» -> «9» (п.2) («9» - помечена как «были»)

7.  «9» -> «10» (п.2) («10» - помечена как «были»)

8.  «10» -> «11» (п.2) («11» - помечена как «были»)

9.  «11» -> «12» (п.2) («12» - помечена как «были»)

10. «12» -> «11» (п.3) (конец ветви графа)

11. «11» -> «13» (п.2) («13» - помечена как «были»)

12. «13» -> «11» (п.3) (конец ветви графа)

13. «11» -> «14» (п.2) («14» - помечена как «были»)

14. «14» -> «11» (п.3) (конец ветви графа)

15. «11» -> «10» (п.3) (помеченная вершина)

16. «10» -> «9» (п.3) (помеченная вершина)

17. «9» -> «16» (п.2) («16» - помечена как «были»)

18. «16» -> «17» (п.2) («17» - помечена как «были»)

19. «17» -> «16» (п.3) (конец ветви графа)

20. «16» -> «18» (п.2) («18» - помечена как «были»)

21. «18» -> «19» (п.2) («19» - помечена как «были»)

22. «19» -> «18» (п.3) (конец ветви графа)

23. «18» -> «16» (п.3) (помеченная вершина)

24. «16» -> «9» (п.3) (помеченная вершина)

25. «9» -> «8» (п.3) (помеченная вершина)

26. «8» -> «15» (п.2) («15» - помечена как «были»)

27. «15» -> «20» (п.2) («20» - помечена как «были»)

28. «20» -> «21» (п.2) («21» - помечена как «были»)

29. «21» -> «22» (п.2) («22» - помечена как «были»)

30. «22» -> «21» (п.3) (помеченная вершина)

31. «21» -> «20» (п.3) (помеченная вершина)

32. «20» -> «15» (п.3) (помеченная вершина)

33. «15» -> «8» (п.3) (помеченная вершина)

34. «8» -> «7» (п.3) (помеченная вершина)

35. «7» -> «4» (п.2) («4» - помечена как «были»)

36. «4» -> «6» (п.2) («6» - помечена как «были»)

37. «6» -> «4» (п.3) (конец ветви графа)

38. «4» -> «7» (п.3) (помеченная вершина)

39. «7» -> «5» (п.2) («5» - помечена как «были»)

40. «5» -> «7» (п.3) (помеченная вершина)

41. «7» -> «3» (п.3) (помеченная вершина)

42. «3» -> «2» (п.3) (помеченная вершина)

43. «2» -> «1» (п.3) (помеченная вершина)

44. Из «1» больше не попасть в неотмеченные вершины

45. Конец

Исходный код программы

#include <iostream>

using namespace std;

int matr[22][22] = {

{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 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, 0},

{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1},

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0}

};        

void dfs(int i)

{

for (int j = 0; j < 22; j++)

{

if (matr[i][j] == 1)

{

cout << '(' << i+1 << '-' << j+1 << ") ";             

matr[i][j] = 0;

matr[j][i] = 0;              

dfs(j);

}

}

}

int main()

{

cout << "Visited ligaments:\n";

dfs(0); 

return 0;

}

Скриншот выполнения программы