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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.94
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
29.07.2011, 00:48     Поиск в глубину #1
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший. В общем киньте плз пример с детальным описанием. И желательно алгоритм с массивами а не с vector-ми.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 00:48     Поиск в глубину
Посмотрите здесь:

C++ итеративный поиск в глубину
C++ поиск в глубину
C++ Не работает поиск в глубину (DFS)
C++ графы,поиск в глубину
графы. поиск в глубину C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
29.07.2011, 08:31     Поиск в глубину #2
Так тебе алгоритм непонятен или ты ищешь готовые проги?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.07.2011, 13:42     Поиск в глубину #3
gr_8_zizu, вот
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 00:36  [ТС]     Поиск в глубину #4
Цитата Сообщение от vitaly1981 Посмотреть сообщение
Так тебе алгоритм непонятен или ты ищешь готовые проги?
Алгоритм я прикрасно понял, но не особо представляю как его реализовать!

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

Добавлено через 5 минут
Я к тому, что скорее всего и алгоритм то не правильно понимаешь. Для меня очень странно сочетание "прекрасно понимаю алгоритм" и "не представляю реализацию"
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 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 );
}
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 13:12  [ТС]     Поиск в глубину #11
Цитата Сообщение от voral Посмотреть сообщение
Ну так словами то можешь выразить? Сам алгоритм. Как ты его понимаешь?

Добавлено через 5 минут
Я к тому, что скорее всего и алгоритм то не правильно понимаешь. Для меня очень странно сочетание "прекрасно понимаю алгоритм" и "не представляю реализацию"
Берется вершина, смотрятся из нее исходящие дуги, берется исходящая дуга и смотрятся ее потомки и так до выхода, а потом поднимаемся на одну вершину вверх с каждым шагом.
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
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 Посмотреть сообщение
Берется вершина, смотрятся из нее исходящие дуги, берется исходящая дуга и смотрятся ее потомки и так до выхода, а потом поднимаемся на одну вершину вверх с каждым шагом.
Может быть у нас разные представления о верхе. По мне так верх это самая верхняя корневая вершина. От нее и надо начинать поиск. Хотя это лишь вопрос реализации. Если каждая вершина имеет информацию о вершине более высокого уровня можно и так - но алгоритм усложнится
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 13:23  [ТС]     Поиск в глубину #13
voral, спасибо, буду разбираться, если будут вопросы, то напишу
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
30.07.2011, 13:23     Поиск в глубину #14
Я в 14 строке ошибся там return тольо для не NULL надо
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 13:24     Поиск в глубину #15
Цитата Сообщение от voral Посмотреть сообщение
в 14 строке ошибся
Да ты и структуры не правильно объявил, если придираться.
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
30.07.2011, 13:25  [ТС]     Поиск в глубину #16
Цитата Сообщение от voral Посмотреть сообщение
Я в 14 строке ошибся там return тольо для не NULL надо
оккей
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
30.07.2011, 13:31     Поиск в глубину #17
Цитата Сообщение от Deviaphan Посмотреть сообщение
Да ты и структуры не правильно объявил, если придираться.
Надеюсь речь только о точке с запятой?
Или мне пора сгорать ?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 13:47     Поиск в глубину #18
Цитата Сообщение от voral Посмотреть сообщение
Надеюсь речь только о точке с запятой?
О двух точках с запятой.)))
voral
345 / 325 / 46
Регистрация: 16.03.2008
Сообщений: 1,694
30.07.2011, 13:57     Поиск в глубину #19
черт.. чувствую себя двоечником - где еще одна. Единственную которую осознал - не хватает после "}"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2011, 14:03     Поиск в глубину
Еще ссылки по теме:

Поиск в глубину C++
C++ Матрица смежности графа - поиск в глубину
C++ Поиск в глубину

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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 14:03     Поиск в глубину #20
Цитата Сообщение от voral Посмотреть сообщение
Единственную которую осознал - не хватает после "}"
Ахах! Ты просто в стиле Си пишешь и я функцию за вторую структуру принял.))) Одной ; не хватало только.)
Yandex
Объявления
30.07.2011, 14:03     Поиск в глубину
Ответ Создать тему
Опции темы

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