Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Связный ориентированный граф

Автор: CENTRALFORWARD 19.4.2008, 17:32

Имеется связный ориентированный граф. Берется любая вершина и необходимо определить все возможные пути из этой вершины. Необходимо вывести все цепочки возможных путей на экран.
Хотелось бы пример. Заранее спасибо.

Автор: pil69 21.4.2008, 15:45

А как задается сам граф? В виде матрицы? Пример покажи

Автор: CENTRALFORWARD 22.4.2008, 07:48

Цитата(pil69 @ 21.4.2008, 15:45)

А как задается сам граф? В виде матрицы? Пример покажи

Матрицей смежности

Автор: Dobermann 25.4.2008, 20:31

В подобной теме я привёл пример http://forum.vingrad.ru/forum/topic-196541/anchor-entry1416753/0.html, который представляется матрицей смежности, каркас так же массивом....и + еще как раз в нем реализуется поиск в глубину. Вообщем тебе нужно в цикле сохранять ребра....сам цикл прогоняешь по всей матрице........

________________________________________________
и блин, пожалуйста восстановите мне кто-нибудь репу......хотя бы до 0

Автор: Naruto05 26.4.2008, 14:27

попробуй использовать поиск в глубину, он быстр и удобен. Там просто каждый раз перед началом или в конце пишешь вывод массива.
{ c:массив, хранящий все пути}
{k - счётчик элементов с}
Procedure solve(x:word);
var
     i:integer;
begin
         for i:=1 to k do begin
              write(c[i],' ');
         end;
         readln;

         for i:=1 to n do
              if (a[x,i]=1)and(b[i]) then begin
                  inc(k);c[k]:=i;b[i]:=false;
                  solve(i);
                  dec(k);b[i]:=true;
              end;
end;
a - таблица смежности
b - вектор булевского типа. обозначает, просмотрен ли элемент.
Я только прикинул процедуру, а там сам дальше разработаешь.

Автор: Dobermann 26.4.2008, 17:48

ОГО!!!
А если у него матрица смежности 50х50.........
solve(i); - может быть ты не понял, но если процедура в теле её описания вызывает сама себя, то это уже рекурсия. И получится, что она будет обращаться сама к себе.............щас-щас.............(хотя бы при размере 15х15)............437893890380859375 раз!!!
CENTRALFORWARD если не передумал разобраться с этим, то выше приведенный мной пример развеит все опасения......

Автор: CENTRALFORWARD 27.4.2008, 07:30

Суть понятна, но мне нужен вывод примерно такой:
Условно, матрица 9 на 9 и возможные пути начиная с 9 вершины (без дублирования вершин):
1) 9 2 4 5
2) 9 2 5
3) 9 2 8 7 1 6 5
4) 9 2 8 7 5
5) 9 3 4 5
6) 9 8 7 1 6 5
7) 9 8 7 2 4 5
8) 9 8 7 2 5
9) 9 8 7 5
и т.д.