Форум программистов, компьютерный форум CyberForum.ru

графы. поиск в глубину - C++

Восстановить пароль Регистрация
 
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 14:23     графы. поиск в глубину #1
Здраствуйте. Вот такая задача
N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i, j), 1≤ i < j ≤ N (шестеpня с номеpом i находится в зацеплении с шестеpней j). Можно ли повеpнуть шестеpню с номеpом 1?
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы максимальное число шестеpен. Указать номеpа убpанных шестеpен ( если такой набоp не один, то любой из них ) и количество шестеpен, пpишедших в движение.


помогите решить, хотя бы частично с поиском в глубину и соответственно проверкой вращения шестеренок(каждая шестеренка заставляет крутиться следующую в противоположную сторону, то есть при наличии нечетных циклов система встанет)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2013, 14:23     графы. поиск в глубину
Посмотрите здесь:

Поиск в глубину C++
C++ итеративный поиск в глубину
C++ поиск в глубину
Конечный автомат. Лабиринт (поиск в глубину) C++
C++ Не работает поиск в глубину (DFS)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
04.07.2013, 15:46     графы. поиск в глубину #2
на алголисте посмотрите алгоритмы.
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 16:11  [ТС]     графы. поиск в глубину #3
Kukurudza, там к сожалению только в чистом виде поиск в глубину, а мне нужно чтобы можно было дважды проходить по вершинам
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
04.07.2013, 19:05     графы. поиск в глубину #4
хорошая задачка. подумайте, когда можно ее повернуть, а когда нет. это забавно)
svk2140
-8 / 0 / 1
Регистрация: 04.07.2013
Сообщений: 254
04.07.2013, 19:07     графы. поиск в глубину #5
ух у меня щяс мозги перегреются)
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:08  [ТС]     графы. поиск в глубину #6
salam, я понимаю, что поворот идет либо когда нет цикла, либо когда он четен, то есть не будет того что нахлестнется одно направление на другое, у меня проблема с тем как просмотреть все элементы и в цикле не зациклится

Добавлено через 1 минуту
svk2140, а у меня второй день так( хотя вроде как продвигается но все равно ничего не работае
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
04.07.2013, 19:22     графы. поиск в глубину #7
Цитата Сообщение от Рехеана Посмотреть сообщение
salam, я понимаю, что поворот идет либо когда нет цикла, либо когда он четен, то есть не будет того что нахлестнется одно направление на другое, у меня проблема с тем как просмотреть все элементы и в цикле не зациклится
да, я думаю, именно это условие и нужно поставить. просто напишите правильно дфс. можете искать цикл просто так. если найдется, посмотреть, четный или нет. тут просто реализация грамотная нужна.
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:26  [ТС]     графы. поиск в глубину #8
salam, вот с ней и проблема, не могу написать так чтобы в цикл проходило и чтобы это было так как это требует преподаватель, практика в универе идет, он совсем объяснять не хочет дал книжку там не очень понятно... а вы не могли бы помочь?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
04.07.2013, 19:27     графы. поиск в глубину #9
Цитата Сообщение от Рехеана Посмотреть сообщение
и чтобы это было так как это требует преподаватель
я ведь наверняка знаю, чего он требует...
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:33  [ТС]     графы. поиск в глубину #10
Прошу прощения торможу.
http://**********/files/xloyc7cra
вот по этой методичке там алгоритм есть, а реализовано на си шарп.
и как бы там не учитываются циклы.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
04.07.2013, 20:00     графы. поиск в глубину #11
не люблю я очень эти методички... прошу прощения. давайте подумаем. цикл можно найти так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int graph[SIZE][SIZE]; // матрица смежности
int color[SIZE];            // color[i] может принимать одно из трех значений {0, 1, 2}
                                 // 0 - вершина не была посещена,
                                 // 1 - мы зашли в нее, но еще не вышли,
                                 // 2 - мы уже вышли из этой вершины.
void dfs(int v) {
   color[v] = 1;                  // мы зашли в вершину v
   for(int i=0; i < SIZE; i++)
      if(i != v && graph[v][i] == true)
         if(color[i] == 1) {      // мы нашли цикл, так как пытаемся пойти из вершины 
                                      // с цветом 1 в вершину с цветом 1, то есть 
         }                           // в вершину, из которой еще не вышли
         else if(color[i] == 0)
                  dfs(i);
   color[v] = 2;
}
дальше можете делать с этим циклом, что угодно.

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

Добавлено через 2 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int graph[SIZE][SIZE]; // матрица смежности
int par[SIZE];               // массив предков 
int color[SIZE];            // color[i] может принимать одно из трех значений {0, 1, 2}
                                 // 0 - вершина не была посещена,
                                 // 1 - мы зашли в нее, но еще не вышли,
                                 // 2 - мы уже вышли из этой вершины.
void dfs(int v) {
   color[v] = 1;                  // мы зашли в вершину v
   for(int i=0; i < SIZE; i++)
      if(i != v && graph[v][i] == true)
         if(color[i] == 1) {      // мы нашли цикл, так как пытаемся пойти из вершины 
                                      // с цветом 1 в вершину с цветом 1, то есть 
         }                           // в вершину, из которой еще не вышли
         else if(color[i] == 0) {
                  par[i] = v;   // мы называем вершину v предком вершины i, 
                                   // так как обход в глубину попал в i именно из v
                  dfs(i);
         }
   color[v] = 2;
}
Добавлено через 1 минуту
надеюсь, вам это все поможет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2013, 20:08     графы. поиск в глубину
Еще ссылки по теме:

C++ графы,поиск в глубину
Поиск в глубину C++
C++ Поиск в глубину

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 20:08  [ТС]     графы. поиск в глубину #12
salam, спасибо
Yandex
Объявления
04.07.2013, 20:08     графы. поиск в глубину
Ответ Создать тему
Опции темы

Текущее время: 20:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru