Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Pthread_create несколько переменных https://www.cyberforum.ru/ cpp-beginners/ thread1293653.html
Доброго времени суток всем. Прошу сильно не пинать - новичек в C++ Взял пример из сети - работа сокетов и потоки, все работает: #include <stdio.h> #include <string.h> //strlen #include...
Подсчитать сколько слов в предложении C++
1) вводится текст. подсчитать сколько слов в предложении. предложении заканчиваются '.' '!' '?'... в предложении могут быть ',' ...
C++ Строки и файлы https://www.cyberforum.ru/ cpp-beginners/ thread1293627.html
Существует текстовый файл, в котором записано некоторое стихотворение, строчки которого перепутаны местами. В конце каждой строки указано число, которое показывает ее номер в исходном тексте....
C++ Перевести числа из одного массива в другой (кроме первого максимального и последнего минимального) https://www.cyberforum.ru/ cpp-beginners/ thread1293617.html
НУ ЗАДАЧА В ТОМ ЧТОБ ПЕРЕМЕСТИТЬ ВСЕ ЦИФРЫ a МАССИВА В b КРОМЕ ПЕРВОГО МАКСИМАЛЬНОГО И ПОСЛЕДНЕГО МИНИМАЛЬНОГО ЭЛЕМЕНТА>Я НАПИСАЛ ТАКОЙ КОД НО НЕ ПОЛУЧИЛСЯ>ЧТО ИЗМЕНИТЬ И ДОПОЛНИТЬ В МОЕМ КОДЕ...
C++ Определить, является ли введённое натуральное число целой степенью тройки
Определить, является ли введённое натуральное число целой степенью числа 3
C++ Задача о последовательных делителях https://www.cyberforum.ru/ cpp-beginners/ thread1293609.html
Учитель написал на доске некое натуральное число. После этого первый ученик сказал: «Это число делится на 1». Второй сказал: «Это число делится на 2», ..., 50-й сказал: «Это число делится на...
C++ Не знаю как сделать цикл Здравствуйте! ребят, помогите решить проблему... Вот сделал программу которая закрывает процессы/окна которые есть в файле т.е. их названия. Всё бы хорошо,но не могу сделать чтобы при выборе... https://www.cyberforum.ru/ cpp-beginners/ thread1293606.html Ввести строку и слово. Вставить введенное слово за пятым словом в строке C++
Помогите ребят. Нужно написать программу на С++ без использования библиотек <ctype.h>, <string.h> или <stdlib.h>. Ввести строку и слово. Вставить введенное слово за пятым словом в строке. Если...
C++ Задача на обработку символьных данных (сравнить строку введенным с клавиатуры, и вывести результат сравнение Здравствуйте. Задача на обработку символьных данных такая: Сравнить строки,введенные пользователем с клавиатуры, и вывести результаты сравнение на экран. Как это реализовать на TurboC? https://www.cyberforum.ru/ cpp-beginners/ thread1293594.html C++ Поиск файлов в локальной сети Программа для Поиск файлов в локальной сети на visual С++ https://www.cyberforum.ru/ cpp-beginners/ thread1293586.html
Изменение даты на N дней C++
Нужно было написать программу, где в первой строчке на вход подаются три числа через - дата в формате день, номер месяца, год; во второй строчке нужно ввести число N. Программа должна выводить дату,...
C++ Перевести слово в другой массив и вставить букву "с" https://www.cyberforum.ru/ cpp-beginners/ thread1293571.html
надо перевести "barelona" в b массив.и после буквы r вставить букву 'с' чтоб в массиве b получилось "barcelona" #include "stdafx.h" #include <iostream> using namespace std; void TpelIrakanMassiv...
4 / 4 / 1
Регистрация: 12.09.2013
Сообщений: 134
0

Алгоритм поиска в глубину в ориентированном графе - C++ - Ответ 6815350

06.11.2014, 18:36. Показов 2673. Ответов 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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int mass[10][10] =
{
    { 0, 0, 0, 0, 3, 0, 0, 0, 0, 4 }, //1
    { 0, 0, 0, 8, 0, 0, 0, 0, -3, 0 }, //2
    { 3, 10, 0, 0, 0, 0, 0, 0, 0, 0 }, //3
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 }, //4
    { 0, 0, 0, 0, 0, 0, 7, 5, 0, 0 }, //5
    { 0, 0, 9, 0, 0, 0, 0, 0, 0, 0 }, //6
    { -2, 0, 0, 0, 2, 0, 0, 0, 0, 0 }, //7
    { 0, 0, -5, 0, 0, 0, 0, 0, 0, 0 }, //8
    { 0, 0, 0, 0, 0, 0, 11, 0, 0, 0 }, //9
    { 0, 0, 0, 0, 0, -1, 0, 0, 0, 0 }, //10
    
};
//поиск в глубину
class DFS
{
private:
    vector<vector<int>> graph;
    vector<vector<bool>> used;
    vector<int> comp;
public:
    DFS();
    ~DFS(){};
    DFS(int n);
    void dp();
    void dfs(int index, vector<bool> &b);
    void show_graph();
};
 
DFS::DFS()
{
    int n = 10;
    vector<int> g;
    vector<bool> b;
    for (int i = 0; i<n; i++)
    {
        comp.push_back(false);
    }
    for (int i = 0; i<n; i++)
    {
        used.push_back(b);
        graph.push_back(g);
        for (int j = 0; j<n; j++)
        {
            graph[i].push_back(mass[i][j]);
            used[i].push_back(false);
        }
    }
}
 
DFS::DFS(int n)
{
    vector<int> g;
    vector<bool> b;
    for (int i = 0; i<n; i++)
    {
        used.push_back(b);
        graph.push_back(g);
        for (int j = 0; j<n; j++)
        {
            graph[i].push_back(mass[i][j]);
            used[i].push_back(false);
        }
    }
}
 
void DFS::dp()
{
    vector<bool> b; 
    int from;
    for (int i = 0; i<graph.size(); i++)
    {
        b.push_back(false);
    }
    cout << "Введите первую вершину: ";
    cin >> from;
    dfs(from - 1, b);
}
 
void DFS::dfs(int index, vector<bool> &b)
{
    for (int i = 0; i<graph[index].size(); i++)
    {
        b[index] = true;
        if (!b[i] && graph[index][i] != 0)
        {
            cout << "Переход от " << index + 1 << "->" << i + 1 << endl;
            dfs(i, b);
        }
    }
}
 
void DFS::show_graph()
{
    for (int i = 0; i<graph.size(); i++)
    {
        for (int j = 0; j<graph[i].size(); j++)
        {
            cout << graph[i][j] << "   ";
        }
        cout << endl<<endl;
    }
}
 
void main()
{
    setlocale(LC_ALL, "Russian");
    char c;
    int l;
    DFS g;
    do
    {
        cout << "Весовая матрица:"<<endl;
        g.show_graph();
        cout << endl;
        g.dp();
        cout << "Если хотите повторить поиск используя другую вершину нажмите Y: ";
        cin >> c;
    } while (c=='y' || c=='Y');
}


Вернуться к обсуждению:
Алгоритм поиска в глубину в ориентированном графе C++
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.11.2014, 18:36
Готовые ответы и решения:

Класс для поиска простых контуров на ориентированном графе
Ребят, помогите прогу написать :gsorry: завтра сдавать, а я не знаю ничего совсем :gsorry::gcray: ...

Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами
Ребята день добрый. Задание у меня вот такое: Используя метод поиска в ширину, найти и вывести...

Метод поиска в глубину, в неориентированном графе
Добрый день! Помогите решить задание: Используя метод поиска в глубину, в неориентированном...

Иллюстрация поиска в глубину в графе
Здравствуйте уважаемые программисты. Необходима ваша помощь в решении задачи. Ниже представлен код...

1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.11.2014, 18:36

Анимирование алгоритма поиска в глубину на графе
Вообщем нужно сделать такую же анимация как здесь -...

Нахождение основного дерева в графе методом поиска в глубину.
УСЛОВИЕ: Разработайте программу нахождения основного дерева в графе методом поиска в глубину!...

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

Алгоритм поиска в глубину
Мне нужен сам алгоритм, как программа на С ++, желательно с пояснениями к строкам. Может кто-то...

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru