Форум программистов, компьютерный форум CyberForum.ru

Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Использование libopencm3 http://www.cyberforum.ru/cpp-beginners/thread1514526.html
Добрый день. Пытаюсь запустить пример к библиотеке libopencm3. Есть объявленная структура: struct usb_config_descriptor { uint8_t bLength; uint8_t bDescriptorType; uint16_t wTotalLength; uint8_t bNumInterfaces;
C++ Кольцевой список STL Добрый день, такой вопрос: можно ли работать с STL-списком как с кольцевым? Если да, то как? Нигде не нашел в литературе. http://www.cyberforum.ru/cpp-beginners/thread1514507.html
C++ Откуда cmd берет тайлы букв?
читаю форум, в соседней ветке обсуждают коды нажатия клавиш клавиатуры. подумал, как происходит рисование в командной строке, в том числе рисование тайлов букв (т.е. какой-нибудь текстовый редактор сделать) кто что может подсказать по данной теме? заранее спасибо
Форма документа о продаже товаров C++
Помогите, пожалуйста. Не знаю как написать по этому программу Информация о продаже товаров подготовлена по следующему макету: номер магазина; номер секции; номер чека; наименование товара; артикул товара; цена товара; количество то- вара; дата продажи. Составить программу определения объема товарооборота по каждому ма- газину, т.е. общую сумму, вырученную от продажи всех товаров в данном...
C++ Где хранит свои данные vector? http://www.cyberforum.ru/cpp-beginners/thread1514458.html
class A { class B{...} vector<B> vec; foo1() { vec.emplace_back(B()); }
C++ Что почитать для обучения В недавнем времени изучил html и css и мне стали интересны компьютеры,но делать сайты не хочу, и начал изучать c++,но насколько я понял,кроме самого c++ нужно знать алгоритмы и что-то ещё,я не знаю...Хочу вообще математику подтянуть (дискретная наверное нужна),потом в ОС начать разбираться ,архитекуре компьютера и сетях Подскажите что почитать Есть книги Танненбаума и Хаггарти(из серии... подробнее

Показать сообщение отдельно
kinivi
0 / 0 / 0
Регистрация: 13.08.2015
Сообщений: 5
14.08.2015, 11:26     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину
В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Входные данные
Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

Выходные данные
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Если пути нет, нужно вывести -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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int> > edges;
vector <int> doroga;
 
int start;
int d[100],mark[100],m[100][100],v[100],p[100];
void BFS()
{
    queue<int> q;
    // Инициализация: есть информация про начальную вершину
    q.push(start);
    p[start]=-1;
    d[start] = 0;
    mark[start] = 1;
    // Главный цикл - пока есть серые вершины
    while (!q.empty())
    {
        // Берем первую из них
        int v = q.front();
        q.pop();
        // Пробегаемся по всем ее соседям
        for (int i = 0; i < (int)edges[v].size(); ++i)
        {
            // Если сосед белый
            if (mark[edges[v][i]] == 0)
            {
                // То вычисляем расстояние
                d[edges[v][i]] = d[v] + 1;
                p[edges[v][i]]= v;
                // И он становится серым
                mark[edges[v][i]] = 1;
                q.push(edges[v][i]);
            }
        }
    }
}
 
int main()
{
setlocale(LC_ALL, "Rus");
int n,k,en,st;
cin>>n;
edges.resize(n);
for(int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    cin>>m[i][j];
 
for (int i=0;i<n;i++) {k=0;
    for (int j=0;j<n;j++)
    if ( m[i][j] ==1) { edges[i].push_back(j);k++;}
}
cin>>st>>en;
start=st-1;
 
BFS();
if (!mark) cout<<-1; else if (en==st) cout<<0; else {
cout<<d[en-1];
cout<<endl;
 
 
    for (int v=en;v!=-1;v=p[v]) doroga.push_back(v+1);
 
    for(int i=doroga.size()-1;i>0;i--) cout<<doroga[i]<<' ';
cout<<en;
}
 
 
 
 
 
 
}
На сайте informatics проходит только 6 тестов (остальные это ошибка: неправильный формат вывода). В коде меня смущает то что конечный елемент пути (p[en]=5 не 4 как это должно быть)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 04:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru