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

Алгоритм поиска в ширину - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 123, средняя оценка - 4.71
r4zieL
 Аватар для r4zieL
15 / 15 / 1
Регистрация: 24.01.2010
Сообщений: 46
29.01.2011, 21:24     Алгоритм поиска в ширину #1
Вот тут нашел реализацию алгоритма поиска в ширину кратчайших расстояний в графе. По идее расстояния должны храниться в массиве d[], но ответ там неправильный. В чем может быть проблема?
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
int main ()
{
    vector < vector<int> > g; // граф
    const int n = 4; // число вершин
    int s = 0; // стартовая вершина (вершины везде нумеруются с нуля)
     // чтение графа
    int Adj[n][n]={ {0,1,0,0},
    {0,0,1,0},
    {0,0,0,1},
    {0,0,0,0} }; 
    for (int i = 0; i<n; i++)
    {
        g.push_back(vector<int>());
        for(int j = 0; j<n; j++)
        {
            g[i].push_back(0);
            g[i][j]=Adj[i][j];
        }
    }
    queue<int> q;
    q.push (s);
    vector<bool> used (n);
    vector<int> d (n), p (n);
    used[s] = true;
    p[s] = -1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (size_t i=0; i<g[v].size(); ++i) 
        {
            int to = g[v][i];
            if (!used[to]) 
            {
                used[to] = true;
                q.push (to);
                d[to] = d[v] + 1;
                p[to] = v;
            }
        }
    }
    for (int i = 0; i<n; i++)
        cout << d[i] << "  ";
    
    cout << endl;
    system("pause");
    return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.01.2011, 21:24     Алгоритм поиска в ширину
Посмотрите здесь:

Алгоритм поиска А* C++
Алгоритмы поиска в глубину и ширину C++
Дерево поиска. Обход в ширину. C++
Алгоритм поиска в ширину C++
C++ Алгоритм поиска
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
29.01.2011, 22:14     Алгоритм поиска в ширину #2
r4zieL, давай пример матрицы и ответ правильный в к ней
r4zieL
 Аватар для r4zieL
15 / 15 / 1
Регистрация: 24.01.2010
Сообщений: 46
29.01.2011, 22:26  [ТС]     Алгоритм поиска в ширину #3
Матрица есть в коде. Правильный ответ должен быть (0,1,2,3)
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
29.01.2011, 22:32     Алгоритм поиска в ширину #4
та матрица, что задана у тебя в коде - полная фигня, т.к. матрица смежности - симметрична.

Добавлено через 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
49
50
51
52
53
54
55
56
57
58
#include <vector>
#include <stdio.h>
#include <queue>
#include <iostream>
 
using namespace std;
 
int main ()
{
    vector < vector<int> > g; // граф
    const int n = 4; // число вершин
    int s = 0; // стартовая вершина (вершины везде нумеруются с нуля)
    // чтение графа
    int Adj[n][n] = {
    {0,1,0,0},
    {1,0,1,0},
    {0,1,0,1},
    {0,0,1,0} }; 
    for (int i = 0; i < n; i++)
    {
        g.push_back(vector<int>());
        for(int j = 0; j < n; j++)
        {
            g[i].push_back(0);
            g[i][j]=Adj[i][j];
        }
    }
    queue<int> q;
    q.push (s);
    vector<bool> used (n);
    vector<int> d (n), p (n);
    used[s] = true;
    p[s] = -1;
    while (!q.empty())
    {
        int v = q.front();
        for (size_t i = 0; i < g[v].size(); ++i) 
        {
            if (!used[i] && g[v][i]) 
            {
                used[i] = true;
                q.push (i);
                d[i] = d[v] + 1; // расстояние;
                p[i] = v; // parent;
            }
        }
        q.pop();
    }
    for (int i = 0; i < n; i++)
        cout << d[i] << "  ";
    cout << endl;
    for (int i = 0; i < n; i++)
        cout << p[i] << "  ";
 
    cout << endl;
    system("pause");
    return 0;
}
правильный код
еще выводит последовательность отцов
r4zieL
 Аватар для r4zieL
15 / 15 / 1
Регистрация: 24.01.2010
Сообщений: 46
29.01.2011, 22:55  [ТС]     Алгоритм поиска в ширину #5
По той ссылке, где я брал код, сказано, что алгоритм работает как с неориентированными графами, так и с ориентированными. Моя матрица смежности - для орграфа.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
29.01.2011, 23:05     Алгоритм поиска в ширину #6
раньше надо было говорить
моя вариант работант для обычного графа, если надо - переделывай сам
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.01.2011, 09:52     Алгоритм поиска в ширину #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от r4zieL Посмотреть сообщение
но ответ там неправильный. В чем может быть проблема?
Проблема в том, что в Вашей ссылке не описано, как происходит чтение графа. Вы решили, что в g нужно записать матрицу смежности. На самом деле для Вами приведенной матрицы смежности:
Цитата Сообщение от r4zieL Посмотреть сообщение
int Adj[n][n]={ {0,1,0,0},
{0,0,1,0},
{0,0,0,1},
{0,0,0,0} };
В g нужно записать такие данные:
1
2
3
""
Т.е. в каждой строке записаны номера вершин в которые есть путь из вершины, соответствующей этой строке.
В строке 0 находится только 1 (из вершины 0 есть путь в вершину 1).
В строке 1 находится только 2 (из вершины 1 есть путь в вершину 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
49
int main ()
{
        vector < vector<int> > g; // граф
        const int n = 4; // число вершин
        int s = 0; // стартовая вершина (вершины везде нумеруются с нуля)
         // чтение графа
        int Adj[n][n]={ {0,0,1,0},
        {0,0,1,0},
        {0,0,0,1},
        {0,2,0,0} }; 
        for (int i = 0; i<n; i++)
        {
                g.push_back(vector<int>());
                for(int j = 0; j<n; j++)
                {
                    if(Adj[i][j])
                        g[i].push_back(j);
                        /*g[i].push_back(0);
                        g[i][j]=Adj[i][j];*/
                }
        }
        queue<int> q;
        q.push (s);
        vector<bool> used (n);
        vector<int> d (n), p (n);
        used[s] = true;
        p[s] = -1;
        while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (size_t i=0; i<g[v].size(); ++i) 
                {
                        int to = g[v][i];
                        if (!used[to]) 
                        {
                                used[to] = true;
                                q.push (to);
                                d[to] = d[v] + 1;
                                p[to] = v;
                        }
                }
        }
        for (int i = 0; i<n; i++)
                cout << d[i] << "  ";
        
        cout << endl;
        system("pause");
        return 0;
}
и еще немного: для того какой результат Вы находите Вам вообще не нужен вектор p. вы просто выводите расстояния от вершины 0 до всех остальных вершин (причем если расстояние 0 (за исключением самой вершины 0), то значит вершина вообще недостижима из вершины 0). Вектор p нужен только когда нужно будет вывести на экран не длинну пути, а сам путь (через какие вершины проходит самый короткий путь от вершины 0 до нужной вершины).
oZ-z-z-z
2 / 2 / 0
Регистрация: 25.01.2011
Сообщений: 3
30.01.2011, 16:39     Алгоритм поиска в ширину #8
valeriikozlov, спасибо, мне тоже помогло
sandye51
31.01.2011, 06:46
  #9

Не по теме:

oZ-z-z-z, вам бы еще помогло правила почитать: для спасибо есть кнопка

oZ-z-z-z
2 / 2 / 0
Регистрация: 25.01.2011
Сообщений: 3
31.01.2011, 09:15     Алгоритм поиска в ширину #10
Цитата Сообщение от sandye51 Посмотреть сообщение

Не по теме:

oZ-z-z-z, вам бы еще помогло правила почитать: для спасибо есть кнопка

спасибо за совет!

Добавлено через 7 минут
Цитата Сообщение от oZ-z-z-z Посмотреть сообщение
спасибо за совет!
для этого тоже есть какая-нибудь кнопочка?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
31.01.2011, 15:57     Алгоритм поиска в ширину #11
Цитата Сообщение от oZ-z-z-z Посмотреть сообщение
для этого тоже есть какая-нибудь кнопочка?
называется "купите мне мозг"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2012, 10:32     Алгоритм поиска в ширину
Еще ссылки по теме:

C++ Простые алгоритм поиска?
C++ Алгоритм поиска(не находит)
C++ Алгоритмы поиска кратчайших путей в ширину и двунаправленный в ширину

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

Или воспользуйтесь поиском по форуму:
ююю
0 / 0 / 0
Регистрация: 10.12.2011
Сообщений: 40
08.06.2012, 10:32     Алгоритм поиска в ширину #12
а на паскали это можете записать !!!!алгоритм обхода графа в ширину
Yandex
Объявления
08.06.2012, 10:32     Алгоритм поиска в ширину
Ответ Создать тему
Опции темы

Текущее время: 07:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru