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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.62
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
#1

Организовать обход в глубину - C++

16.03.2013, 22:53. Просмотров 3961. Ответов 8
Метки нет (Все метки)

Искал код, не смог найти подходящий.
Цель следующая - первым обходом ищем все шарниры, а вторым нужно найти для каждого шарнира, на сколько компонент связности дробит граф этот шарнир и сколько в каждой компоненте останется вершин. Было бы вообще великолепно, если бы было возможно реализовать это одним обходом.
Поделитесь, пожалуйста, кодом по этому вопросу, или идеями, если есть
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.03.2013, 22:53     Организовать обход в глубину
Посмотрите здесь:

Обход графа в глубину - C++
Как сделать обход этого графа в глубину ?

Обход графа в глубину - C++
Покажите кто-нибудь как работает "обход графа" в графе в консоле А именно вывод глубины графа,сколько ребер обошел ,где был уже... ...

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

Многопоточный обход графа в глубину - C++
Доброго времени суток. Подскажите многопоточный алгоритм обхода графа в глубину (нужно распараллелить алгоритм поиска компонент связности)....

Хитрый обход дерева в глубину - C++
По условию необходимо обойти дерево так чтобы найти путь max длины не имеющий кратных вершин, приэтом советуют пользоваться алгоритмом с...

Обход неориентированного графа в глубину - C++
#include <iostream> #include <fstream> #include <vector> #include <conio.h> #include <locale.h> using namespace std; int...

Обход вершин графа в глубину стеком - C++
Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в глубину. Есть код.. Но он не совсем правильно...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.03.2013, 00:08     Организовать обход в глубину #2
Это довольно непростая задача в плане алгоритма.
Для меня сложнее всего было понять сам алгоритм поиска точек сочленения - для этого я долго и упорно рисовал различные графы и строил для них деревья поиска в глубину(сам алгоритм заключается как раз в анализе такого дерева). Вся нужная вам информация вытаскивается также из дерева обхода в глубину. То есть фактически эта задача решается за один обход в глубину.
Тут есть немного теории + реализация, но чтобы выжать из дерева dfs еще больше, нужно осознать алгоритм самостоятельно.
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.03.2013, 00:41  [ТС]     Организовать обход в глубину #3
diagon, алгоритм поиска в глубину и его применение на точках сочленения осознан, вопрос в поиске распавшихся компонент и числа вершин в них. Я сейчас ищу решение, просто возможно кто-то уже сталкивался с таким и имеет идеи или готовый код.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.03.2013, 00:56     Организовать обход в глубину #4
Цитата Сообщение от Veyron Посмотреть сообщение
вопрос в поиске распавшихся компонент и числа вершин в них
Да там вроде как не очень сложно.
Распавшиеся компоненты при удалении из графа какой-либо точки сочленения - это ее сыновья + весь оставшийся граф (то есть количество_вершин - количество_сыновей - 1).
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.03.2013, 01:03  [ТС]     Организовать обход в глубину #5
Цитата Сообщение от diagon Посмотреть сообщение
это ее сыновья
Если имелись в виду сыновья в дереве обхода, то да. Но, опять же, некоторые сыновья шарнира могут лежать в одной компоненте связности. Плюс ко всему более важен вопрос - сколько останется вершин в КАЖДОЙ из получившихся компонент связности.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.03.2013, 01:27     Организовать обход в глубину #6
Цитата Сообщение от Veyron Посмотреть сообщение
Но, опять же, некоторые сыновья шарнира могут лежать в одной компоненте связности.
Неа. Вот представьте себе дерево обхода в глубину графа с точкой сочленения.

Код
                   предок
                      |
                      |
              точка сочленения
                /     |    \
               /      |     \
              /       |      \
          1 сын     2 сын   3 сын
Очевидно, что после удаления точки сочленения ее сыновья окажутся в разных компонентах связности.
Ну, там правда был какой-то частный случай...

сколько останется вершин в КАЖДОЙ из получившихся компонент связности
Это еще проще считается - допустим, вы находитесь в какой-то вершине, у которой есть сыновья, и вы знаете ответ для этих сыновей. Тогда вам нужно просто сложить ответы для каждого из сыновей (ну и про самих сыновей не забыть).
То есть пускаете dfs из каждого сына, и этот же dfs считает вам ответ. И так для каждой вершины.
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.03.2013, 01:32  [ТС]     Организовать обход в глубину #7
Цитата Сообщение от diagon Посмотреть сообщение
предок
* * * * * * * * * * * |
* * * * * * * * * * * |
* * * * * * * точка сочленения
* * * * * * * * / * * | * *\
* * * * * * * */ * * *| * * \
* * * * * * * / * * * | * * *\
* * * * * 1 сын * * 2 сын * 3 сын
Соедините первого сына со вторым, третьего с предком - поймете, что заблуждаетесь.


Цитата Сообщение от diagon Посмотреть сообщение
Это еще проще считается - допустим, вы находитесь в какой-то вершине, у которой есть сыновья, и вы знаете ответ для этих сыновей. Тогда вам нужно просто сложить ответы для каждого из сыновей (ну и про самих сыновей не забыть).
То есть пускаете dfs из каждого сына, и этот же dfs считает вам ответ. И так для каждой вершины.
Изначально вопрос стоял как это реализовать в ОДНОМ или в ДВУХ DFS, а не запускать от каждого сына шарнира.

Пардон, забываю, что вы говорите про сыновей в дереве обхода. Первый вопрос исчерпан. Но по второму еще актуален.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.03.2013, 02:21     Организовать обход в глубину #8
Цитата Сообщение от Veyron Посмотреть сообщение
Изначально вопрос стоял как это реализовать в ОДНОМ или в ДВУХ DFS, а не запускать от каждого сына шарнира.
Так там и получается один dfs.
Вы ведь при dfs из каждой вершины рекурсивно вызываете функцию. От обычного dfs это будет отличаться лишь тем, что функция будет возвращать значение.
То есть при обычном обходе у вас будет нечто такое
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 //edges - вектор списков ребер для каждой вершины
//used - булевый массив
void dfs(int v)
{
   for (int i = 0; i < edges[v].size(); ++i)
   {
       int to = edges[v][i];
       if (!used[to])
      {
           used[to] = true;
           dfs(to);
       }
   }
}
А если модифицировать, то будет как-то так (для простоты не учитывается время входа в вершину и наивысший достижимый предок, то есть это не поиск точек сочленения, а обычный dfs).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//int dfs(int v)
int res = 0;
...
for (int i = 0; i < edges[v].size(); ++i)
{
    int to = edges[v][i];
    if (!used[to])
    {
        used[to] = true;
        res += dfs(to) + 1; //учитываем ответ для to и саму to
    }
}
...
return res;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2013, 02:32     Организовать обход в глубину
Еще ссылки по теме:

Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" - C++
Ребятаа, обьясните чем различается: Обход в прямом направлении и Итерационный прямой обход Добавлено через 10 минут НароооД,...

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.03.2013, 02:32  [ТС]     Организовать обход в глубину #9
diagon, спасибо, уже сообразил
Yandex
Объявления
17.03.2013, 02:32     Организовать обход в глубину
Ответ Создать тему
Опции темы

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