Nie działający BFS

0

Witam, mam napisać program który z macierzy sąsiedztwa wypisze wszystkie połączenia między wierzchołkami stosując algorytm BFS. Niestety wyniki programu są błędne i nie potrafię powiedzieć czemu, bo wydaje mi się że wszystko powinno być ok.

#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

unsigned const  int N=12; // ilosc wierzcholkow
bool tab[N][N]; // tablica z macierza sasiedztwa
int odwiedzone[N];
queue<int> kolejka;

void wczytaj()
{
    ifstream plik ("macierz_sasiedztwa.txt");
    for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
                plik >> tab[i][j] ;
    plik.close();
}

void BFS(int i)
{
    kolejka.push(i);
    odwiedzone[i]=1;
    int s;
     while(!kolejka.empty())
     {
         //pobierz z kolejki element który jest pierwszy
         s=kolejka.front();
         kolejka.pop();
         odwiedzone[s] = 1; //oznacza ten wierzchołek jako odwiedzony
         for(int k=0; k<N; k++) //wykonuj pętlę tyle razy ile jest wierzchołków
                 //jeśli punkt sąsiedztwa ustawiony na 1
                 //to znaleziono połączenie między wierzchołkami
                 if (tab[s][k]==1)
                 {
                    cout << s+1 << "---->" << k+1 << endl;
                      if(odwiedzone[k]==0) //sprawdź kolejny wierzchołek jeśli nie był dotąd odwiedzany
                      {  
                           odwiedzone[k]=1; //oznacz jako odwiedzony
                           kolejka.push(k);//wstaw do kolejki
                      }
                 }
     }
} 
int main()
{
    wczytaj();
    for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
                   { cout<<tab[i][j]<<" "; if(j==N-1) cout<<endl;}
    for(int i=0;i<N;i++) odwiedzone[i]=0;
    BFS(0);
 
    system("PAUSE");
    return 0;
}

Macierz sąsiedztwa w załączniku

Na pierwszy rzut oka widać, że coś jest nie tak bo 1 nie jest połączone z dwa i tak dalej. Za wszelką pomoc będę bardzo wdzięczny

1

Dziwne, u mnie wszystko działa :D
Początek wyniku u mnie:

1---->2
1---->6
1---->10
2---->5
2---->7
2---->9
2---->11
6---->4
6---->8
6---->12

I zdaje mi się, że to jest dobrze (np. jest połączenie z 1 do 2, bo wartość macierzy (1, 2) ma 1).

0

Dobra, moja głupota mnie czasami przeraża :D Myliłem wiersze z kolumnami, temat do zamknięcia czy wręcz usunięcia

1 użytkowników online, w tym zalogowanych: 0, gości: 1