Поиск в графе 3

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u);

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1;

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1; Father[u] := 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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum,

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, L[u] := counterNum,

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, L[u] := counterNum, counterNum + +

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, L[u] := counterNum, counterNum + +

á) Åñëè Visit[u] = true, ïðè num[v] > num[u] è u 6= Father[v] , òî L[v] := minfL[v];num[u]g

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

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()).

à) Åñëè u еще не посещалась (Visit[u] = 0), òî ïðè Father[v] = 0; numSonsRoot + +

Stack:Push(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, L[u] := counterNum, counterNum + +

á) Åñëè Visit[u] = true, ïðè num[v] > num[u] è u 6= Father[v] , òî L[v] := minfL[v];num[u]g

Перейти к шагу 2.

Расин О.В.	Поиск в графе

	Поиск точек сочленения и блоков в графе	Модификация поиска в глубину для поиска точек сочлене
		Использование свойства точек сочленения в дереве поиск

Формулировка алгоритма

4. åñëè numSonsRoot > 1, òî v точка сочленения

Расин О.В.	Поиск в графе