Господа, знание, а точнее не знание математики на должном уровне не позволяет помочь товарищу в написании программы "прооверка графа на ацикличность". Будьте добры поделиться исходником на си или паскале.
Здравствуйте, Аноним, Вы писали:
А>Господа, знание, а точнее не знание математики на должном уровне не позволяет помочь товарищу в написании программы "прооверка графа на ацикличность". Будьте добры поделиться исходником на си или паскале.
Да в общем-то кроме поиска в ширину или в глубину тут больше никаких знаний не надо. Стартуешь поиск с произвольной точки и помечаешь вершины. Как только пришел в уже посещенную вершину — стоп, это цикл (естественно по одному ребру дважды не ходишь).
no fate but what we make
Re[2]: Проверка графа на ацикличность.
От:
Аноним
Дата:
01.05.06 14:02
Оценка:
Здравствуйте, kl, Вы писали:
Трабл в том что понятия не имею даже как задавать граф. Слышал что копать надо в сторону матрицы смежности, что это?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, kl, Вы писали:
А>Трабл в том что понятия не имею даже как задавать граф. Слышал что копать надо в сторону матрицы смежности, что это?
Здравствуйте, kl, Вы писали:
kl>Да в общем-то кроме поиска в ширину или в глубину тут больше никаких знаний не надо. Стартуешь поиск с произвольной точки и помечаешь вершины. Как только пришел в уже посещенную вершину — стоп, это цикл (естественно по одному ребру дважды не ходишь).
В общем случае, это неправильное решение. Так лишь можно проверить, не проходит ли цикл через стартовую вершину. Для того, чтобы выполниить проверку на ацикличность, придется запускать обход из каждой вершины. Это уже слишком неэффективно -- O(VE).
Оптимальное решение состоит в использовании подходящей модицикации обхода в глубину. Критерием того, что граф ыциклический, является отсутствие при обходе обратных дуг, то есть дуг, идущих из текущей обрабатываемой вершины в "серую" вершину (обработка которой уже начата, но еще не завершена). Сложность O(V+E).
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, kl, Вы писали:
Mab>Оптимальное решение состоит в использовании подходящей модицикации обхода в глубину. Критерием того, что граф ыциклический, является отсутствие при обходе обратных дуг, то есть дуг, идущих из текущей обрабатываемой вершины в "серую" вершину (обработка которой уже начата, но еще не завершена). Сложность O(V+E).
Ну да, про поиск в ширину я прогнал. В глубину — это и имелось в виду.
Еще наверное можно рассуждать следующим образом:
Если граф без циклов, но у него должен быть минимум один лист.
Но это — недостаточное условие.
Но если этот лист оторвать со всеми ребрами, то граф должен остаться ацикличным. Соответственно продолжая отрывать листья мы либо получим пустой граф (тогда исходный граф был без циклов) либо получим граф без листьев. Значит исходный был с циклами.
Может это конечно и неправда, щас лень проверять.. но похоже на правду.
Здравствуйте, kl, Вы писали:
kl>Если граф без циклов, но у него должен быть минимум один лист.
Когда говорят про ориентированные графы, то термин 'лист' не используют. Лучше говорить 'сток' или (еще понятнее) 'вершина без исходящих дуг'.
kl>Может это конечно и неправда, щас лень проверять.. но похоже на правду.
Это правда, но не стоит изобретать велосипед. Реализовать такой алгоритм так, чтобы он укладывался за время O(V+E), конечно можно, но это чуть труднее, чем DFS.
Здравствуйте, Mab, Вы писали:
Mab>Когда говорят про ориентированные графы, то термин 'лист' не используют. Лучше говорить 'сток' или (еще понятнее) 'вершина без исходящих дуг'.
До меня только что дошло, что в вопросе ничего не было сказано про то, ориентированный граф или нет
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, Mab, Вы писали:
Mab>>Когда говорят про ориентированные графы, то термин 'лист' не используют. Лучше говорить 'сток' или (еще понятнее) 'вершина без исходящих дуг'. Mab>До меня только что дошло, что в вопросе ничего не было сказано про то, ориентированный граф или нет :)
Да, сорри, я часто коряво выражаюсь на-русском. Это я втупую перевел "leaf" что используется в литературе сплошь и рядом.
Здравствуйте, Аноним, Вы писали:
А>Господа, знание, а точнее не знание математики на должном уровне не позволяет помочь товарищу в написании программы "прооверка графа на ацикличность". Будьте добры поделиться исходником на си или паскале.
В принципе, можно адаптировать мою бакалаврскую, см. здесь. Написана на Delphi 7. Но там всё запутано и не эффективно (я очень торопился). Если будешь делать с ней будет очень трудно разобраться.
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, FDSC, Вы писали:
FDS>>В принципе, можно адаптировать мою бакалаврскую, см. <b>здесь</b>.
Там нужен файл uCircuitForm.pas, procedure TCircuitForm.TopSort. Если процедура генерит исключение граф содержит циклы
Re: Проверка графа на ацикличность.
От:
Аноним
Дата:
02.05.06 10:30
Оценка:
Здравствуйте, Аноним, Вы писали:
А>Господа, знание, а точнее не знание математики на должном уровне не позволяет помочь товарищу в написании программы "прооверка графа на ацикличность". Будьте добры поделиться исходником на си или паскале.
кусок кода для определения ацикличности графа:
Graph *G;
int depth,cnt,cntP;
std::vector<int> pre, post;
void DFS()//обход в глубину
{
cnt=0;
cntP=0;
count=0;
pre.clear();
post.clear();
for(int i=0;i<G->V();i++) //G->V() - возвращает кол-во вершин в графе
{
pre.push_back(-1);
post.push_back(-1);
}
for(int v=0;v<G->V();v++)
{
if(pre[v]==-1)
{
dfsR(v,v);
}
}
}
void dfsR(int v,int w)
{
pre[w] = cnt++;
depth++;
Graph::Iterator A(G,w); //итератор для вершины wint t;
if(A.beg(t))
{
do
{
if(pre[t]==-1) dfsR(w,t);
else if(post[t]==-1) //обратное ребро - значит граф не ациклический
{
; //что-то делаем с таким графом
}
}
while(A.next(t));
}
post[w]=cntP++;
depth--;
}
АТД графа и его итератора взяты из Фундаментальных алгоритмов Седжвика
Здравствуйте, Аноним, Вы писали:
А>Господа, знание, а точнее не знание математики на должном уровне не позволяет помочь товарищу в написании программы "прооверка графа на ацикличность". Будьте добры поделиться исходником на си или паскале.
В свое время делал так — определял матрицу смежности для графа и ее перемножал саму на себя N раз (N — размерность графа). Как только на главной диагонали появится единица — имеем циклы. Правда ... на матрицах 600 на 600 допустим дико тормозит
Re[2]: Проверка графа на ацикличность.
От:
Аноним
Дата:
03.05.06 11:41
Оценка:
Здравствуйте, elmal, Вы писали:
E>В свое время делал так — определял матрицу смежности для графа и ее перемножал саму на себя N раз (N — размерность графа). Как только на главной диагонали появится единица — имеем циклы. Правда ... на матрицах 600 на 600 допустим дико тормозит
Огромное спасибо. Осталось узнать что такое матрица смежности
Re[2]: Проверка графа на ацикличность.
От:
Аноним
Дата:
03.05.06 11:43
Оценка:
Здравствуйте, Аноним, Вы писали:
А>[ccode]
... А>АТД графа и его итератора взяты из Фундаментальных алгоритмов Седжвика
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, elmal, Вы писали:
E>>В свое время делал так — определял матрицу смежности для графа и ее перемножал саму на себя N раз (N — размерность графа). Как только на главной диагонали появится единица — имеем циклы. Правда ... на матрицах 600 на 600 допустим дико тормозит
А>Огромное спасибо. Осталось узнать что такое матрица смежности
Матрица, каждый элемент (i,j) содержит 1, если есть дуга из i в j и 0, если они не соединены. Ну ... и на самом то деле N раз саму на себя умножать не надо, можно в квадрат возводить гораздо меньшее количество раз (возможность для оптимизации есть ). Ну и умножение матрицы не обычное, а там вместо умножения логическое И будет.
Кстати — а есть ли способ быстрее это сделать? По моему итеративные алгоритмы будут все-же помедленнее.
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, elmal, Вы писали:
E>>>В свое время делал так — определял матрицу смежности для графа и ее перемножал саму на себя N раз (N — размерность графа). Как только на главной диагонали появится единица — имеем циклы. Правда ... на матрицах 600 на 600 допустим дико тормозит
А>>Огромное спасибо. Осталось узнать что такое матрица смежности E>Матрица, каждый элемент (i,j) содержит 1, если есть дуга из i в j и 0, если они не соединены. Ну ... и на самом то деле N раз саму на себя умножать не надо, можно в квадрат возводить гораздо меньшее количество раз (возможность для оптимизации есть ). Ну и умножение матрицы не обычное, а там вместо умножения логическое И будет.
E>Кстати — а есть ли способ быстрее это сделать? По моему итеративные алгоритмы будут все-же помедленнее.
А ты думаешь, почему столько смайлов? Это можно сделать обычным поиском в глубину. Сложность O(V+E). В общем-то выше уже это обсудили.
Здравствуйте, elmal, Вы писали:
E>и на самом то деле N раз саму на себя умножать не надо, можно в квадрат возводить гораздо меньшее количество раз (возможность для оптимизации есть
Открою секрет -- даже этого (log n возведений в квадрат) делать не нужно. Вместо этого нужно узнать, как работает алгоритм Флойда-Уоршалла, строящий ту же матрицу, но за O(n^3).
Ну и, конечно, для исходной задачи применять такие методы просто абсурдно.
Здравствуйте, Аноним, Вы писали:
