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