Поиск в графе 3
.pdf
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Поиск точек сочленения (формулировка алгоритма)
Все пункты ниже соответствуют пунктам поиска в глубину изменения выделены (синим цветом)
после алгоритма даны пояснения
0.(инициализация) Для каждой вершины v 2 V присваиваем
Visit[v] := 0, Father[v] := 0; num[v] := 0; counterNum := 1; numSonsRoot := 0
1.Если есть непросмотренные вершины, т. е. существует v 2 V , ÷òî Visit[v] = 0,
берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, L[v] := 1,
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Поиск точек сочленения (формулировка алгоритма)
Все пункты ниже соответствуют пунктам поиска в глубину изменения выделены (синим цветом)
после алгоритма даны пояснения
0.(инициализация) Для каждой вершины v 2 V присваиваем
Visit[v] := 0, Father[v] := 0; num[v] := 0; counterNum := 1; numSonsRoot := 0
1.Если есть непросмотренные вершины, т. е. существует v 2 V , ÷òî Visit[v] = 0,
берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, L[v] := 1, counterNum + +
Перейти к шагу 2
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Поиск точек сочленения (формулировка алгоритма)
Все пункты ниже соответствуют пунктам поиска в глубину изменения выделены (синим цветом)
после алгоритма даны пояснения
0.(инициализация) Для каждой вершины v 2 V присваиваем
Visit[v] := 0, Father[v] := 0; num[v] := 0; counterNum := 1; numSonsRoot := 0
1.Если есть непросмотренные вершины, т. е. существует v 2 V , ÷òî Visit[v] = 0,
берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, L[v] := 1, counterNum + +
Перейти к шагу 2 Если все вершины просмотрены,
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Поиск точек сочленения (формулировка алгоритма)
Все пункты ниже соответствуют пунктам поиска в глубину изменения выделены (синим цветом)
после алгоритма даны пояснения
0.(инициализация) Для каждой вершины v 2 V присваиваем
Visit[v] := 0, Father[v] := 0; num[v] := 0; counterNum := 1; numSonsRoot := 0
1.Если есть непросмотренные вершины, т. е. существует v 2 V , ÷òî Visit[v] = 0,
берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, L[v] := 1, counterNum + +
Перейти к шагу 2 Если все вершины просмотрены, то перейти к шагу 4.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Поиск точек сочленения (формулировка алгоритма)
Все пункты ниже соответствуют пунктам поиска в глубину изменения выделены (синим цветом)
после алгоритма даны пояснения
0.(инициализация) Для каждой вершины v 2 V присваиваем
Visit[v] := 0, Father[v] := 0; num[v] := 0; counterNum := 1; numSonsRoot := 0
1.Если есть непросмотренные вершины, т. е. существует v 2 V , ÷òî Visit[v] = 0,
берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, L[v] := 1, counterNum + +
Перейти к шагу 2 Если все вершины просмотрены, то перейти к шагу 4.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Формулировка алгоритма
2. Åñëè Stack 6= 0/, то просматриваем очередную вершину из стека v := Stack:Top()
перейти к шагу 3. Если Stack = 0/,
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Формулировка алгоритма
2. Åñëè Stack 6= 0/, то просматриваем очередную вершину из стека v := Stack:Top()
перейти к шагу 3.
Åñëè Stack = 0/, то перейти к шагу 4.
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Формулировка алгоритма
3. Если список смежности v просмотрен до конца, то Stack:Pop() (удаляем v из стека)
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Формулировка алгоритма
3. Если список смежности v просмотрен до конца, то Stack:Pop() (удаляем v из стека) åñëè Father[v] 6= 0, òî
L[Father[v]] := minfL[Father[v]];L[v]g,
åñëè num[Father[v]] 6 L[v], òî Father[v] точка сочленения
Расин О.В. |
Поиск в графе |
|
|
Поиск точек сочленения и блоков в графе |
Модификация поиска в глубину для поиска точек сочлене |
|
Использование свойства точек сочленения в дереве поиск |
||
|
||
|
|
Формулировка алгоритма
3. Если список смежности v просмотрен до конца, то Stack:Pop() (удаляем v из стека) åñëè Father[v] 6= 0, òî
L[Father[v]] := minfL[Father[v]];L[v]g,
åñëè num[Father[v]] 6 L[v], òî Father[v] точка сочленения
Получаем очередной элемент списка смежности (u := copyList[v]:GetNext()).
Расин О.В. |
Поиск в графе |
|
|