Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.90/21: Рейтинг темы: голосов - 21, средняя оценка - 4.90
0 / 0 / 0
Регистрация: 07.11.2015
Сообщений: 15

Поиск в глубину. Графы. С++

04.12.2016, 23:04. Показов 4020. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задана ,допустим, такая матрица смежности
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
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#pragma once
#include <iostream> 
#include <fstream>
#include <vector>
class Node {
private:
    static const int n = 5;
    int i, j;
    int graph[n][n];
public:
    void Show();
    void DFS(std::vector<bool> &visited, int unit);
};
Node.cpp
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
#include "Node.h"
void Node::DFS(std::vector<bool> &visited, int unit){
    std::vector <int> queue(n, 0);
    int count = 0;
    int head = 0;
    queue[count++] = unit; //стартовая вершина помещается в "очередь" 
    visited[unit] = true; //вершина помечается как посещенная 
    unit = queue[head++];
    std::cout << unit + 1 << " ";
    int to = 0;
    for (i = 0; i < n; i++) {
        if ((graph[unit][i] != 0) && (!visited[i])) {
            DFS(visited, i);
        }
    }
}
void Node::Show() {
    std::ifstream f("matrix.txt"); 
    if (!f.is_open()) {
        std::cout << "Файл не может быть открыт!\n";
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            f >> graph[i][j];
        }
    }
    f.close();
    int start;
    std::vector <bool> visited(n);
    std::cout << "Матрица смежности графа: " << std::endl;
    for (i = 0; i < n; i++)
    {
        visited[i] = false;
        for (j = 0; j < n; j++) {
            std::cout << " " << graph[i][j];
        }
        std::cout << std::endl;
    }
    std::cout << "Стартовая вершина >> ";
    std::cin >> start;
    std::cout << "Порядок обхода: ";
    DFS(visited, start - 1);
    std::cout << std::endl;
}
main.cpp
C++
1
2
3
4
5
6
7
8
#include "Node.h"
using namespace std;
 
void main(){
    setlocale(LC_ALL, "Rus");
    Node a;
    a.Show();
}
Работает некорректно. не могу понять в чем ошибка. Подскажите пожалуйста
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
04.12.2016, 23:04
Ответы с готовыми решениями:

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

графы. поиск в глубину
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк...

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

7
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,224
04.12.2016, 23:40
Цитата Сообщение от Samchik Посмотреть сообщение
Работает некорректно. не могу понять в чем ошибка.
Во-первых, с чего вы взяли, что что-то "работает некорректно"? Что вы запускали, что вводили? Почему это не указано в начальном сообщении? Телепатов тут нет.

Во-вторых, зачем в DFS используется какая-то queue? Зачем вы заносите значение unit в queue и сразу же снова оттуда достате? Объясните, в чем заключается смысл этой манипуляции.

В-третьих, у вас переменная i почему-то объявлена за пределами рекурсивной функции DFS, в результате чего рекурсивные вызовы DFS конфликтуют друг с другом. Из-за этого ваша функция DFS корректно работать не будет. С чего это вдруг у вас i и j стали членами класса?
0
0 / 0 / 0
Регистрация: 07.11.2015
Сообщений: 15
04.12.2016, 23:41  [ТС]
TheCalligrapher,
Зачем вы заносите значение unit в queue и сразу же снова оттуда достате?
Мне кажется так я помещаю в очередь.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,224
04.12.2016, 23:46
Цитата Сообщение от Samchik Посмотреть сообщение
Мне кажется так я помещаю в очередь.
Так в том-то и вопрос: откуда взялась какая-то "очередь"? И зачем вы в нее что-то помещаете? Какую роль эта "очередь" играет в вашем алгоритме?
0
0 / 0 / 0
Регистрация: 07.11.2015
Сообщений: 15
04.12.2016, 23:49  [ТС]
TheCalligrapher, надо ее вообще убрать? так должно быть ?
C++
1
2
3
4
5
6
7
8
9
10
void Node::DFS(std::vector<bool> &visited, int unit){
    int i=0;
    visited[unit] = true
    std::cout << unit + 1 << " ";
    for (i = 0; i < n; i++) {
        if ((graph[unit][i] != 0) && (!visited[i])) {
            DFS(visited, i);
        }
    }
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,224
04.12.2016, 23:52
Цитата Сообщение от Samchik Посмотреть сообщение
надо ее вообще убрать?
Вы приделали туда какую-то "очередь", которая используется только для переливания из пустого в порожнее. Зачем это было сделано и нужно ли ее убрать - это уже у вас надо спрашивать.

А основная ошибка у вас с переменными i и j. Тольоко зачем вы именно в эту функцию приплели переменную j, которая никому тут не нужна - мне опять не ясно.
0
0 / 0 / 0
Регистрация: 07.11.2015
Сообщений: 15
04.12.2016, 23:55  [ТС]
TheCalligrapher, Вот что выводит,теперь верно?
Тольоко зачем вы именно в эту функцию приплели переменную j
Увидел -исправил
Изображения
   
0
0 / 0 / 0
Регистрация: 07.11.2015
Сообщений: 15
05.12.2016, 00:28  [ТС]
TheCalligrapher, все верно же отрабатывает?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
05.12.2016, 00:28
Помогаю со студенческими работами здесь

Графы: как можно использовать обход в глубину?
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?

Поиск в глубину (графы)
Привет прошу помощи) Есть у меня ориентированный граф граф, нужно в нем найти элементарные цепи при помощи поиска в глубину. Вот мой...

Графы. Визуализация поиска в глубину
Может быть кто-нибудь подскажет,как можно реализовать такую программу,а то с визуализацией вообще идей 0. Про компоненты сейчас читаю,но...

Графы, обход вершин в ширину и глубину
Граф задан матрицей смежности. Изобразить граф и два его подграфа, получаемые обходом его вершин поиском в глубину и в ширину. Ещё не...

Поиск в глубину, поиск в ширину, дерево
Добрый день. Есть задача с бидонами (есть три бидона : 1ый 14 литров -заполнен молоком, 2ой 9 литров-пуст, 3ий 5 литров - пуст. Нужно путем...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера 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. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru