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

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

Форум программистов > Алгоритмы > Алгоритм поиска петель в графе

Автор: GLX 12.7.2011, 02:23

Откройте файл Notepad'ом++. Меня интересует будет ли работать этот алгоритм. Подскажите, пожалуйста.

Автор: Silent 12.7.2011, 08:56

многа букафф )))
петельки находятся через поиск в глубину - если на текущем шаге смежная вершина уже помечена как посещенная, то вот она, петелька. Примерный код (не компилил, не тестил, только идея):

Код


const int N = 10;    //количество вершин
bool a[N,N];        //матрица смежности
bool ex[N];        //признак посещенности вершин
int q[N];

void init()
{
    memset(ex,0,sizeof(ex));
    // + формирование матрицы смежности
}

void solve(int x, int level)
{
    for (int i = 0; i < N; i++)
        if (a[x,i])
            if (ex[i] == 0)
            {
                ex[i] = false
                q[level] = i;
                solve(i,level+1);
                ex[i] = true;
            }
            else    //петелька нашлась
            {
                for (int j = level-1; q[j] != i; j--)
                    cout << q[j] << " ";
                cout << i << endl;
            }
}

int main()
{
    init();
    for (int i = 0; i < N; i++)
    {
        q[0] = i;
        ex[i] = false;
        solve(i, 1);
        ex[i] = true;
    }
    return 0;
}

Автор: Earnest 12.7.2011, 09:09

Проблема в том, что поиск в глубину находит ВСЕ циклы в графе. Если задача в этом, то ок (код особо не смотрела, но проблем там быть не должно).
Но если нужны только минимальный циклы (например, соответствующие фасетам планарного графа)... даже не знаю, есть ли какой-то общий алгоритм (для произвольного графа), кроме анализа полученных поиском в глубину циклов на "минимальность".

Автор: Silent 12.7.2011, 12:35

А какая у вас задача? получить все циклы минимальной длины? или получить грани планарного графа? если второе - то вам http://e-maxx.ru/algo/facets, а если первое - то можно пойти и другим путем, не в глубину, а через генерацию возможных путей "в ширину"

Автор: GLX 12.7.2011, 16:09

По условию задачи нужно найти все петли.

Автор: Peter 18.7.2011, 20:06

Петля - это дуга, имеющая начало и конец в одной и той же вершине.

Добавлено через 3 минуты и 37 секунд
Какие там посещенные или непосещенные вершины?

Добавлено через 4 минуты и 20 секунд
В матрице смежности смотрим диагональные элементы - и всё! Для других представлений графа тоже ничего сложного.

Автор: Earnest 19.7.2011, 07:47

Автор так описал задачу, что все подумали про поиск циклов. И до сих пор мне представляется маловероятным, чтобы автор поднял проблему обнаружения именно таких замкнутых дуг-петель. Действительно, чего их искать-то.