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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
#1

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

04.07.2013, 14:23. Просмотров 1052. Ответов 11
Метки нет (Все метки)

Здраствуйте. Вот такая задача
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++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once

Поиск в глубину - C++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...

поиск в глубину - C++
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается. vector&lt;char&gt; used; int...

Поиск в глубину - C++
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? Пробовал сделать так const...

Поиск в глубину - C++
&quot;В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки. Кровати в комнате стоят очень плотно. Чтобы...

Поиск в глубину - C++
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
04.07.2013, 19:05     графы. поиск в глубину #4
хорошая задачка. подумайте, когда можно ее повернуть, а когда нет. это забавно)
svk2140
-8 / 0 / 1
Регистрация: 04.07.2013
Сообщений: 262
04.07.2013, 19:07     графы. поиск в глубину #5
ух у меня щяс мозги перегреются)
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:08  [ТС]     графы. поиск в глубину #6
salam, я понимаю, что поворот идет либо когда нет цикла, либо когда он четен, то есть не будет того что нахлестнется одно направление на другое, у меня проблема с тем как просмотреть все элементы и в цикле не зациклится

Добавлено через 1 минуту
svk2140, а у меня второй день так( хотя вроде как продвигается но все равно ничего не работае
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
04.07.2013, 19:22     графы. поиск в глубину #7
Цитата Сообщение от Рехеана Посмотреть сообщение
salam, я понимаю, что поворот идет либо когда нет цикла, либо когда он четен, то есть не будет того что нахлестнется одно направление на другое, у меня проблема с тем как просмотреть все элементы и в цикле не зациклится
да, я думаю, именно это условие и нужно поставить. просто напишите правильно дфс. можете искать цикл просто так. если найдется, посмотреть, четный или нет. тут просто реализация грамотная нужна.
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:26  [ТС]     графы. поиск в глубину #8
salam, вот с ней и проблема, не могу написать так чтобы в цикл проходило и чтобы это было так как это требует преподаватель, практика в универе идет, он совсем объяснять не хочет дал книжку там не очень понятно... а вы не могли бы помочь?
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
04.07.2013, 19:27     графы. поиск в глубину #9
Цитата Сообщение от Рехеана Посмотреть сообщение
и чтобы это было так как это требует преподаватель
я ведь наверняка знаю, чего он требует...
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:33  [ТС]     графы. поиск в глубину #10
Прошу прощения торможу.
http://**********/files/xloyc7cra
вот по этой методичке там алгоритм есть, а реализовано на си шарп.
и как бы там не учитываются циклы.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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++
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то рекурсивный и нерекурсивный поиски дадут одинаковые...

Не работает поиск в глубину (DFS) - C++
Вот код (заполнен для ориентированного графа 0 2 | + +/ 1--+3--+4 | + 5--+6 |

Конечный автомат. Лабиринт (поиск в глубину) - C++
Пусть лабиринт задан двумерным массивом bool, индексы ячеек соответствуют их координатам. Ячейка содержит true, если она проходима, и...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru