Графы. Метод, отличающийся от поиска в ширину тем, что вновь достигнутая вершина помещается не в очередь, а в стек

@Viwwna · Регистрация: 18.11.2011

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

Прошу помочь с Графами по поиску в глубину.... Задача такая:
Напишите и используйте в программе процедуру, реализующую метод, отличающийся от поиска в ширину только тем, что вновь достигнутая вершина помещается не в очередь, а в стек.

Спасибо, кто откликнется...

Pascal

const n=9;
C:array[0..n,0..n] of 0..1=
((...матрица смежности))
visit:array[0..n] of boolean=
(true,true,true,true,true,true,true,true,true);
var v:integer;
procedure DFS(v:integer);
var Stek:array[1..(n+1)] of 0..n;
t,Uk:integer;f:boolean;
begin
write(v:3);
Uk:=0;
Uk:=Uk+1;
stek[Uk]:=v;
visit[v]:=false;
while Uk<>0 do
begin
v:=stek[Uk];
t:=0;f:=false;
repeat
if(C[v,t]=1) and (visit[t]) then 
f:=true
else
t:=t+1;
until f or (t>n);
if f then begin
write(t:3);
Inc(Uk);
stek[Uk]:=t;
visit[t]:=false;
end
else
Uk:=Uk-1;
end;
end;
begin
writeln('поиск в глубину');
writeln('введите вершину начала поиска');
readln(v);
DFS(v);
end.

Добавлено через 16 часов 6 минут
Все еще нуждаюсь в Вашей помощи.

@Small Lamer · 03.07.2012, 18:14

Pascal

procedure Dfs(v :longint);
var i :longint;
begin
    was[v] := true;
    for i := 1 to n do
        if (was[i] = false) and (a[v][i] = true) then Dfs(i);
end;

21.05.2013, 16:31

Всем здравствуйте. Снова поднимаю данную тему, как не раскрытую. Предложение использовать поиск в глубину не актуален, т.к. преподаватель такую работу не принял. Данную задачу нашел в книге Липского "Комбинаторика для программистов". У него звучит задача так: "Исследовать метод, отличающийся от поиска в ширину только тем, что
вновьдостигнутая вершина помещается в стек (такой алгоритм описывается в
точности процедурой WS, в которой ОЧЕРЕДЬ заменена на СТЕК) [35]."

1. procedure WS(v); (* поиск в ширину в графе с началом в вершине v;
переменные НОВЫЙ, ЗАПИСЬ — глобальные*)
2. begin
3. ОЧЕРЕДЬ ∅; ОЧЕРЕДЬ ⇐ v; НОВЫЙ v :=ложь
4. while ОЧЕРЕДЬ ∅ do
5. begin p ⇐ ОЧЕРЕДЬ; посетить p;
6. for u ∈ ЗАПИСЬ p do
7. if НОВЫЙ u then
8. begin ОЧЕРЕДЬ ⇐ u; НОВЫЙ u :=ложь
9. end
10. end
11. end

В этой книге делается ссылка на источник, содержащий эту задачу в оригинале. Звучит там она так:
Another way to search a graph is D-search. this method differs from BFS in that the next vertex to explore is the vertex most recently added to the list of unexplored vertices. hence,this list operates as a stack rather then a queue. write an algorithm for D-search. show that D-search starting from vertex v visits all vertices reachable from v. what are the time and space requirements of your algorithm?

Понятно, что алгоритм, который надо написать, не есть поиск в ширину и не есть поиск в глубину. Это третий вариант, причем не могу понять, как можно заменить очередь в поиске в ширину на стек так, чтобы он не превратился а поиск в глубину.
Была мысль, а что если добавлять новые найденные вершины в начало очереди, но для этого надо использовать двусвязную очередь, а это уже другая задача. http://ric.uni-altai.ru/Fundam... most-5.htm - тут вот есть и данная задача и задача про дек.
Подобные темы: http://forum.shelek.ru/index.p... 772.0.html

http://forum.ru-board.com/topi... start=7760

Задача поиска в глубину реализована, она ищет число компонент связности графа по матрице смежности. Все работает, но преподавателю надо иное. Цитата из рецензии: "Задание не выполнено. Необходимо использовать поиск в ширину с использованием очереди. При описании алгоритма решения задачи следует делать упор именно на поиск, и показать где и каким образом реализуется очередь." Вероятно, он имел ввиду стек, а не очередь.

MaxMas
	21.05.2013, 16:31	3
	Всем здравствуйте. Снова поднимаю данную тему, как не раскрытую. Предложение использовать поиск в глубину не актуален, т.к. преподаватель такую работу не принял. Данную задачу нашел в книге Липского "Комбинаторика для программистов". У него звучит задача так: "Исследовать метод, отличающийся от поиска в ширину только тем, что вновьдостигнутая вершина помещается в стек (такой алгоритм описывается в точности процедурой WS, в которой ОЧЕРЕДЬ заменена на СТЕК) [35]." 1. procedure WS(v); (* поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, ЗАПИСЬ — глобальные*) 2. begin 3. ОЧЕРЕДЬ ∅; ОЧЕРЕДЬ ⇐ v; НОВЫЙ v :=ложь 4. while ОЧЕРЕДЬ ∅ do 5. begin p ⇐ ОЧЕРЕДЬ; посетить p; 6. for u ∈ ЗАПИСЬ p do 7. if НОВЫЙ u then 8. begin ОЧЕРЕДЬ ⇐ u; НОВЫЙ u :=ложь 9. end 10. end 11. end В этой книге делается ссылка на источник, содержащий эту задачу в оригинале. Звучит там она так: Another way to search a graph is D-search. this method differs from BFS in that the next vertex to explore is the vertex most recently added to the list of unexplored vertices. hence,this list operates as a stack rather then a queue. write an algorithm for D-search. show that D-search starting from vertex v visits all vertices reachable from v. what are the time and space requirements of your algorithm? Понятно, что алгоритм, который надо написать, не есть поиск в ширину и не есть поиск в глубину. Это третий вариант, причем не могу понять, как можно заменить очередь в поиске в ширину на стек так, чтобы он не превратился а поиск в глубину. Была мысль, а что если добавлять новые найденные вершины в начало очереди, но для этого надо использовать двусвязную очередь, а это уже другая задача. http://ric.uni-altai.ru/Fundam... most-5.htm - тут вот есть и данная задача и задача про дек. Подобные темы: http://forum.shelek.ru/index.p... 772.0.html http://forum.ru-board.com/topi... start=7760 Задача поиска в глубину реализована, она ищет число компонент связности графа по матрице смежности. Все работает, но преподавателю надо иное. Цитата из рецензии: "Задание не выполнено. Необходимо использовать поиск в ширину с использованием очереди. При описании алгоритма решения задачи следует делать упор именно на поиск, и показать где и каким образом реализуется очередь." Вероятно, он имел ввиду стек, а не очередь.