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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.79
comalex90
7 / 7 / 1
Регистрация: 28.01.2011
Сообщений: 33
#1

поиск в глубину - C++

19.03.2012, 15:03. Просмотров 2543. Ответов 3
Метки нет (Все метки)

Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается.
C++
1
2
3
4
5
6
7
8
9
10
11
vector<char> used;
int n;
vector <vector <int> > g;
 
void dfs (int v) {
    used[v] = true;
    for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
        if (!used[*i])
            dfs (*i);
 
}
в g у меня список сумежности нашего графа,в функцию я передаю количество вершин но программа почемуто падает.Может я что то не так понял?И просьба обьяснить код,а вчастности что означает вот это
C++
1
vector<int>::iterator i
?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2012, 15:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос поиск в глубину (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.03.2012, 15:18 #2
Цитата Сообщение от stiv.loh Посмотреть сообщение
Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается.
там ошибка.

Цитата Сообщение от stiv.loh Посмотреть сообщение
C++
1
vector<char> used;
заменить на:
C++
1
vector<bool> used;
comalex90
7 / 7 / 1
Регистрация: 28.01.2011
Сообщений: 33
19.03.2012, 20:05  [ТС] #3
всеравно не работает(((

Добавлено через 14 минут
делаю примерно так(очень спростил)-
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <vector>
#include <iostream>
#include <conio.h>
using namespace std;
vector <int> ver;
vector<bool> used;
void  Graph_gen(int **a, int V, double probab);
vector <vector <int> > adjasent;
void dfs (int v) {
    used[v] = true;
    for (vector<int>::iterator i=adjasent[v].begin(); i!=adjasent[v].end(); ++i)
        if (!used[*i])
            dfs (*i);
 
}
int main()
{   double probab=0.7;
    int **graf; 
    int n=4;
    vector < vector <int> > adjasent(n);
    graf = new int*[n];
    for (int l=0; l<n; l++)
        graf[l] = new int[n];
 
    Graph_gen(graf, n,probab);
 
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (graf[i][j]==1){
                adjasent[i].push_back(j+1);
        }}
    }
cout<<"\nAdjasent list:\n";
    for (int i=0; i<n; i++){
        cout<<i+1<<"   ";
        copy(adjasent[i].begin(), adjasent[i].end(), ostream_iterator <int>(cout,"  "));
        cout<<endl;
    }
 
    dfs (n);
    
 
    getch();
    return 0;
}
//Generate Edge of a graph with a fixed probability
void Graph_gen(int **a, int V, double probab){
    for (int i=0; i<V; i++)
        for(int j=0; j<i; j++){
            if(rand()<=probab*RAND_MAX) a[i][j]=1;else a[i][j]=0;
        }
 
    for (int i=0; i<V; i++)
        for(int j=i+1; j<V; j++){
            a[i][j]=a[j][i];
        }
        for (int i=0; i<V; i++)
            a[i][i]=0;
        //вивід
        for (int i=0; i<V; i++){
        for (int j=0; j<V; j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
}
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.03.2012, 02:39 #4
Цитата Сообщение от stiv.loh Посмотреть сообщение
всеравно не работает(((

Не по теме:

все логично, что написали, то и получилось


У Вас код не завершенный. В общем-то все правильно (создаете невзвешенный, неориентированный граф), кроме одной строчки:
Цитата Сообщение от stiv.loh Посмотреть сообщение
C++
1
dfs (n);
У Вас нет вершины с индексом n. А есть вершины с индексами от 0 до n-1.
Кроме того, сама функция, которую Вы взяли отсюда:
http://e-maxx.ru/algo/dfs
она делает поиск в глубину, но никакой задачи не выполняет. Грубо говоря если вызвать эту функцию вот так:
C++
1
dfs (0);
то при поиске в глубину будут помечены все вершины от 0 до n-1 в векторе:
C++
1
vector<bool> used;
и все. Т.е. все вершины из которых есть путь от вершины 0 будут помечены true. Остальные останутся с меткой false.
Я не знаю какую задачу Вы хотите решить (условие задачи в теме не увидел), но с помощью данного алгоритма можно например решить такую задачу: определить до скольких вершин нет пути из 1 вершины. Тогда Вам осталось подсчитать после вызова
C++
1
dfs(0);
сколько вершин осталось с меткой false в used.
Или например можно решить такую задачу: определить сколько независимых подграфов существует в заданом графе. В этом случае будет несколько вызовов
C++
1
dfs();
Добавлено через 9 минут
да еще одно, перед вызовом
C++
1
dfs();
желательно сделать:
C++
1
2
        for(int i=0; i<n; i++)
            used.push_back(false);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2012, 02:39
Привет! Вот еще темы с ответами:

Поиск в глубину. Графы. С++ - 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++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

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

Не работает поиск в глубину (DFS) - C++
Вот код (заполнен для ориентированного графа 0 2 | + +/ 1--+3--+4 | + 5--+6 |


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

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

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