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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.94
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
#1

Поиск в глубину - C++

29.07.2011, 00:48. Просмотров 5086. Ответов 19
Метки нет (Все метки)

Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший. В общем киньте плз пример с детальным описанием. И желательно алгоритм с массивами а не с vector-ми.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 00:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск в глубину (C++):

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

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

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

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

графы. поиск в глубину - C++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

графы,поиск в глубину - C++
очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину. Есть готовый алгоритм поиска,из...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
solar_wind
756 / 747 / 42
Регистрация: 06.07.2009
Сообщений: 2,969
Завершенные тесты: 1
29.07.2011, 08:31 #2
Так тебе алгоритм непонятен или ты ищешь готовые проги?
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
29.07.2011, 13:42 #3
gr_8_zizu, вот
0
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 00:36  [ТС] #4
Цитата Сообщение от vitaly1981 Посмотреть сообщение
Так тебе алгоритм непонятен или ты ищешь готовые проги?
Алгоритм я прикрасно понял, но не особо представляю как его реализовать!

Добавлено через 2 минуты
Цитата Сообщение от Mayonez Посмотреть сообщение
gr_8_zizu, вот
Спасибо но я не работал с vector и мало знаю что он из себя представляет, так что пример не очень помог. PS я его уже смотрел.
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 09:40 #5
Поиск в бинарном дереве себе представить можешь?
Рекурсивная реализация такого поиска и будет примером поиска в глубину.
0
voral
452 / 433 / 66
Регистрация: 16.03.2008
Сообщений: 2,104
30.07.2011, 10:23 #6
Цитата Сообщение от gr_8_zizu Посмотреть сообщение
Алгоритм я прикрасно понял, но не особо представляю как его реализовать!
Интересно.... Я что то не понимаю, как так может быть.
Может попробовать пойти другим путем: напиши алгоритм, который ты понял, выясним что непонятного есть в его реализации.
0
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 12:52  [ТС] #7
Цитата Сообщение от voral Посмотреть сообщение
Интересно.... Я что то не понимаю, как так может быть.
Может попробовать пойти другим путем: напиши алгоритм, который ты понял, выясним что непонятного есть в его реализации.
Я гворю не пойму как его реализовать, а ты пишишь реализуй. странный ты.
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
30.07.2011, 12:55 #8
Цитата Сообщение от gr_8_zizu Посмотреть сообщение
Спасибо но я не работал с vector и мало знаю что он из себя представляет, так что пример не очень помог. PS я его уже смотрел.
ну дык теперь посмотрите что такое vector
0
voral
452 / 433 / 66
Регистрация: 16.03.2008
Сообщений: 2,104
30.07.2011, 13:05 #9
Цитата Сообщение от gr_8_zizu Посмотреть сообщение
Я гворю не пойму как его реализовать, а ты пишишь реализуй. странный ты.
Ну так словами то можешь выразить? Сам алгоритм. Как ты его понимаешь?

Добавлено через 5 минут
Я к тому, что скорее всего и алгоритм то не правильно понимаешь. Для меня очень странно сочетание "прекрасно понимаю алгоритм" и "не представляю реализацию"
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 13:11 #10
Цитата Сообщение от gr_8_zizu Посмотреть сообщение
Я гворю не пойму как его реализовать
На примере дерева.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//дерево
struct Node { Node*left, *right; int value; };
 
Node * Find( Node * tree, int value )
{
    if( !tree )
       return NULL;
 
    if( tree->value == value )
         return tree;
 
    Node * node = Find( tree->left, value );
    if( node )
        return node;
 
    return Find( tree->right, value );
}
 
//main
{
     // формирование дерева
     Node * tree = ...
     ...
 
     Node * node = Find( tree, 123 );
}
2
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 13:12  [ТС] #11
Цитата Сообщение от voral Посмотреть сообщение
Ну так словами то можешь выразить? Сам алгоритм. Как ты его понимаешь?

Добавлено через 5 минут
Я к тому, что скорее всего и алгоритм то не правильно понимаешь. Для меня очень странно сочетание "прекрасно понимаю алгоритм" и "не представляю реализацию"
Берется вершина, смотрятся из нее исходящие дуги, берется исходящая дуга и смотрятся ее потомки и так до выхода, а потом поднимаемся на одну вершину вверх с каждым шагом.
1
voral
452 / 433 / 66
Регистрация: 16.03.2008
Сообщений: 2,104
30.07.2011, 13:22 #12
Ладно упростим задачу.
Итак есть
http://ru.wikipedia.org/wiki/Поиск_в_глубину
Гласит:
Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.
Т.е. мы для каждой вершины должны выполнить следующие действия
1. Проверить не удовлетворяет ли она заданным условиям
2. Рекурсивно выполнить для каждой из связанных вершин эту же самую процедуру (т.е. п.п. 1 и 2)
Т.е. имеем связанный список структур примерно такого вида
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Mytest 
{
    int val;
    struct Mytest *child1;
......
    struct Mytest *child2;
}
// поиск
struct Mytest *getNode(int searchValue, struct Mytest *current)
{
    if (current->value==searchValue) return current;
   <цикл_обхода child1 - childN>
       return getNode(searchValue, child_i);
   <конец_цикл_обхода child1 - childN>
   return NULL;
}
Если какието сложные связи. т.е. к конкретной вершине от корня можно добраться разными путями то тут еще нужно условий прикрутить

Добавлено через 2 минуты
Да естественно
C
1
struct Mytest *child1; ...... struct Mytest *childN;
вместо этого в зависимости от задачи может быть и динамический массив.

Добавлено через 2 минуты
Цитата Сообщение от gr_8_zizu Посмотреть сообщение
Берется вершина, смотрятся из нее исходящие дуги, берется исходящая дуга и смотрятся ее потомки и так до выхода, а потом поднимаемся на одну вершину вверх с каждым шагом.
Может быть у нас разные представления о верхе. По мне так верх это самая верхняя корневая вершина. От нее и надо начинать поиск. Хотя это лишь вопрос реализации. Если каждая вершина имеет информацию о вершине более высокого уровня можно и так - но алгоритм усложнится
1
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 13:23  [ТС] #13
voral, спасибо, буду разбираться, если будут вопросы, то напишу
0
voral
452 / 433 / 66
Регистрация: 16.03.2008
Сообщений: 2,104
30.07.2011, 13:23 #14
Я в 14 строке ошибся там return тольо для не NULL надо
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 13:24 #15
Цитата Сообщение от voral Посмотреть сообщение
в 14 строке ошибся
Да ты и структуры не правильно объявил, если придираться.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2011, 13:24
Привет! Вот еще темы с ответами:

Рекурсивный поиск в глубину - 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++
Здравствуйте! Вопрос связан с поиском в графе. Меня интересуют идеи решения или ссылка на литературу. Пожалуйста, подскажите... ...

Рекурсивный и нерекурсивный поиск в глубину - C++
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то рекурсивный и нерекурсивный поиски дадут одинаковые...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.07.2011, 13:24
Ответ Создать тему
Опции темы

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