Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 31.12.2010, 11:10
Новичок

Отправить личное сообщение для tomsoier Посмотреть профиль Найти все сообщения от tomsoier
 
Регистрация: 31.12.2010
Сообщений: 2

Проверить, содержит ли данный граф цикл (С++)
Читал несколько алгоритмов, но проблема в том, что у меня граф задан списком ребер. Все ребра хранятся в массиве структур
Код:
struct edge
    {    
    int begin;
    int weight;
    int end;
    };
Красит вершины массив paint[i]. (2 - пройдена, 1 - окрашена, 0 - не покрашена).
у меня было вот так, но это неверно
Код:
    for ( p = 0; p < l; p++ )
        {
        if (((krus[i2].begin == krus[p].begin) || (krus[i2].begin == krus[p].end) || (krus[i2].end == krus[p].end)
            || (krus[i2].begin == krus[p].begin)))
            {
            if (paint[p] == 2)
                {
                s2[p]++;
                };

            if ((paint[p] == 0) || (paint[p] == 1))
                {
                paint[p] = 1;
                };
            };
        };
    paint[i2] = 2;
    };
Массив s2[i] считает сколько раз обработанная вершина встретилась при покраске смежных вершин. Но в таком случае не получается четко по s2[i] задать условия цикла.

Помогите пожалуйста, курсач горит, как и ,пожалуй, мой мозг.
  #2  
Старый 31.12.2010, 11:23
гocть

 
Сообщений: n/a

Цитата:
что у меня граф задан списком ребер
ну и что с того? преобразуй в списки смежности и запусти поиск в глубину

или воспользуйся структурой union-find, тогда можно и твои списки ребер ей сразу скормить без дополнительных действий (только для неорграфов)

Цитата:
Код:
                };
            };
        };
что это за ***** вы нам суете? кто вас программировать учил? не ставится здесь ;

Цитата:
Помогите пожалуйста, курсач горит, как и ,пожалуй, мой мозг.
чем помочь? ты ничего про сути своей проблемы не сказал. код у тебя непонятно что считает, экстрасенсы в отпуске
  #3  
Старый 31.12.2010, 11:26
гocть

 
Сообщений: n/a

сформулируй точно вопросы, на которые ты хочешь услышать ответ.

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

также нужно сказать - граф ориентированный или нет.
  #4  
Старый 31.12.2010, 11:43
Новичок

Отправить личное сообщение для tomsoier Посмотреть профиль Найти все сообщения от tomsoier
 
Регистрация: 31.12.2010
Сообщений: 2

граф неориентированный.Как реализовать dfs, если граф представлен массивом тех структур, которую я привел? Какие существуют способы проверить содержит ли граф цикл?
  #5  
Старый 31.12.2010, 11:58
гocть

 
Сообщений: n/a

Сообщение от tomsoier Посмотреть сообщение
Как реализовать dfs, если граф представлен массивом тех структур, которую я привел?
надо преобразовать их в списки смежности. это совсем несложно, просто один раз пройтись по входному массиву ребер, раскидать данные по спискам смежности.

Цитата:
Какие существуют способы проверить содержит ли граф цикл?
практически любой вид обхода обхода графа позволит это вам определить. в глубину/ширину самые простые. но для этого нужны будут списки смежности, как я уже сказал. или матрица смежности, если граф небольшой.

для неориентированных графов есть другой вариант - вместо обхода воспользоваться структурой данных union-find aka disjoint-sets structure aka "лес непересекающихся множеств". добавляете в нее ребра по одному, каждый раз перед этим проверяете, принадлежат ли оба конца ребра одному и тому же связному множеству - если да, то в графе цикл.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Гамильтонов цикл гость Графы 1 11.06.2010 07:06
Гамильтонов цикл в графе гость Графы 6 27.05.2009 00:50
Цикл гость Задачи 6 19.10.2008 00:58
Цикл гость Графы 1 17.06.2008 20:47
цикл fox Графы 1 09.12.2006 20:45