Skip to content

report2.md

Latest commit

 

History

History
78 lines (56 loc) · 3.55 KB

report2.md

File metadata and controls

78 lines (56 loc) · 3.55 KB

Графы 2

Задание: Поиск шарниров в графе.

Поиск шарниров в графе осуществляется с помощью модифицированного алгоритма поиска в глубину. Метод recursiveGetAp осуществляет рекурсивный "спуск" по графу из вершины ptr_.

"Спуск" осуществляется по следующему алгоритму:

  1. текущая (T) вершина помечается.
  2. Dnum (в коде это depth) и low этой вершины присваевается текущая глубина.
  3. Для каждой присоединенной (P) к текущей и не посещенной вершине выполняется:
    • 3.1 количество потомков T + 1
    • 3.2 предок P := T
    • 3.3 переход на пункт 1 для P (рекурсивный вызов функции "спуска" для P)
    • 3.4 low[T] = min(low[T], low[P])\
    • 3.5 Если у T нет предка, но есть потомки: T - шарнир
    • 3.6 Если у T есть предок и low[P] >= Dnum[T], то T это шарнир.
  4. Если P посещена и P не предок T, то необходимо пересчитать low[T] := min(low[T], low[P]).

Результатом выполнения метода recursiveGetAp будет массив result содержащий все шарниры графа и массив groups содержащий все компоненты связности.

Пример

В качестве примера в директории samples содержится файл apgraph.in в котором содержится следующий граф:

apgraph.png

Граф записан в виде матрицы смежности, которая выглядит следующим образом:

12
0 1 0 0 1 0 0 0 0 0 0 0
1 0 1 0 0 1 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0 1
1 0 0 1 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 1 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 1 0 0 1 1 0 0 0 0

Найти шарниры в графе:

./graphsalg -f graph.in -a

Найти шарниры в графе и записать "раскрашенный" граф в .json файл

./graphsalg -f graph.in -a -o graph.json -j

Найти шарниры в графе, удалить их и записать получившийся граф в .json файл

./graphsalg -f graph.in -a -d -o graph.json -j

Ввести граф с клавиатуры (как матрицу смежности) и найти шарниры в графе

./graphsalg -a

Ввести граф с клавиатуры (как матрицу смежности), найти шарниры в графе, и записать получившийся граф в файл

./graphsalg -a -o graph.json -j

Ввести граф с клавиатуры (как матрицу смежности), найти шарниры в графе, удалить шарниры и записать получившийся граф в файл

./graphsalg -a -d -o graph.json -j