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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ <> в С++ http://www.cyberforum.ru/cpp-beginners/thread337106.html
Прошу прощения за нубский вопрос. Как в С++ выглядит логическая операция из Pascal <>?
C++ Как работает "шаг цикла" в цикле for? Всем привет! Я в с++ новичек !! кому не сложно обьясните как работает "шаг цикла" в цикле for For(счетчик = значение; счетчик < значение; шаг цикла) я понял что это значение, на которое будет... http://www.cyberforum.ru/cpp-beginners/thread337049.html
C++ дружественные функции
Всем привет!!! Есть код: #include<iostream.h> #include<conio.h> #include<string.h> enum Shape{prizm,parallelepiped,cube,pyramid,cone,cylinder}; static char*...
Как заставить машину ждать перед очередным выполнением цикла? C++
есть код#include <stdio.h> #include <iostream> #include <conio.h> using namespace std; int main(int argc, char *argv) { int x = 9; while(x != 0){ x = x-1;
C++ Перебор http://www.cyberforum.ru/cpp-beginners/thread337005.html
Ребят, помогите решить две задачи. Занимаюсь программированием уже 6 лет. Но тут в ступор встал. 1 задача: есть массив. из него нужно получить все возможные варианты строк заданной длинной(пусть...
C++ Многопоточность Как создать 2 функции. Главную и второстепенную. Чтобы в определенный момент из главной в второстепенную было передано число и дальше 2 функции продолжили свою работу одновременно? подробнее

Показать сообщение отдельно
voral
455 / 436 / 68
Регистрация: 16.03.2008
Сообщений: 2,130
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 Посмотреть сообщение
Берется вершина, смотрятся из нее исходящие дуги, берется исходящая дуга и смотрятся ее потомки и так до выхода, а потом поднимаемся на одну вершину вверх с каждым шагом.
Может быть у нас разные представления о верхе. По мне так верх это самая верхняя корневая вершина. От нее и надо начинать поиск. Хотя это лишь вопрос реализации. Если каждая вершина имеет информацию о вершине более высокого уровня можно и так - но алгоритм усложнится
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru