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

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

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

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

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

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


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

Пардон, забываю, что вы говорите про сыновей в дереве обхода. Первый вопрос исчерпан. Но по второму еще актуален.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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++
C++ Поиск в глубину
Обход неориентированного графа в глубину C++

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

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

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