1 / 1 / 0
Регистрация: 27.10.2017
Сообщений: 123

Обход в глубину ( без процедур )

16.09.2018, 21:20. Показов 3874. Ответов 7

Студворк — интернет-сервис помощи студентам
Здравствуйте, нашла на одном из сайтов код для обхода в глубину, не могу понять как он работает, и что можно сделать чтобы входными данными считывалась матрица смежности или хотя бы список смежности. Помогите разобраться


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
#include <iostream>
   #include <vector>
    using namespace std;
 
    vector <int> adj[10];
    bool visited[10];
 
    void dfs(int s) {
        visited[s] = true;
        for(int i = 0;i < adj[s].size();++i)    {
         if(visited[adj[s][i]] == false)
             dfs(adj[s][i]);
        }
    }
 
    void initialize() {
        for(int i = 0;i < 10;++i)
         visited[i] = false;
    }
 
    int main() {
        int nodes, edges, x, y, connectedComponents = 0;
        cin >> nodes;                       //Number of nodes
        cin >> edges;                       //Number of edges
        for(int i = 0;i < edges;++i) {
         cin >> x >> y;     
     //Undirected Graph 
         adj[x].push_back(y);                   //Edge from vertex x to vertex y
         adj[y].push_back(x);                   //Edge from vertex y to vertex x
        }
 
        initialize();                           //Initialize all nodes as not visited
 
        for(int i = 1;i <= nodes;++i) {
         if(visited[i] == false)     {
             dfs(i);
             connectedComponents++;
         }
        }
        cout << "Number of connected components: " << connectedComponents << endl;
        return 0;
    }
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
16.09.2018, 21:20
Ответы с готовыми решениями:

Обход в глубину (задача на количество грядок)
Прошу помочь с решением задачи, как уже только не возился с этим кодом, даже не представляю в чем подвох. Для входных данных в примере...

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

Обход в ширину обход в глубину
помогите написать комментарии к коду def bfs_path(graph, start, end): visited = set() queue = deque(]) ...

7
1741 / 913 / 480
Регистрация: 05.12.2013
Сообщений: 3,074
16.09.2018, 21:36
Вам точно нужен поиск в глубину? Если это продолжение вашей темы,то вам нужен поиск в ширину. Поищите поиском в разделе, эта задача уже решалась
0
1 / 1 / 0
Регистрация: 27.10.2017
Сообщений: 123
16.09.2018, 21:55  [ТС]
ТабуретY, мне нужен и поиск в глубину и поиск в ширину, и алгоритм Краскала Поиск в глубину я искала, но для питона особо не нашла, чтобы через матрицы или списки . Там еще проблемы, что встроенной функцией dfs и bfs нельзя пользоваться
0
1741 / 913 / 480
Регистрация: 05.12.2013
Сообщений: 3,074
16.09.2018, 22:05
Посмотрите ссылки внизу страницы, там поиск в глубину есть и переделать не трудно
0
1 / 1 / 0
Регистрация: 27.10.2017
Сообщений: 123
16.09.2018, 22:10  [ТС]
ТабуретY, а что с кодом который есть все сложно ? Просто переделывать с одного языка на другой для меня будет очень сложно.
0
1741 / 913 / 480
Регистрация: 05.12.2013
Сообщений: 3,074
16.09.2018, 22:11
Вам код на c++ нужен? Тогда лучше перейдите в раздел c++
0
1 / 1 / 0
Регистрация: 27.10.2017
Сообщений: 123
16.09.2018, 22:15  [ТС]
ТабуретY, нет на Python
0
1741 / 913 / 480
Регистрация: 05.12.2013
Сообщений: 3,074
16.09.2018, 22:19
Тогда в чем проблема, первая ссылка https://www.cyberforum.ru/pyth... 47083.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
16.09.2018, 22:19
Помогаю со студенческими работами здесь

кто поможет переделать 5 процедуру обход графа в глубину на обход графа в ширину
program kurs_work; uses crt,GraphABC; const n = 6; max = 1000; max_n = 36; var i, j, b : integer; Graf :...

Обход в глубину?
Вот http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3022#1 Бьюсь с ней, но никак даже несколько тестов не проходит....

Обход в глубину
Задача заключается в определении наличия цикла в ориентированном графе. Задано количество вершин и сама таблица смежности. Суть решения -...

Обход в глубину
Вот код: &lt;Window x:Class=&quot;WpfApp2.MainWindow&quot; xmlns=&quot;http://schemas.microsoft.com/winfx/2006/xaml/presentation&quot; ...

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


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

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

Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru