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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Пардон, забываю, что вы говорите про сыновей в дереве обхода. Первый вопрос исчерпан. Но по второму еще актуален.
0
diagon
Higher
1930 / 1196 / 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;
1
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.03.2013, 02:32  [ТС] #9
diagon, спасибо, уже сообразил
0
17.03.2013, 02:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2013, 02:32
Привет! Вот еще темы с ответами:

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

Организовать обход массива по заданной схеме - C++
Добрый день. такое вот задание : 1. Заполнить значения элементов, чтобы они образовали циклический односвязный список в соответствии с...

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

Поиск в глубину - C++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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