Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 18.04.2014
Сообщений: 26
1

Обход неориентированного графа в глубину

27.12.2014, 04:02. Просмотров 1611. Ответов 1
Метки нет (Все метки)

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
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <fstream>
#include <vector>
#include <conio.h>
#include <locale.h>
 
using namespace std;
 
int DFS(int a, int b, vector< vector<int> > &graph, vector<int> &visit, int &n, ofstream &fout)
{
    int res = 0;
    fout << (a + 1) << endl;
    if (a == b)
    {
        fout << (a + 1) << endl;
        return 1;
    }
 
    if (visit[a] == 1) //Если мы здесь уже были, то тут делать нечего
    {
        fout <<(a + 1) << endl;
        return 0;
    }
    visit[a] = 1; //Помечаем, что мы здесь были
 
    for (int i = 0; i < n; i++)
    {
        if ((graph[a][i] == 1) && (visit[i] == 0))
            res |= DFS(i, b, graph, visit, n, fout);
        if (res == 1) 
        {
            fout << (a + 1) << endl;
            return res;
        }
    }
    fout << (a + 1) << endl;
    return res;
}
 
int main()
{
    setlocale(LC_ALL,"rus");
    ifstream fin("f.txt");
    
    int n;
    fin >> n;
    
    vector < vector<int> > graph;
    for (int i = 0; i < n; i++)
    {
        vector <int> b;
        for (int j = 0; j < n; j++)
        {
            graph.push_back(b);
            b.clear();
        }
    }   
 
    vector<int> visit(n);
    int a, b;
    cout<<"введите начало пути ";
    cin >> a ;
    cout<<"введите конец пути ";
    cin>> b;
    fin.close();
 
    ofstream fout("g.txt");
    
    fout << "Стартовая вершина: " << a << endl;
    fout << "Конечная вершина: " << b << endl;
    fout << "Порядок обхода:" << endl;
    if (DFS(a-1, b-1, graph, visit, n,  fout) == 1)
        { fout << "Путь из " << a << " в " << b << " существует."; }
    else
        { fout << "Путь из " << a << " в " << b << " не существует."; }
    return 0;
}
выдает ошибку "Необработанное исключение в "0x75ae2f71" в "graf.exe": Исключение Microsoft C++: std::length_error по адресу 0x0038f1a8.."

посмотрите пожалуйста! помогите исправить и довести программу до ума) Граф не ориентированный, матрица смежности задается из файла
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.12.2014, 04:02
Ответы с готовыми решениями:

Обход неориентированного графа в ширину. В конце выдаёт путь: 1
#include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;conio.h&gt; using namespace std; int n;// число...

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

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

Обход графа в глубину
Доброго времени суток, братцы! Есть такая задачка - обойти граф в глубину. Сам алгоритм примерно...

1
0 / 0 / 0
Регистрация: 18.04.2014
Сообщений: 26
27.12.2014, 05:29  [ТС] 2
подскажите ответы на эти вопросы, а то я сам не могу разобраться(
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
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <fstream>
#include <vector>
#include <conio.h>
 
using namespace std;
 
int DFS(int a, int b, vector< vector<int> > &graph, vector<int> &used, int &N, ofstream &fout)
{
    int res = 0; //это переменная чего?
    fout << "[ " << (a + 1) << endl;
    if (a == b)
    {
        fout << "] " << (a + 1) << endl;
        return 1;
    }
 
    if (used[a] == 1) //Если мы здесь уже были, то тут делать нечего
    {
        fout << "] " << (a + 1) << endl;
        return 0;
    }
    used[a] = 1; //Помечаем, что мы здесь были
 
    for (int i = 0; i < N; i++)
    {
        if ((graph[a][i] == 1) && (used[i] == 0))
            res |= DFS(i, b, graph, used, N, fout); //почему здесь i, а не а?
        if (res == 1) 
        {
            fout << "] " << (a + 1) << endl;
            return res; 
        } 
    } 
    fout << "] " << (a + 1) << endl;
    return res; 
}
 
int main()
{
    setlocale(LC_ALL,"rus");
    ifstream fin("1.txt");
    
    int N;
    fin >> N;
    vector < vector<int> > graph;
    for (int i = 0; i < N; i++)
    {
        vector <int> b;
        for (int j = 0, x; j < N; j++)
        {           
            fin >> x;
            b.push_back(x);         
        }
        graph.push_back(b);
        b.clear();
    }   
 
    vector<int> used(N);
    int a, b;
    fin >> a >> b;
    fin.close();
 
    ofstream fout("2.txt");
    
    fout << "Стартовая вершина: " << a << endl;
    fout << "Конечная вершина: " << b << endl;
    fout << "Порядок обхода:" << endl;
    if (DFS(a-1, b-1, graph, used, N, fout) == 1)  //почему а-1, b-1?
        { fout << "Путь из " << a << " в " << b << " существует."; }
    else
        { fout << "Путь из " << a << " в " << b << " не существует."; }
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.12.2014, 05:29

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Обход графа в глубину
Покажите кто-нибудь как работает &quot;обход графа&quot; в графе в консоле А именно вывод глубины...

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

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

Обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии от данной вершины
Реализуйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном...


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

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

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