Нахождение компоненты сильной связности методом поиска в ширину

@N@tali · Регистрация: 20.02.2010

Author24 — интернет-сервис помощи студентам

Нахождение компоненты сильной связности методом поиска в ширину

Прошу помочь с описанием словесного алгоритма... нужно для программирования
В интернете есть подробное описание поиска компоненты сильной связности методом поиска в глубину...
В чем различия этих методов ?

@kazak · 28.10.2011, 00:17

Сообщение от N@tali

В чем различия этих методов ?

Один использует стек, другой очередь.

@N@tali · 28.10.2011, 09:52 **[ТС]**

Есть какой нибудь пример ? возьмем хотя бы три вершины

@kazak · 30.10.2011, 05:53

Вход: граф G{V,E), представленный списками смежности Г.
Выход: R − последовательность вершин обхода.
for v∈V do x[v]:= 0 { вначале все вершины не отмечены }
end for
select v∈V { начало обхода — произвольная вершина }
v→T { помещаем v в структуру данных T}
x[v]:= 1 {... и отмечаем вершину v }
repeat
. u←T {извлекаем вершину из структуры данных Т: T:=T\{u}...}
. u→R {и возвращаем ее в качестве очередной пройденной вершины }
. for w∈Г(u) do
. . if x[w]=0 then
. . . w→T {помещаем w в структуру данных T ... }
. . . x[w]:= 1 { ... и отмечаем вершину w }
. . end if
. end for
until T=∅
Если T − это стек (LIFO — Last In First Out), то обход называется
поиском в глубину. Если T — это очередь (FIFO — First In First Out),
то обход называется поиском в ширину.

@N@tali · 30.10.2011, 12:57 **[ТС]**

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

@kazak · 31.10.2011, 13:52

Мда, бяда...
Нашел пока только такую реализацию http://e-maxx.ru/algo/strong_connected_components с обходом в глубину. Как его под обход в ширину переделать, незнаю, надо будет поразмышлять на досуге. Если это вообще возможно.

@N@tali 781 / 462 / 85 Регистрация: 20.02.2010 Сообщений: 974
		1
	Нахождение компоненты сильной связности методом поиска в ширину 27.10.2011, 21:10. Показов 2979. Ответов 5 Метки нет (Все метки) Нахождение компоненты сильной связности методом поиска в ширину Прошу помочь с описанием словесного алгоритма... нужно для программирования В интернете есть подробное описание поиска компоненты сильной связности методом поиска в глубину... В чем различия этих методов ? 0

@kazak 3528 / 2686 / 334 Регистрация: 11.03.2009 Сообщений: 6,168
	28.10.2011, 00:17	2
	Сообщение от N@tali В чем различия этих методов ? Один использует стек, другой очередь. 1

@N@tali 781 / 462 / 85 Регистрация: 20.02.2010 Сообщений: 974
	28.10.2011, 09:52 [ТС]	3
	Есть какой нибудь пример ? возьмем хотя бы три вершины 0

@kazak 3528 / 2686 / 334 Регистрация: 11.03.2009 Сообщений: 6,168
	30.10.2011, 05:53	4
	Вход: граф G{V,E), представленный списками смежности Г. Выход: R − последовательность вершин обхода. for v∈V do x[v]:= 0 { вначале все вершины не отмечены } end for select v∈V { начало обхода — произвольная вершина } v→T { помещаем v в структуру данных T} x[v]:= 1 {... и отмечаем вершину v } repeat . u←T {извлекаем вершину из структуры данных Т: T:=T\{u}...} . u→R {и возвращаем ее в качестве очередной пройденной вершины } . for w∈Г(u) do . . if x[w]=0 then . . . w→T {помещаем w в структуру данных T ... } . . . x[w]:= 1 { ... и отмечаем вершину w } . . end if . end for until T=∅ Если T − это стек (LIFO — Last In First Out), то обход называется поиском в глубину. Если T — это очередь (FIFO — First In First Out), то обход называется поиском в ширину. 2

@N@tali 781 / 462 / 85 Регистрация: 20.02.2010 Сообщений: 974
	30.10.2011, 12:57 [ТС]	5
	Так впринципе и делала но преподаватель говорит что потом матрица смежности должна транспонироваться и снова должен быть сделан еще раз обход и потом только находим вершины компонент сильной связности, а мне нигде в интернете про обход в ширину такое не встечалось мне 0

@kazak 3528 / 2686 / 334 Регистрация: 11.03.2009 Сообщений: 6,168
	31.10.2011, 13:52	6
	Мда, бяда... Нашел пока только такую реализацию http://e-maxx.ru/algo/strong_connected_components с обходом в глубину. Как его под обход в ширину переделать, незнаю, надо будет поразмышлять на досуге. Если это вообще возможно. 0