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

BFS. Путь из вершины в нее саму - C++

Восстановить пароль Регистрация
 
Космонавт_
0 / 0 / 0
Регистрация: 24.04.2011
Сообщений: 30
27.04.2011, 21:52     BFS. Путь из вершины в нее саму #1
Неверно выводит путь из вершину в нее же саму, то есть из 5 в 5 путь равен 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
59
60
61
62
63
64
65
66
67
#include <iostream>
using namespace std; 
const int m=50;
int n;// число вершин графа
int mass[m][m];//матрица смежности
int ways[m];//массив кратчайших путей
int q[m];
int st, en,tail,head ;//стартовая и конечная вершины
 //процедура получает на вход номер стартовой вершины
 
void push (int a)
{ 
    tail++;
    if (tail<m)
        q[tail]=a;
    else {
        tail=0;
        q[tail]=a;
    }
}
 
int pop ()
{ 
    head++;
    if (head<m)
        return q[head];
    else {
        head=0;
        return q[head];
    }
}
 
int empty ()
{   if (tail==head) return 1;
    else return 0;
}
 
void BFS(int stt)
{
     for (int i = 0; i < n; ++i)
      ways[i] = 0;       
     push(stt);            //помещаем первую вершину в очередь
     ways[stt] = 0 ;         //расстояние от старта до данной вершины = 0  
      while (!empty())    //пака не просмотрели все вершины
      {
            int u =pop();         
            for (int i = 0; i < n; ++i)//цикл по всем вершинам
                  if (mass[u][i] == 1 && ways[i] == 0)
                  {
                        push(i);//помещаем ее в очередь
                        ways[i] = ways[u] + 1;//обновляем для нее расстояние
                  }
      }
      cout << "Length of way: " << ways[en] << endl;
}
 int main()
{tail=0; head=0;
      freopen("input.txt", "r", stdin);
      cin >> n >> st >> en;
      st--;
      en--;
      for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                  cin >> mass[i][j];
       BFS(st);
      return 0;
 }

6 1 1
0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 0 1
1 0 0 0 0 1
1 0 0 1 1 0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2011, 21:52     BFS. Путь из вершины в нее саму
Посмотрите здесь:

C++ Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине
C++ Функция bfs
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
C++ Обход графа в ширину - Breadth First Search (BFS)
Определить, какие вершины достижимы из заданной вершины S C++
Найти путь, соединяющий вершины a и b и не проходящий через заданное подмножество вершин V C++
C++ Найти кратчайший путь из вершины u в вершину v
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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