Поиск в глубину

@gr_8_zizu · Регистрация: 07.01.2011

Студворк — интернет-сервис помощи студентам

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

@solar_wind · 29.07.2011, 08:31

Так тебе алгоритм непонятен или ты ищешь готовые проги?

@Mayonez · 29.07.2011, 13:42

gr_8_zizu, вот

@gr_8_zizu · 30.07.2011, 00:36 **[ТС]**

Сообщение от vitaly1981

Так тебе алгоритм непонятен или ты ищешь готовые проги?

Алгоритм я прикрасно понял, но не особо представляю как его реализовать!

Добавлено через 2 минуты

Сообщение от Mayonez

gr_8_zizu, вот

Спасибо но я не работал с vector и мало знаю что он из себя представляет, так что пример не очень помог. PS я его уже смотрел.

@Deviaphan · 30.07.2011, 09:40

Поиск в бинарном дереве себе представить можешь?
Рекурсивная реализация такого поиска и будет примером поиска в глубину.

@voral · 30.07.2011, 10:23

Сообщение от gr_8_zizu

Алгоритм я прикрасно понял, но не особо представляю как его реализовать!

Интересно.... Я что то не понимаю, как так может быть.
Может попробовать пойти другим путем: напиши алгоритм, который ты понял, выясним что непонятного есть в его реализации.

@gr_8_zizu · 30.07.2011, 12:52 **[ТС]**

Сообщение от voral

Интересно.... Я что то не понимаю, как так может быть.
Может попробовать пойти другим путем: напиши алгоритм, который ты понял, выясним что непонятного есть в его реализации.

Я гворю не пойму как его реализовать, а ты пишишь реализуй. странный ты.

Jupiter · 30.07.2011, 12:55

Сообщение от gr_8_zizu

Спасибо но я не работал с vector и мало знаю что он из себя представляет, так что пример не очень помог. PS я его уже смотрел.

ну дык теперь посмотрите что такое vector

@voral · 30.07.2011, 13:05

Сообщение от gr_8_zizu

Я гворю не пойму как его реализовать, а ты пишишь реализуй. странный ты.

Ну так словами то можешь выразить? Сам алгоритм. Как ты его понимаешь?

Добавлено через 5 минут
Я к тому, что скорее всего и алгоритм то не правильно понимаешь. Для меня очень странно сочетание "прекрасно понимаю алгоритм" и "не представляю реализацию"

@Deviaphan · 30.07.2011, 13:11

Сообщение от 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 · 30.07.2011, 13:12 **[ТС]**

Сообщение от voral

Ну так словами то можешь выразить? Сам алгоритм. Как ты его понимаешь?

Добавлено через 5 минут
Я к тому, что скорее всего и алгоритм то не правильно понимаешь. Для меня очень странно сочетание "прекрасно понимаю алгоритм" и "не представляю реализацию"

Берется вершина, смотрятся из нее исходящие дуги, берется исходящая дуга и смотрятся ее потомки и так до выхода, а потом поднимаемся на одну вершину вверх с каждым шагом.

@voral · 30.07.2011, 13:22

Ладно упростим задачу.
Итак есть
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 · 30.07.2011, 13:23 **[ТС]**

voral, спасибо, буду разбираться, если будут вопросы, то напишу

@voral · 30.07.2011, 13:23

Я в 14 строке ошибся там return тольо для не NULL надо

@Deviaphan · 30.07.2011, 13:24

Сообщение от voral

в 14 строке ошибся

Да ты и структуры не правильно объявил, если придираться.

@gr_8_zizu · 30.07.2011, 13:25 **[ТС]**

Сообщение от voral

Я в 14 строке ошибся там return тольо для не NULL надо

оккей

@voral · 30.07.2011, 13:31

Сообщение от Deviaphan

Да ты и структуры не правильно объявил, если придираться.

Надеюсь речь только о точке с запятой?
Или мне пора сгорать ?

@Deviaphan · 30.07.2011, 13:47

Сообщение от voral

Надеюсь речь только о точке с запятой?

О двух точках с запятой.)))

@voral · 30.07.2011, 13:57

черт.. чувствую себя двоечником - где еще одна. Единственную которую осознал - не хватает после "}"

@Deviaphan · 30.07.2011, 14:03

Сообщение от voral

Единственную которую осознал - не хватает после "}"

Ахах! Ты просто в стиле Си пишешь и я функцию за вторую структуру принял.))) Одной ; не хватало только.)

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@gr_8_zizu 13 / 8 / 3 Регистрация: 07.01.2011 Сообщений: 149

	Поиск в глубину 29.07.2011, 00:48. Показов 7484. Ответов 19 Метки нет (Все метки) Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший. В общем киньте плз пример с детальным описанием. И желательно алгоритм с массивами а не с vector-ми. 0

@solar_wind 770 / 760 / 59 Регистрация: 06.07.2009 Сообщений: 3,021
	29.07.2011, 08:31
	Так тебе алгоритм непонятен или ты ищешь готовые проги? 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	29.07.2011, 13:42
	gr_8_zizu, вот 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	30.07.2011, 09:40
	Поиск в бинарном дереве себе представить можешь? Рекурсивная реализация такого поиска и будет примером поиска в глубину. 0

@gr_8_zizu 13 / 8 / 3 Регистрация: 07.01.2011 Сообщений: 149
	30.07.2011, 13:23 [ТС]
	voral, спасибо, буду разбираться, если будут вопросы, то напишу 0

@voral 3012 / 1449 / 262 Регистрация: 16.03.2008 Сообщений: 6,458 Записей в блоге: 2
	30.07.2011, 13:23
	Я в 14 строке ошибся там return тольо для не NULL надо 0

@voral 3012 / 1449 / 262 Регистрация: 16.03.2008 Сообщений: 6,458 Записей в блоге: 2
	30.07.2011, 13:57
	черт.. чувствую себя двоечником - где еще одна. Единственную которую осознал - не хватает после "}" 0