Помощь - Поиск - Пользователи - Календарь
Полная версия: Остовное дерево
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Слай
Не получается написать программу нахождения любого остовного дерева в ориентированном графе.
Смотрел в FAQ, но то что там есть не помогло. Поиск и гугл тоже юзал...
Помогите, пожалуйста! smile.gif
volvo
Цитата
Смотрел в FAQ, но то что там есть не помогло.
Что ж ты тогда хочешь? Если ни "построение стягивающего дерева поиском в глубину", ни "построение стягивающего дерева поиском в ширину" отсюда тебе не помогло - я уж и не знаю, что поможет...
Слай
Ну, вот что я написал:


{
=====================
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
Цитата
Ну, вот что я написал:


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

что такое остовное дерево в орграфе?
Слай
Цитата(Michael_Rybak @ 7.04.2008 1:06) *

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

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


вот я про то же.. у меня в задании сказано:
Цитата
Составить подпрограмму нахождения и печати одного любого остовно-
го дерева заданного орграфа.
Michael_Rybak
вот значит уточни сначала задание. я, например, не знаю, что такое остов орграфа. есть понятие остовного маршрута в орграфе и понятие остова в неорграфе.
Слай
наверно, примерно то же, что и для неорграфа
Michael_Rybak
примерно то же, что для неорграфа, есть в FAQ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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