Форум программистов, компьютерный форум, киберфорум С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 12.03.2023
Сообщений: 2
1

Поиск вершин, откуда доступна первая в графе (в глубину)

12.03.2023, 14:20. Показов 622. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Ищу в графе все вершины, из которых доступна первая
Граф ориентированный, с петлями / кратными ребрами
В качестве ввода два числа - V (количество вершин) и E (количество ребер), затем Е пар этих самых ребер
для хранения пользуюсь 2d-вектором, в [i][0] лежит номер i-ой вершины и затем уже перечисляются связные с ней

Обход в глубину написал, но на больших числах V = 1000 и E = 10000 внезапно перестает работать, в чем ошибка?

Вот код:
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
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <vector>
#include <fstream>
 
using namespace std;
 
bool dfs(int u, vector<vector<int>> graph, int* color, int* flag) {
        if (u == 1) {
                flag[u] = 1;
                return true;
        }
        if (color[u] == 1) {
                if (flag[u] == 1) {
                        return true;
                } else {
                        return false;
                }
        }
        color[u] = 1;
        for (int j = 1; j < graph[u].size(); j++) {
                if (color[j] == 0) {
                        if (dfs(graph[u][j], graph, color, flag)) {
                                flag[u] = 1;
                                return true;
                        }
                }
        }
        return false;
}
 
int main() {
//      fstream file("input");
        vector <vector <int>> graph;
 
        int V, E;
 
        cin >> V >> E;
        graph.resize(V + 1);
        int color[V + 1];
        int flag[V + 1];
 
        for (int i = 0; i < V + 1; i++) {
                color[i] = 0;
                flag[i] = 0;
                graph[i].resize(1);
                graph[i][0] = i;
        }
 
        for (int i = 0; i < E; i++) {
                int v1, v2;
                cin >> v1 >> v2;
                graph[v1].push_back(v2);
        }
 
/*
        for (int i = 0; i <= V; i++) {
                for (int j = 0; j < graph[i].size(); j++) {
                        cout << graph[i][j] << ' ';
                }
                cout << endl;
        }
*/
 
/*
        for (int i = 0; i <= V + 1; i++) {
                cout << i << ": " << color[i] << endl;
        }
*/
 
        for (int i = 1; i <= V; i++) {
                        if (dfs(i, graph, color, flag)) {
                                cout << graph[i][0] << ' ';
                        }
        }
        cout << endl;
 
/*
        for (int i = 1; i <= V + 1; i++) {
                cout << i << ": " << flag[i] << endl;
        }
        cout << endl;
*/
 
//      file.close();
        return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.03.2023, 14:20
Ответы с готовыми решениями:

Поиск в глубину и проверка четности\нечетности степени вершин в графе, заданном матрицей смежности
Поиск в глубину и проверка четности\нечетности степени вершин в графе, заданном матрицей...

Поиск в глубину. Поиск кратчайшего пути на взвешенном графе (Алгоритм Дейкстры)
Плз.Нужна помощь в проверке кода. Найти количество путей между двумя вершинами в некотором графе...

Поиск в глубину в графе
Пытаюсь написать алгоритм поиска в глубину в матлабе, но плохо разбираюсь в нем.. function = dfs(...

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

Поиск в глубину в ориентированном графе
Помогите реализовать поиск в глубину в ориентированном графе. Поиск не работает корректно с...

2
3697 / 2647 / 761
Регистрация: 29.06.2020
Сообщений: 9,800
12.03.2023, 14:42 2
Цитата Сообщение от domino6 Посмотреть сообщение
vector<vector<int>> graph
Вы огромный граф передаете по значению, его копию, так стек очень быстро переполнится, и "считаем единорогов"

Добавлено через 44 секунды
Это только поверхностный осмотр больного ...
0
0 / 0 / 0
Регистрация: 12.03.2023
Сообщений: 2
12.03.2023, 16:19  [ТС] 3
Уже исправил, но лучше не стало
0
12.03.2023, 16:19
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.03.2023, 16:19
Помогаю со студенческими работами здесь

Рекурсивный поиск в глубину в графе
Помогите с рекурсивным поиском в глубину. Как я понял, у меня не помечает какие ребра были...

Поиск в глубину на графе, исправить ошибку
пишу прогу поиск в глубину на графе. где Assign (Input,'Input.txt'); E2029 ',' or ':' expected but...

слепой прямой поиск целевой вершины в глубину на ориентированном графе
Доброго времени суток. Случайно увидел данный раздел. У меня как раз лабы по этому предмету. Но я...

Поиск зависимых вершин в ориентированном графе
Имеется матрица смежности, вся заполнена как ориентированный граф (ну, короче не симметричная)....

Поиск максимального независимого множества вершин в графе
Всем доброго времени суток, Имеем матрицу смежности простого неориентированного графа Задача...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru