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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.78
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
#1

графы,поиск в глубину - C++

08.04.2013, 21:12. Просмотров 7683. Ответов 3
Метки нет (Все метки)

очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину. Есть готовый алгоритм поиска,из интернета,но как связать все вместе не могу сообразить. Может кто-нибудь решал подобные задачки. Заранее спасибо
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
vector < vector <int> > g; // заданный граф.
vector <int> used; // массив меток. в начале его нужно заполнить 0.
int n; // число вершин в графе.
 
void dfs (int v){
     used[v] = 1; // ставим метку, что посетили данную вершину
     for (int i = 0; i < (int)g[v].size(); i++){ // проходим по все ребрам.
           if (!used[g[v][i]]){ // смотрим были ли мы в вершине раньше
                 dfs(g[v][i]); // если нет, то запускаемся из нее.
           }
     }
 
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2013, 21:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос графы,поиск в глубину (C++):

графы. поиск в глубину - C++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

Поиск в глубину. Графы. С++ - C++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Avazart
Эксперт С++
7187 / 5361 / 280
Регистрация: 10.12.2010
Сообщений: 23,654
Записей в блоге: 17
08.04.2013, 21:51 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    const int SIZE = 1e3 + 10;
    vector<int> adj[SIZE];
    bool usd[SIZE];
    ...
    void dfs(int cur) {
      usd[cur] = true;
      for (int i=0;i<adj[cur].size();++i) {
        int nxt = adj[cur][i];
        if (!usd[nxt])
          dfs(nxt);
      }
    }
    int connected_components_amount_dfs() {
      int cnt = 0;
      for (int i=1; i<=n; ++i) {
        if (!usd[i]) {
          dfs(i);
          ++cnt;
        }
      }
      return cnt;
    }
http://cppalgo.blogspot.com/2012/08/blog-post.html
2
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
08.04.2013, 21:54 #3
поиск компонент связанность. граф на вход задается списком ребер
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
using namespace std;
 
vector<vector<int> > g;
vector<bool> used;
vector<int> comp;
 
void dfs(int v)
{
    used[v] = true;
    for (int i = 0; i < g[v].size(); ++i)
    {
        int to = g[v][i];
        if (!used[to])
            dfs(to);
    }
    comp.push_back(v);
}
 
int main(void)
{
    int n, m;
    cin >> n >> m;
    g.resize(n);
    used.resize(n);
    for (int i = 0, a, b; i < m; ++i)
    {
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < g.size(); ++i)
    {
        if (!used[i])
        {
            comp.clear();
            dfs(i);
            cout << comp.size() << endl;
            for (int j = 0; j < comp.size(); ++j)
                cout << comp[j] << ' ';
            cout << endl;
        }
    }
    return 0;
}
2
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
10.04.2013, 17:26  [ТС] #4
большое спасибо)))
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2013, 17:26
Привет! Вот еще темы с ответами:

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

Рекурсивный поиск в глубину - C++
Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта...

Итеративный поиск в глубину - C++
Здравствуйте! Вопрос связан с поиском в графе. Меня интересуют идеи решения или ссылка на литературу. Пожалуйста, подскажите... ...

Рекурсивный и нерекурсивный поиск в глубину - C++
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то рекурсивный и нерекурсивный поиски дадут одинаковые...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.04.2013, 17:26
Ответ Создать тему
Опции темы

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