Помогите пожалуйста с программкой: "Поиск кратчайшего пути в графе методом полного перебора в ширину с использованием АТД очередь" Сам алгоритм у меня есть, но ничего не знаю про АТД очередь, ни у кого нет примеров такой программы?
работать с очередями, стеками и деками целый семестр, поэтому хотелось бы поподробнее.
Что именно "поподробнее"? Ты ж сказал, что у тебя есть алгоритм, но ты не знаешь про очереди. Все, что тебе надо знать - это то, что есть операции Put и Get, все остальное - уже детали реализации (на то он и абстрактный тип данных).
Цитата
Мне дан такой алгоритм:
Не-не... Ты перепутал все на свете... Это не процедура называется Quepush... Вот так выглядит программа в простейшем случае:
function visited(what: integer; path: WayType): boolean; var i: integer; begin visited := true; for i := low(path) to high(path) do if path[i] = what then exit; visited := false; end;
var q: TQueue; i, j, start, finish, current: integer; finished: boolean; Way: WayType;
begin q.init;
start := 1; finish := 5;
q.put(start); While not q.isEmpty do begin Current := q.get; Finished := Current = finish; j:=1; while j<=N do begin if (M[Current,j] <> 0) and not visited(j, way) then begin Way[j] := Current; Finished:=(j = finish); // если не закончили перебор - добавляем очередную вершину // в очередь, чтобы потом к ней вернуться... if not Finished then q.put(j) end; inc(j); end; end;
// а когда закончили - то печатаем путь // от конечной вершины к начальной i:=finish; write(i:3);
while i<>start do begin write(Way[i]:3); i:=Way[i]; end; writeln;
end.
(я использовал собственный модуль queue_oop, в принципе можешь использовать любой другой, по названиям методов понятно, что они делают: Put - забрасывает элемент в конец очереди, Get - вытаскивает элемент из ее начала)