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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.78
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
08.04.2013, 21:12     графы,поиск в глубину #1
очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину. Есть готовый алгоритм поиска,из интернета,но как связать все вместе не могу сообразить. Может кто-нибудь решал подобные задачки. Заранее спасибо
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]); // если нет, то запускаемся из нее.
           }
     }
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2013, 21:12     графы,поиск в глубину
Посмотрите здесь:

Поиск в глубину C++
C++ Итеративный поиск в глубину
C++ поиск в глубину
Конечный автомат. Лабиринт (поиск в глубину) C++
C++ Не работает поиск в глубину (DFS)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,583
Записей в блоге: 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
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;
}
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
10.04.2013, 17:26  [ТС]     графы,поиск в глубину #4
большое спасибо)))
Yandex
Объявления
10.04.2013, 17:26     графы,поиск в глубину
Ответ Создать тему
Опции темы

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