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

Найти путь из А в Б в неориентированном невзвешенном графе заданным матрицей смежности

20.12.2020, 19:14. Показов 1367. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задан неориентированный граф матрицей смежности(6х6). 1 - есть путь 0 - нет пути, задается случайным образом. Найти путь из заданной вершины А в вершину Б. Результат записать в виде последовательности прохождения по вершинам графа.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.12.2020, 19:14
Ответы с готовыми решениями:

Найти и вывести все циклы в невзвешенном, неориентированном графе без петель с N вершинами и E ребрами
Дан невзвешенный, неориентированный граф без петель с N вершинами и E ребрами. Граф вводится в...

Найти все циклы в неориентированном графе по матрице смежности
Здравствуйте. Задача в заголовке. С построением матрицы смежности проблем нет, вопрос в алгоритме...

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

Найти эйлеров путь в неориентированном графе
Найти эйлеров путь в неориентированном графе. Начальную вершину пути ввести с клавиатуры. Граф...

3
610 / 415 / 151
Регистрация: 11.01.2019
Сообщений: 1,746
20.12.2020, 19:18 2
Каков критерий выбора пути, если их будет много?
0
0 / 0 / 0
Регистрация: 25.09.2020
Сообщений: 5
20.12.2020, 19:24  [ТС] 3
Любой, первый попавшийся
0
392 / 262 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
20.12.2020, 19:52 4
https://informatics.mccme.ru/m... p?id=255#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
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<int>>v;
int n,f,s;
 
void bfs(){ 
    vector<bool>used(n);
    vector<int>from(n);
    queue<int>q;
    
    q.push(f);
    from[f] = -1;
    used[f] = 1;
    
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for(int i = 0;i<n;++i)if(!used[i] && v[t][i]){
            used[i] = 1;
            q.push(i);
            from[i] = t;
        }
    }
    if(s == f){
        cout << 0;
        return;
    }
    if(!used[s]){
        cout << -1;
        return;
    }
    vector<int>ans;
    for(int i = s;;){
        if(i == -1)break;
        ans.push_back(from[i]+1);
        i = from[i];
    }
    cout << ans.size()-1 << "\n";
    if(!(ans.size()-1))return;
    ans.pop_back();
    for(int i = ans.size()-1;i>=0;--i)cout << ans[i] << ' ';
    cout << s+1;
}
 
int main()
{
    cin >> n;
    v.resize(n);
    for(int i = 0;i<n;++i)v[i].resize(n);
    for(int i = 0;i<n;++i){
        for(int j = 0;j<n;++j)cin >> v[i][j];
    }
    cin >> f >> s;
    --f; --s;
    bfs();
    
    return 0;
}


Я верю, что вы сможете заменить ввод числа n на присваивание ему значения 6. А ввод матрицы на ее случайное заполнение.
0
20.12.2020, 19:52
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.12.2020, 19:52
Помогаю со студенческими работами здесь

Найти Эйлеров путь в неориентированном графе
Программа читает таблицу смежности(можно с файла),или можете выбрать свой способ задачи ребер...

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

найти и вывести путь в неориентированном графе между двумя вершинами
Методом поиска в ширину найти и вывести путь в неориентированном графе между двумя вершинами....

В неориентированном графе найти минимальный путь между двумя вершинами
В неориентированном графе требуется найти минимальный путь между двумя вершинами. Входные данные...

В неориентированном графе найти минимальный путь между двумя вершинами
Почему-то решение не проходит 1 тест. Условие В неориентированном графе требуется найти...

В неориентированном графе требуется найти минимальный путь между двумя вершинами
Путь В неориентированном графе требуется найти минимальный путь между двумя вершинами. ...


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

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