VPF::Алгоритм поиска петель в графе

GLX

Дата 12.7.2011, 02:23 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 30.3.2011

Репутация: нет
Всего: нет

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

Присоединённый файл ( Кол-во скачиваний: 26 )

____.txt 7,27 Kb

Silent

Дата 12.7.2011, 08:56 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

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

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183

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

--------------------

...

Silent

Дата 12.7.2011, 12:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

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

GLX

Дата 12.7.2011, 16:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 30.3.2011

Репутация: нет
Всего: нет

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

Peter

Дата 18.7.2011, 20:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 771
Регистрация: 28.7.2003
Где: Ставрополь

Репутация: нет
Всего: 1

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

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

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

--------------------

всё, что делаете, делайте от души, как для Господа (Послание апостола Павла колоссянам, 3:23).

Earnest

Дата 19.7.2011, 07:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183

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

--------------------

...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »