IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Остовное дерево, в орграфе
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Не получается написать программу нахождения любого остовного дерева в ориентированном графе.
Смотрел в FAQ, но то что там есть не помогло. Поиск и гугл тоже юзал...
Помогите, пожалуйста! smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
Смотрел в FAQ, но то что там есть не помогло.
Что ж ты тогда хочешь? Если ни "построение стягивающего дерева поиском в глубину", ни "построение стягивающего дерева поиском в ширину" отсюда тебе не помогло - я уж и не знаю, что поможет...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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


{
=====================
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}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


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

что такое остовное дерево в орграфе?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Цитата(Michael_Rybak @ 7.04.2008 1:06) *

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

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


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


Сообщение отредактировано: Слай -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


вот значит уточни сначала задание. я, например, не знаю, что такое остов орграфа. есть понятие остовного маршрута в орграфе и понятие остова в неорграфе.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


наверно, примерно то же, что и для неорграфа
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

уточни у преподавателя. как можно решить задачу, не зная точного условия?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


ну, просто из графа нужно удалить минимальное число дуг, чтобы не было циклов...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

решать как - не знаю. "классического" алгоритма для нее нет, скорее всего, ты все-таки напутал. ну или решай перебором.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


там тогда нужно еще прикрутить возвращение по стеку в поисках возможности ответвления...
не поможете?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

опиши алгоритм который ты хочешь реализовать, и где в нем прикручивать возврат по стеку.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


ну, когда мы обходим в глубину, когда мы наталкиваемся на вершину, кот. уже посещали, возвращаемся по стеку до вершины, из которой возможно еще одно ответвление
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

так что лучше сразу признавайся, если тебе нужно топологическую сортировку реализовать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

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

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

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

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

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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 22:16
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name