Версия для печати темы

Автор: Слай 6.04.2008 18:49

Не получается написать программу нахождения любого остовного дерева в ориентированном графе.
Смотрел в FAQ, но то что там есть не помогло. Поиск и гугл тоже юзал...
Помогите, пожалуйста!

Автор: volvo 7.04.2008 0:57

Что ж ты тогда хочешь? Если ни "построение стягивающего дерева поиском в глубину", ни "построение стягивающего дерева поиском в ширину" http://forum.pascal.net.ru/index.php?s=&showtopic=4030&view=findpost&p=35152 тебе не помогло - я уж и не знаю, что поможет...

Автор: Слай 7.04.2008 2:25

Ну, вот что я написал:

{
  =====================
    Poisk lyubogo ostovnogo dereva
  =====================
}
Procedure OTree(v:word);
const n=15;
Var
    stack: Array [1..n] of word;
    i, j, sp, trc: word;
    curV: word;
BEGIN
WIV[v]:=TRUE; {otmechaem, chto posetili vershinu}
for i:=1 to n do
    if (MRX[v,i]=1) and (v<>i) then
       if (WIV[i]=FALSE) then
          begin
               trc:=trc+1;
               Tree[1,yk]:=v;
               Tree[2,yk]:=i;
               count_tree:=count_tree+1;
               yk:=yk+1;
               OTree(i);
          end
       else
          begin
               StTree:=StTree+1;
               writeln('---------------------');
               if (WIV[StTree]=FALSE) then
                  OTree(StTree);
          end;
END;

в главной программе переменные:

var MRX: Array [1..n,1..n] of byte; {matrica smezhnosti}
 { OSTOVNOE DEREVO: }
    Tree: Array [1..2,1..n] of byte;
    WIV: Array [1..n] of boolean;
    itree, jtree: word;
    StTree: word;
    count_tree: word;
    yk: word;

{BEGIN: OSTOVNOE DEREVO}
for itree:=1 to n do
    WIV[itree]:=FALSE;
StTree:=1;
yk:=1;
count_tree:=0;
OTree(StTree);
    for jtree:=1 to count_tree do
        writeln(Tree[1,jtree],' | ',Tree[2,jtree]);
ReadLn;
{END: OSTOVNOE DEREVO}

Автор: Michael_Rybak 7.04.2008 4:06

тебя вольво спросил не что ты написал, а что ты хочешь, алгоритм построения чего тебе нужен?

что такое остовное дерево в орграфе?

Автор: Слай 7.04.2008 15:11

вот я про то же.. у меня в задании сказано:

Автор: Michael_Rybak 7.04.2008 15:24

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

Автор: Слай 7.04.2008 23:44

наверно, примерно то же, что и для неорграфа

Автор: Michael_Rybak 8.04.2008 0:32

примерно то же, что для неорграфа, есть в FAQ.

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

Автор: Слай 8.04.2008 2:23

ну, просто из графа нужно удалить минимальное число дуг, чтобы не было циклов...

Автор: Michael_Rybak 8.04.2008 3:00

вот так бы сразу и сказал.

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

Автор: Слай 8.04.2008 4:00

там тогда нужно еще прикрутить возвращение по стеку в поисках возможности ответвления...
не поможете?

Автор: Michael_Rybak 8.04.2008 4:18

прикрутить к чему?

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

Автор: Слай 8.04.2008 4:30

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

Автор: Michael_Rybak 8.04.2008 5:58

ты можешь сказать толком что ты делаешь и что не получается?

про поиск в глубину я должен сам был догадаться? про удаление минимального числа дуг тоже?

представь, ты приходишь в магазин и говоришь продавщице: "дайте продуктов для сладкого". продавщица такая: "каких?". ты такой: ну, вот что я купил на базаре (показываешь сумку). продавщица опять: "каких"? ты: "мама сказала, дословно: купить продуктов для сладкого!". продавщица: "если те, что на витрине - не подходят, помочь не могу". ты: "ну нужно пирог приготовить. яблочный. помогите с тестом". она: "с каким тестом?". ты: "ну чтоб его замесить". она: "КАКОЕ тесто замесить?", ты: "ну руками, руками!!! чтоб дрожжи хорошо получились!!". она: "ага, значит дрожжевое тесто и яблоки! как я сама-то не догадалась".

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

Автор: Слай 8.04.2008 14:26

топологическая сортировка, насколько я понял, действительна для графа, в котором ЗАВЕДОМО нет циклов. у меня не такой случай.
у меня есть орграф, в котором есть циклы. необходимо ударить из графа минимальное число дуг, чтобы избавиться от циклов.

Автор: Michael_Rybak 8.04.2008 17:21

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

итак, у нас уже есть условие.

на всякий случай: "чтобы избавиться от циклов" - имеются ввиду ведь ориентированные циклы?

*решения*, которое ты пробуешь реализовать, ты не описал.

поэтому мы не можем подсказать, как к нему прикрутить работу со стеком (точнее, подправить, т.к. она уже у тебя есть).

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

судя по твоему коду, ты идешь из каждой вершины поиском в глубину, и какие-то ребра заносишь в массив Tree. у меня складывается впечатление, что в Tree хранится конечный ответ. но у тебя стоит органичение n в размерности этого массива, а в орграфе у "остова" может быть порядка n^2 ребер. то есть уже тут что-то явно не так.

но проблема не в этом. а в том, что я *продолжаю угадывать*.

попытайся поставить себя на мое место, и постарайся, пожалуйста, донести до меня ту информацию, которой мне хватит, чтобы понять твою проблему.