Написать алгоритм нахождения всех возможных путей орграфа из вершины A в B.

[R@UBTIER]

Написать алгоритм нахождения всех возможных путей орграфа из вершины A в B.

Ориентированный граф имеет 7 вершин, 12 ребер.

Ребра, их вершины и направления:

1_2 1_4 1_3

2_4 2_5

3_1 3_6 3_7

4_3 4_6

5_6

6_7

Получается матрица смежности вида x,y:

____y1 -> y7

x1 0 1 1 1 0 0 0

x2 0 0 0 1 1 0 0

x3 1 0 0 0 0 1 1

x4 0 0 1 0 0 1 0

x5 0 0 0 0 0 1 0

x6 0 0 0 0 0 0 1

x7 0 0 0 0 0 0 0

Надо найти путь из каждой вершины в вершину 7.

Результаты записать на тетради из семи листов.

На первом листе указаны все возможные пути из вершины 1 в вершину 7:

Путь 1 - 12437

Путь 2 - 12567

Путь 3 - 1367

Путь 4 - 137

Путь 5 - 1437

Путь 6 - 1467

и т.д.

На втором листе указаны все возможные пути из вершины 2 в вершину 7:

Путь 1 - 2437

Путь 2 - 2567

Путь 3 - 2467

и т.д

На остальных листах также ...

Данные тетради хранятся в трехмерном массиве (куб) ...

Условия поиска:

Количество вершин в пути не больше 13.

Количество ребер в пути не больше 12.

Это моя маленькая подзадача с которой я не могу справиться, самой же задачей является игра "Кот и Лиса" (227 Задача из книги Б.Н. Иванова - "Дискретная математика. Алгоритмы и программы.). После решения описанной выше задачи мне нужно будет использовать фильтры, чтобы отсеять не нужные пути, но с этим я попробую разобраться сам. Помогите мне или подскажите мне, как найти исходя из матрицы смежности (двумерный массив), найти все возможные маршруты по условию и записать полученные данные в трехмерный массив. Эта задача часть моей курсовой по Доп. гл. Дискретной Математики. Какие алгоритмы использовать - Алгоритм А*, Дейкстры, Йена, обход в глубину или в ширину, как это реализовать???

Начал делать на Turbo Pascal. Рассмотрю любые идеи и буду благодарен.

[TolkienDRR]

R@UBTIER, 2ой курс повтаса? могу поспрашивать некоторых людей, мож кто такое делал. за N-ную сумму продадут с отчетом и т.п.

[R@UBTIER]

3-й Курс ПОВТАС, ДОУ ... Да, можно и поспрашивать ...

[TolkienDRR]

R@UBTIER, хе, с тобой некая Женя Ноходоева учится поди? =)

[R@UBTIER]

Нет! Д639-5 Группа! МРИПК ВСГТУ

[genemy]

писал что то подобное на cpp

может пригодится

http://genemy.inkosmos.org/quest_dlg.txt

[0xDEADBEEF]

R@UBTIER

Не могли бы вы выложить условие задачи сюда.

[R@UBTIER]

227. Кот и Лиса.

Дан ориентированный граф Г= (X, U, Ф), вершины которого являются позициями в следующей игре. Участвуют два игрока — Кот и Лиса. Они двигают фишку из позиции в позицию по дугам графа. Множество позиций X разделено на два подмножества Х= (К "объединение" Л). В позициях Л ход делает Лиса, а в позициях К— Кот. Если игра находится в позиции х "принадлежит" X, владелец этой позиции выбирает произвольную выходящую дугу (х, у) "принадлежит" U и двигает фишку из х в у. Игра начинается в некоторой позиции. Лиса выигрывает, если фишка оказалась в фиксированной вершине z "принадлежит" X. Если за любое количество ходов фишка не попадает в эту позицию z "принадлежит" X, то выигрывает Кот.

Составить алгоритм — программу, которая определяет все выигрышные стартовые позиции для Лисы при оптимальной стратегии обеих сторон. Считаем, что Х={1, 2,..., n), 1

Исходные данные представлены в текстовом файле, имеющем следующую структуру.

Первая строка: n, m, z, где n — число вершин, m — число дуг, z — заключительная позиция.

Со второй строки записаны: b1, b2,..., bn и х1у1,х2y2, ... , хmуm где bi=1, если вершина i принадлежит Лисе; bi = 0, если вершина i принадлежит Коту; xiyi - список дуг графа, хi — начальная вершина, yi — конечная вершина соответствующей дуги.

Все параметры — целые числа, разделенные пробелами.

Пример входного файла:

7 12 7

0 1 0 0 0 1 0

1 2 1 4 1 3

2 4 2 5

3 1 3 6 3 7

4 3 4 6

5 6

6 7

Результат представить в текстовом файле, в котором записать n целых чисел с1, с2, ... , сi, где сi = 1, если позиция выигрышная для Лисы; иначе сi = 0.

Для примера результаты расчетов представляются строкой:

0 1 0 0 1 1 1

Я пока только это сделал:

Program FOX;

Uses crt;

Var

myin,out:text; {in and out files}

n,m,z:integer; {nodes, arrows, finish}

fn:array [1..10] of integer; {FOX's nodes}

xy:array [1..10,1..10] of integer;{main graph matrix}

{array of way's - all ways to z:}

aw:array [1..10,1..20,1..50] of longint;

i,j,k,w,wn:integer; {some variables}

Begin

Assign(myin, 'MYW\in.txt');{connect to in.txt}

Reset(myin); {set for read}

ReadLn(myin, n); {read n}

ReadLn(myin, m); {read m}

ReadLn(myin, z); {read z}

clrscr; {Clear Screen}

{Write information about n, m, z:}

WriteLn('Directed graph have ',n,' nodes and ',m,' arrows.');

WriteLn('Finish position in node number ',z,'.');

{Read FOX's nodes and add it to array fn:}

For i:=1 to n do

begin

Read(myin, fn);

end;

{Write FOX nodes:}

Writeln('FOX nodes:');

For i:=1 to n do

begin

if fn=1

then Write(' ',i);

end;

Writeln('');

Writeln('Adjacency matrix:');

{read graph arrows and add it to xy matrix:}

For k:=1 to m do

begin

Read(myin, i);

Read(myin, j);

xy[i,j]:=1

end;

Close(myin); {close file in.txt}

For i:=1 to n do

begin

for j:=1 to n do

begin

Write(' ',xy[i,j]);

end;

Writeln('');

end;

{Find ways:} {Дальше фигней маюсь:}

For i:=1 to n do

begin

if xy[i,z]=1

then

begin

Write('Ways from ',i,' to ',z,';','Way - ',w,':');

Writeln(' ',i,' ',z);

{wa[i,w,wn]:=}

w:=w+1;

end;

end;

end.

[0xDEADBEEF]

R@UBTIER

В той постановке, в которой вы хотите ее решать сложность будет порядка N^(N-2), где N - количество вершин. Оценка вытекает из алгоритма поиска всех путей - а именно простой dfs, проходящий все эти пути.

Решить ее можно одним bfs'ом, используя базовые понятия игр на графах.

[R@UBTIER]

R@UBTIER

В той постановке, в которой вы хотите ее решать сложность будет порядка N^(N-2), где N - количество вершин. Оценка вытекает из алгоритма поиска всех путей - а именно простой dfs, проходящий все эти пути.

Решить ее можно одним bfs'ом, используя базовые понятия игр на графах.

Спасибо, а можно поподробней, что такое dfs и bfs, в смысле Breadth-first search, тогда может материал какой подскажите, о том как условия ставить при поиске?

[0xDEADBEEF]

R@UBTIER

Тема - игры на графах. Нужны самые начала - N-P позиции (т.е. выигрышные/проигрышные).

http://e-maxx.ru/algo/games_on_graphs

Тут небольшое описание и пример. В ваше задаче разница в том, что ходят не по очереди, а по принадлежности.

[R@UBTIER]

Почитав код и условия задачи, проведя некоторые тесты по игре и немного подумав, решил использовать в этой задаче алгоритм Дейкстры.

Почему именно Дейкстры?

Потому что этот алгоритм проще реализовать в данной задаче.

Как появилась такая идея?

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

Я реализовал данную задачу так:

1) Создал две матрицы смежности с весами, одну для Кота, другую для Лисы.

2) Будем считать что ходы из своей вершины дешевле, чем ходы из чужих вершин, присваиваем матрицам смежности Кота и Лисы стоимость хода из своей вершины в любую другую равную единице.

3) Поэтому для остальных ходов присваиваем стоимость равную m, как бы если бы какая-либо точка A перешла в саму же себя пройдя все ребра.

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

Вот и все. 0xDEADBEEF, спасибо за помощь.

Тема закрыта.

[0xDEADBEEF]

Ваши рассуждения в корне не верны.

[R@UBTIER]

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

[0xDEADBEEF]

1. Потомучто на каждую выкладку можно придумать нехитрый контр пример.

2. Ничейных позиций быть не может.

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

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

3.

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

Выйгрышный путь может состоять только из вершин кота, может заходить на вершины кота, может делать, вообще говоря, любые ходы. Заранее сказать нельзя.

[R@UBTIER]

1. Потомучто на каждую выкладку можно придумать нехитрый контр пример.

1. Согласен, такие примеры можно привести, проблема в том что не указано количество фишек, одна или две? Какие выкладки вы имеете в виду, и как тут рассматривать с двумя или с одной фишкой?

2. Ничейных позиций быть не может.

2. Согласен, у меня их нет.

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

Согласен, если они равны, то позиция выигрышная для обеих сторон. А если она выигрышная, то разве мы не можем написать её в ответе? Что значит матрицы не равноценны, они у меня одинаковые, там только веса разные, что вы имели в виду?

3. Выйгрышный путь может состоять только из вершин кота, может заходить на вершины кота, может делать, вообще говоря, любые ходы. Заранее сказать нельзя.

3. Тоже согласен, но все равно путаюсь, тогда для чего было указано какие вершины принадлежат лисе?

Ниже представлен рассматриваемый график:

Выигрышные позиции лисы: 2,5,6,7.

По какому принципу получается такой ответ?

Если делать два поиска Дейкстры в двух матрицах с весами, а потом сравнивать вес кратчайших путей, то ответ сходится.

Если я ошибаюсь, то по какому алгоритму Теории Графов лучше искать ответы?

P.S.: В конец запутался, уже устал от этой задачи ...

Указанные по ссылкам выше примеры не могу понять ...

[0xDEADBEEF]

Фишка одна, двигать ее может только владелец позиции.

Позиция не может быть выигрышной для обоих сторон. Наша игра - с нулевой суммой, т.е. если кто-то выигрывает, то другой обязательно проиграет.

Так получилось, что для вашего решения тестовый пример сработал). А вот на таком графе, который иллюстрирует почти все противоречия, нет:

Лиса-->Лиса-->Кот --> Кот --> Кот --> Z

1 2 3 4 5

1. От позиции 3 лисья позиция ни разу не встретилась, однако выигрывает однозначно лиса.

2. От позиции 1 длины путей длина пути для кота меньше, чем для лисы. однако однозначно выигрывает она.

Итак. Будем каждой вершине проставлять метки П и В (проигрышная и выигрышная), для игры с поочередным ходом:

1. Если из вершины с мы можем попасть только в в вершины с меткой В, то эта вершина П.

2. В другом случае она В.

Оптимальная стратегия предельно проста - мы должны перевести следующего игрока в П вершину, т.е. ту из которой он не сможет сделать выигрышный ход.

Теперь принимая во внимания условия задачи, модифицируем. Для определенности П,В метки расставляются относительно лисы:

Стратегия кота - ходить только в П вершины. Для лисы наоборот.

Для вершины кота:

1. Если из вершины мы можем попасть только в В вершины (неважно чьи), то эта позиция В (относительно лисы)

2. Иначе это П.

Для вершины лисы:

1. Если из вершины мы можем попасть только в П вершины (неважно чьи), то эта позиция П.

2. Иначе это В.

Помечать можно дфсом или бфсм (на свой вкус) из вершины Z. Не пройденные (не помеченные) вершины являются П.

[R@UBTIER]

Фишка одна, двигать ее может только владелец позиции.

Почему фишку может двигать только владелец позиции, разве ходы делаются не по очереди?

Позиция не может быть выигрышной для обоих сторон. Наша игра - с нулевой суммой, т.е. если кто-то выигрывает, то другой обязательно проиграет.

Что такое нулевая сумма?

Так получилось, что для вашего решения тестовый пример сработал).

Под тестовым примером вы имеете в виду пример данный в самой задаче?

А вот на таком графе, который иллюстрирует почти все противоречия, нет:

Лиса-->Лиса-->Кот --> Кот --> Кот --> Z

1 2 3 4 5

На каком таком графе, какие противоречия? Этот момент я вообще не понял, вы имеете в виду - движение из позиции 1 в Z?

1. От позиции 3 лисья позиция ни разу не встретилась, однако выигрывает однозначно лиса.

2. От позиции 1 длины путей длина пути для кота меньше, чем для лисы. однако однозначно выигрывает она.

1. Тогда почему для позиции 3 в ответе эта позиция является проигрышной для лисы?

2. Для позиции 1 тоже-же в ответе эта позиция указана как проигрышная.

Цель задачи, как я понял из её условия, найти выигрышные позиции из которых Лиса может добраться до вершины z. Если лиса не доберется из какой-то позиции до позиции z (из-за условий, об этом ниже), то эта позиция проигрышная.

Чтобы ответы сходились, я считал все возможные ходы, получилось что есть определенные условия, то есть лиса не может ходить не на свою позицию, если у нее есть возможность пойти в свою. Так как позиция 7 наверняка никому не принадлежит, то ход в нее можно сделать только из своей позиции, если нет возможности сделать из своей позиции, то тогда делается из чужой. Нужно пройти две свои позиции, если такая возможность имеется (пример если находим путь из 4 в 7, в ответе позиция 4 проигрышная для лисы).

Если посчитать стоимости, для пути с позиции 1 до поизиции 7, при маршруте 1-3-7 стоимость пути для Кота равна 2, а для Лисы 24, значит она проигрышная для Лисы. Естественно по условиям такой маршрут из 1 в 7 является неправильным, если есть возможность пойти в свою позицию, то нужно в нее и идти + еще можно предположить, что есть возможность снизить стоимость, а значит лиса пойдет в позицию 2 (по условию она обязана туда идти), а там как мы видим "тупик". Если мы бы начинали с позиции 2, то первым ходом мы по любому сделали бы ход в чужую позицию, иначе позиция проигрышная, а значит из этого следует что первый ход можно сделать не в свою позицию. Конечно это рассуждение может быть неправильным, но больше я никак не могу объяснить почему получились именно такие результаты в ответе, а именно позиции 2, 5, 6 и 7.

Итак. Будем каждой вершине проставлять метки П и В (проигрышная и выигрышная), для игры с поочередным ходом:

1. Если из вершины с мы можем попасть только в в вершины с меткой В, то эта вершина П.

2. В другом случае она В.

Оптимальная стратегия предельно проста - мы должны перевести следующего игрока в П вершину, т.е. ту из которой он не сможет сделать выигрышный ход.

Что за вершина "с", откуда мы смотрим куда попасть? И тогда как определить что позиция является П или В, мы же ведь этого не знаем? Как мы узнаем что с позиции нельзя сделать ходов, и вообще если туда сделать ход, то как мы доберемся до позиции z? Ведь наша цель добраться до позиции z или нет?

Теперь принимая во внимания условия задачи, модифицируем. Для определенности П,В метки расставляются относительно лисы:

Стратегия кота - ходить только в П вершины. Для лисы наоборот.

Как модифицируем задачу? Опять же, как расставить П, В метки если нам нужно их искать? Почему Коту ходить можно только в позиции П и лисе наоборот в В, разве мы не берем во внимание В позиции Кота, или этого не надо делать?

Для вершины кота:

1. Если из вершины мы можем попасть только в В вершины (неважно чьи), то эта позиция В (относительно лисы)

2. Иначе это П.

Для вершины лисы:

1. Если из вершины мы можем попасть только в П вершины (неважно чьи), то эта позиция П.

2. Иначе это В.

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

Помечать можно дфсом или бфсм (на свой вкус) из вершины z. Не пройденные (не помеченные) вершины являются П.

Что такое дфс и бфс, это алгоритмы обхода графа, какие?

Заранее извиняюсь за такое множество вопросов, но я видимо действительно плохо во всем этом разобрался, либо точно "тугодум", не судите строго, если бы я в этом разбирался, то давно бы все сделал!

[0xDEADBEEF]

Постараюсь ответить на все.

1. Ход делает владелец позиции:

Множество позиций X разделено на два подмножества Х= (К "объединение" Л). В позициях Л ход делает Лиса, а в позициях К— Кот. Если игра находится в позиции х "принадлежит" X, владелец этой позиции выбирает произвольную выходящую дугу (х, у) "принадлежит" U и двигает фишку из х в у

Нулевая сумма проще говоря, это если 1 выигрывает, то другой обязательно проигрывает. Если за выигрыш дают 1 (балл) за проигрыш -1, а за ничью 0. Если у нас 2 игрока и один из них выиграл (получил 1), то другой обязательно получит -1 (проиграет) чтобы в сумме получилось 0.

Тестовый пример имелся ввиду тот, который дан в задаче.

Контрпример - это то что я нарисовал, пояснения тоже к нему относятся, а не к примеру из задачи.

Что за вершина "с", откуда мы смотрим куда попасть? И тогда как определить что позиция является П или В, мы же ведь этого не знаем? Как мы узнаем что с позиции нельзя сделать ходов, и вообще если туда сделать ход, то как мы доберемся до позиции Z? Ведь наша цель добраться до позиции z или нет?

Процедура можно сказать рекурсивная, стартует от заранее известных позиций (в нашем случае Z). Как узнать? - здесь ничего сложного: стартуя из Z и идя по инвертированным ребрам для каждой вершины считаем количество П (В) вершин, в которые мы можем из нее попасть. После этого сравниваем степень вершины с данным числом - это даст ответ на вопрос все ли пути ведут в П (В) вершины, и далее в зависимости от владельца выдаем ответ.

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

То что вы здесь процитировали и есть алгоритм расстановки.

если вспомнить, что пометки расставляются относительно лисы - то ясно что лиса всегда хочет выиграть, а значит идет по своим выигрышам. Кот наоборот идет по ее проигрышам, те.е своим выигрышам.

ДФС = Depth First Search - поиск в глубину.

БФС = Breadth First Serch - поиск в ширину.

Давайте попробуем расставить метки для примера из задачи.

Делать это будем поиском в ширину.

У нас 2 массива D - степени вершин по исходу, P - количество П вершин, в которые мы можем попасть, V - количество V вершин. Нужно отметить важный факт D = V+P.

Вершину можно считать рассмотренной, когда для нее можно поставить пометку.

Z - заранее известная В позиция.

1. В нее можем прийти из 2х вершин 3 и 6. Значит V[3] = 1, V[6] = 1;

вершина 6 полностью рассмотрена: имеем D[6] = 1, V[6] = 1. Т.к. она принадлежит лисе и есть ход в В, то она В.

2. В 6 попадаем из 5, 4, 3 значит V[5] = 1, V[4] = 1, V[3] = 2; Для 3х V[1] = 1, V[4] = 2.

вершина 5 полностью рассмотрена: имеем D[5] = 1, V[5] = 1, Т.к. она принадлежит коту и

из нее нет хода в П, значит она В.

3 не является рассмотренной, т.к. не все исходы из нее известны.

3. Далее в 5 попадаем из 2 V[2] = 1 может считаться рассмотренной и получает метку В (принадлежит лисе, имеет ход в В). В 4 из 2 и 1, но для них ничего не происходить, т.к. 2 уже рассмотрена, а 1 еще нет.

У нас остались 3 не рассмотренные вершины - для них мы можем однозначно поставить метку П.

К стати этот пример дает ответ на вопрос о результате игры, когда коту выгодно бесконечно ходить по кругу.

[R@UBTIER]

Спасибо большое за помощь, очень вам признателен!

Суть почти ясна, но есть еще некоторые вопросы:

После этого сравниваем степень вершины с данным числом - это даст ответ на вопрос все ли пути ведут в П (В) вершины ...

Степень вершины и данное число, это что?

У нас 2 массива D - степени вершин по исходу, P - количество П вершин, в которые мы можем попасть, V - количество V вершин. Нужно отметить важный факт D = V+P.

Что записывается в массив D, как это выглядит? Два массива D, или все таки их три - D,V,P? Почему значения массива D равно сумме значений V и P?

Вершину можно считать рассмотренной, когда для нее можно поставить пометку.

Это как?

вершина 6 полностью рассмотрена: имеем D[6] = 1, V[6] = 1. Т.к. она принадлежит лисе и есть ход в В, то она В.

Когда считать вершиной рассмотренной?

V увеличивается на один когда рассматривается два раза?

Условие при котором позиция является выйгрышной это:

Если позиция принадлежит лисе и имеет ход в В;

Иначе если позиция принадлежит коту и не имеет ход в П.

Если неправильно сформулировано, то как будет правильно задать такое условие?

Каким образом дает ответ о бесконечных ходах кота?

P.S.:

Очень конечно стесняюсь из-за того, что вам приходится все это "разжевывать" мне ...

Буду очень благодарен вам ...

[0xDEADBEEF]

Данное число - количество П (В) вершин.

Очевидно всетаки 3 массива). Множетсво смежных вершин с данно разбивается на 2 (V и P), поэтому V+P = D;

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

Для вершины кота:

1. Если из вершины мы можем попасть только в В вершины (неважно чьи), то эта позиция В (относительно лисы)

2. Иначе это П.

Для вершины лисы:

1. Если из вершины мы можем попасть только в П вершины (неважно чьи), то эта позиция П.

2. Иначе это В.

Вот правила для расстановки меток, из них все следует.

Если расставить все метки в примере - то получается что для кота выйгрышные 1,3,4. Которые образуют цикл. Значит чтобы выйграть он должен ходить по этому циклу. Бесконечно.

[R@UBTIER]

Для вершины кота:

1. Если из вершины мы можем попасть только в В вершины (неважно чьи), то эта позиция В (относительно лисы)

2. Иначе это П.

Для вершины лисы:

1. Если из вершины мы можем попасть только в П вершины (неважно чьи), то эта позиция П.

2. Иначе это В.

Я не разобрался как будут выглядеть представленные выше условия в коде на Паскаль, два дня думал и ничего интересного в голову не пришло, решил снова обратиться за советом. Нашел из учебника Окулова С. М. - "Программирование в алгоритмах" код процедуры BFS (см. ниже), как изменить эту процедуру и добавить в неё представленные выше условия? Опишите псевдокодом ... будет здорово если на Паскале ...

|Procedure Pw (v:Integer);

|Var

| Og:Array[1..N] Of 0..N;{*Очередь.*}

| yk1,yk2:Integer;{*Указатели очереди, yk1 - запись; yk2 - чтение.*}

| j:integer;

|Begin

| FillChar(Og,SizeOf(Og),0);

| yk1:=0; yk2:=0;{*Начальная инициализация. *}

| Inc(yk1); Og[yk1]:=v; For j:=1 to N do Nnew[j]:=False;{*B очередь - вершину v.*}

| While yk2<=yk1 Do

| | |Begin {*Пока очередь не пуста.*}

| | | | Inc(yk2); v:=Og[yk2]; Write(v:3);{*"Берем" элемент из очереди.*)

| | | | For j:=1 To N Do {*Просмотр всех вершин, связанных с вершиной v.*}

| | | | |If (A[j,v]<>0) And (Nnew[j]=false)

| | | | |Then

| | | | | |Begin

| | | | | | Inc (yk1); Og[yk1]:=j; Nnew[v]:=true; {*Если вершина ранее не просмотрена, то заносим её номер в очередь.*}

| | | | | |End;

| | |End;

|End;

v - фиксированная вершина.

А - это матрица смежности.

N - это количество вершин.

Для фиксации признака, просмотрена вершина графа или нет,

представлена структура данных типа: Nnew: Array[1..N] Of Boolean.

Злая задачка все-таки попалась.