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

BFS и удаление вершины графа

13.05.2019, 17:44. Показов 1238. Ответов 6

Дан граф, который необходимо представить списком смежности или матрицей смежности. Требуется запустить bfs(поиск в ширину) из заданной вершины и отметить смежные вершины. Вершины непомеченные удалить.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2019, 17:44
Ответы с готовыми решениями:

Удаление вершины графа
Добрый вечер. Нужна помощь в удалении вершины графа. Вот код: struct arc; struct node {...

Обход графа в ширину - Breadth First Search (BFS)
Всем привет! Я не понимаю алгоритм обхода в глубину BFS:( Кто может помощь?

Найти вершины графа, находящихся на заданном расстоянии от данной вершины
Есть неориентированный граф задан матрицей смежности, нужно найти вершины графа находящихся на...

Найти вершины графа, находящихся на заданном расстоянии от данной вершины
Найти вершины графа, находящихся на заданном расстоянии от данной вершины. Абсолютно безвыходная...

6
3660 / 2997 / 828
Регистрация: 25.03.2012
Сообщений: 11,044
Записей в блоге: 1
13.05.2019, 18:49 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
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;
int main()
{
    vector<string> mat;
    string s;
    int start;
    {
        ifstream in("input.txt");
        in >> start; in.ignore();
        while (getline(in, s))
            mat.push_back(s);
    }
    queue<int> bfs;
    set<int> linked;
    bfs.push(start);
    linked.insert(start);
    while (!bfs.empty())
    {
        int node = bfs.front();
        bfs.pop();
        for(int i=0; i<mat.size(); ++i)
            if (mat[node][i] == '1' && linked.find(i) == linked.end())
            {
                linked.insert(i);
                bfs.push(i);
            }
    }
    for (auto result : linked)
        cout << result << " ";
    {
        ofstream out("output.txt");
        for (int i = 0; i < mat.size(); ++i) {
            for (int j = 0; j < mat.size(); ++j)
                if (linked.find(i) != linked.end())
                    out << mat[i][j];
                else
                    out << '0';
            out << endl;
        }
    }
    return 0;
}
Добавлено через 16 секунд
Код
0
11100
11100
11100
00011
00011
0
0 / 0 / 0
Регистрация: 17.09.2018
Сообщений: 68
13.05.2019, 19:45  [ТС] 3
Kuzia domovenok, большое спасибо за ответ! Но мне трбуется реализовать список смежности или матрицу массивом, а не вектором.
0
3660 / 2997 / 828
Регистрация: 25.03.2012
Сообщений: 11,044
Записей в блоге: 1
13.05.2019, 19:46 4
Sicario, А какая разница?
0
0 / 0 / 0
Регистрация: 17.09.2018
Сообщений: 68
13.05.2019, 20:15  [ТС] 5
Условие задачи+в векторах неизвестно, сколько памяти выделается для работы программы
0
3660 / 2997 / 828
Регистрация: 25.03.2012
Сообщений: 11,044
Записей в блоге: 1
13.05.2019, 20:19 6
Sicario, что значит "неизвестно"? В том смысле, что векторам можно менять размер? И что же в этом плохого?
0
3660 / 2997 / 828
Регистрация: 25.03.2012
Сообщений: 11,044
Записей в блоге: 1
28.05.2019, 12:23 7
да что не так-то? Вы С++ знаете? Массивы знаете? В чём проблема считать матрицу смежности в массив?

Вы либо трусите что-то самостоятельно написать на С++, либо вообще плохо знаете С++.
В обоих случаях, вы не станете программистом.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.05.2019, 12:23
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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