Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> алгоритмы на графах, вывести все циклы на экран 
V
    Опции темы
fuckingniger
Дата 6.3.2011, 22:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: 1
Задан неориентированный граф. Необходимо вывести все циклы.Не поможете?

Можно исключить лишние вершины - только не уверен чтов этом есть смысл.

Это сообщение отредактировал(а) fuckingniger - 6.3.2011, 22:47
PM MAIL   Вверх
alexvs11
Дата 6.3.2011, 22:52 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


hell is here
**


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

Репутация: 6
Всего: 10
первое, что приходит в голову - рекурсивный обход, по-ходу ведем журнал вершин, если какаята вершина повторяется - значит есть цикл
вообщеж наверняка тьма алгоритмов для этого есть

Добавлено через 2 минуты
это напоминает поиск решения в лабиринте в своей мере тоже граф - перебираем все варианты исключая циклы
PM MAIL   Вверх
fuckingniger
Дата 6.3.2011, 22:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: 1
Цитата(alexvs11 @  6.3.2011,  22:52 Найти цитируемый пост)
первое, что приходит в голову - рекурсивный обход, по-ходу ведем журнал вершин, если какаята вершина повторяется - значит есть цикл


Если речь идёт о прямом(обратном, симметричном), то он вроде как для деревьев (орграф)
Цитата(alexvs11 @  6.3.2011,  22:52 Найти цитируемый пост)
вообщеж наверняка тьма алгоритмов для этого есть


ну да )  наверняка... может хоть 1 скажете?
PM MAIL   Вверх
fuckingniger
Дата 7.3.2011, 01:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: 1
Цитата(alexvs11 @  6.3.2011,  22:52 Найти цитируемый пост)
вообщеж наверняка тьма алгоритмов для этого есть

 smile 
PM MAIL   Вверх
alexvs11
Дата 7.3.2011, 02:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


hell is here
**


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

Репутация: 6
Всего: 10
ну это и правда несложно

Код

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iterator>
#include <list>

const size_t N = 7;

typedef std::vector<bool> VBool;
typedef std::vector<VBool> Matrix; 
typedef std::list<size_t> Path;

void recurs( Matrix& m, const size_t state, Path& path )
{
  //find all states
  VBool::iterator it, end;
  it = m[state].begin();
  end = m[state].end();
  //std::cout << "recurs: " << state << std::endl;
  //std::copy( it, end, std::ostream_iterator<bool>( std::cout, " " ) ); std::cout << std::endl;
  while( (it = std::find( it, end, true )) != end )
  {
      //check for cicle
      size_t next_state = it - m[state].begin();
      //std::cout << "next_state: " << next_state << std::endl;
      Path::iterator _it = std::find( path.begin(), path.end(), next_state );
      if( _it != path.end() )
        {
          std::copy( _it, path.end(), std::ostream_iterator<size_t>( std::cout, " " ) );
          std::cout << state << " " << next_state << std::endl;
        }
      else
        {
          path.push_back( state );
          recurs( m, next_state, path );
          path.pop_back();
        }
      ++it;
    }
}

int main()
{
  /*
    0->2<->3
    |  | ^ 
    v  v/ 
    1  5
    | / ^
    vv   \ 
    4 -> 6

 0123456
0-xx----
1----x--
2---x-x-
3--x--x-
4------x
5---xx--
6-----x-
   */
  Matrix vTable( N );
  for( size_t i=0;i<vTable.size();++i )
    {
      vTable[i].resize( N );
    }
  vTable[0][1] = true; vTable[0][2] = true;
  vTable[1][4] = true;
  vTable[2][3] = true; vTable[2][5] = true;
  vTable[3][2] = true; vTable[3][5] = true;
  vTable[4][6] = true;
  vTable[5][3] = true; vTable[5][4] = true; 
  vTable[6][5] = true; 
  
  Path path;
  std::cout << "start" << std::endl;
  recurs( vTable, 0, path );

}


Код

start
3 2 3
5 3 2 5
5 3 5
4 6 5 4
2 3 2
3 5 3
5 4 6 5
2 5 3 2
5 3 5
5 4 6 5
(END) 
PM MAIL   Вверх
alexvs11
Дата 7.3.2011, 03:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


hell is here
**


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

Репутация: 6
Всего: 10
как видите не только для деревьев
PM MAIL   Вверх
fuckingniger
Дата 7.3.2011, 13:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: 1
как много стандартных функций.Надо изучить некоторые такие как find

а можете, если не сложно в двух словах описать алгоритм?

Программа работает отлично!
PM MAIL   Вверх
alexvs11
Дата 7.3.2011, 15:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


hell is here
**


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

Репутация: 6
Всего: 10
все очень просто

Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
  Matrix vTable( N );

матрица смежности (вроде так)
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
  Path path;

журнал - путь, в него будем добавлять уже посещенные вершины
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
  recurs( vTable, 0, path );

вызываем процедуру с начальным состоянием пустым журналом
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
  while( (it = std::find( it, end, true )) != end )

ищем в матрице смежности состояния в которые можем перейти из текущего, вообщем возможные переходы
далее проделываем действия для каждого возможного перехода
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
      Path::iterator _it = std::find( path.begin(), path.end(), next_state );

проверяем бывали ли мы уже в этом состоянии, в которое хотим перейти, если бывали - имеем цикл
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
      if( _it != path.end() )

если в этом состоянии еще не были то
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
          path.push_back( state );
          recurs( m, next_state, path );
          path.pop_back();

добавляем состояние в журнал, берем его за начальное и продолжаем рекурсию
после выхода из рекурсии удаляем состояние из журнала, чтобы продолжить движение по другому пути
можно иметь свой журнал для каждого пути, но это более накладно
Цитата(alexvs11 @  7.3.2011,  02:59 Найти цитируемый пост)
      ++it;

после выхода из рекурсии выбираем другой возможный путь
PM MAIL   Вверх
fuckingniger
Дата 8.3.2011, 17:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: 1
Спасибо.Пара часов втыкания и стало ясно)) сложная штука эта рекурсия.

Добавлено через 2 минуты и 6 секунд
это как, я понимаю, аналог поиска вглубину?
PM MAIL   Вверх
alexvs11
Дата 8.3.2011, 18:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


hell is here
**


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

Репутация: 6
Всего: 10
Цитата(fuckingniger @  8.3.2011,  17:58 Найти цитируемый пост)
это как, я понимаю, аналог поиска вглубину?

похоже это он и есть
PM MAIL   Вверх
fuckingniger
Дата 8.3.2011, 21:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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


# include <iostream>
# include <string>
using namespace std;
const int  N = 5 ;
bool matrix[N][N];
void filling_mas(int str , int stlb);
void init(int k);
int search(int n1, int n2 , int q );
void deep(int );
string is;
string all;
string check;
int main()
{
    init(N);
    matrix[1][0]=true; matrix[0][1]=true;
    matrix[2][1]=true;matrix[1][2]=true;
    matrix[0][2]=true; matrix[2][0]=true; matrix[3][2]=true;matrix[2][3]=true;
    matrix[4][3]=true;matrix[3][4]=true;
    matrix[2][4]=true;matrix[4][2]=true;
    deep(0);
    cout <<all;
    return 0;
}

void filling_mas(int str , int stlb)
{
    matrix[str][stlb]=false;
    if (str==0 && stlb==0)
        return;
    else
    {
        if(stlb==0)
            filling_mas(str-1,N-1);
        else
            filling_mas(str,stlb-1);
    }
}

void init(int k)
{
    filling_mas(k-1,k-1);
}


int search(int n1, int n2 , int q )
{
    if(n1>n2)
        return -1;
    else
        if(matrix[n1][q]==true)
            return n1;
        else
            search(n1+1,n2,q);
}

void deep(int q)
{
    int index;
    if(is.find(q+'0')==-1 )
    {
        is.push_back(q+'0');
        if(all.find(q+'0')==-1 )
            all.push_back(q+'0');
        index=0;
    
        while( (index = search(index,N-1,q)) != -1 )
            deep(index++);
        is.pop_back();
    }
    else
        if(is.substr(is.find(q+'0')).length()>2)
            cout << "cicle " <<is.substr(is.find(q+'0')) <<q<<endl ;
}



вот, что я написал.Ну собственно отдичаетсятолько тем, что выводит циклы длиннее 3 элементов.
вопрос такой. при графе (все связи в обе стороны)
user posted image

он выводит:


Код

cicle 0120
cicle 2342
cicle 2432
cicle 0210
cicle 2342
cicle 2432
01234Для продолжения нажмите любую клавишу . . .


как бы избежать повторения без прямого сравнения(или без использования цикла)???


Это сообщение отредактировал(а) fuckingniger - 8.3.2011, 21:23
PM MAIL   Вверх
alexvs11
Дата 8.3.2011, 21:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


hell is here
**


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

Репутация: 6
Всего: 10
да заметил тоже такое
это происходит изза того что пути 
0-1-2-3-4-2 и
0-2-3-4-2
разные, но циклы одни
надо подумать будет

Это сообщение отредактировал(а) alexvs11 - 8.3.2011, 21:24
PM MAIL   Вверх
fuckingniger
Дата 8.3.2011, 21:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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


это я тож понял) .просто в задании прям так и сказано(избегая повторений)
циклы кстати тоже нельзя использовать.так что думаю как последний while убрать

Это сообщение отредактировал(а) fuckingniger - 8.3.2011, 21:34
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0524 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.