BFS wypisywane w postaci listy sąsiedztwa

0

Cześć napisałem algorytm Przeszukiwania grafu (BFS) i zażyczyłem sobie, aby wypisywane to było w liście sąsiedztwa, niestety coś poszło nie tak i za bardzo nie rozumiem co "go" boli

#include <iostream>

using namespace std;

struct kolejka {
    kolejka *next;
    int data;
};

struct lista
{
  lista *next;
  int value;
};

int n;      //liczba wierzcholkow
int *d;     //tablica odleglosci
int *p;     //tablica poprzednikow
char *kolor;//tablica kolorow wierzcholkow

lista **A;
lista *c,*r;


void BFS(int s) {
    int i;
    kolejka *q,*head,*tail;
    kolor[s] = 'G'; //szary kolor GREY
    d[s]=0;
    p[s]=-1;
    //umieszczamy s w kolejce
    q = new kolejka;
    q->next = NULL;
    q->data = s;
    head=tail=q;

    while(head) {
        s = head->data; //odczytujemy s z kolejki
        for(i=0;i<n;i++)
                //dla ka¿dego sasiada s o kolorze bia³ym
            if((A[s][i]==1) && kolor[i]=='W') {
                q=new kolejka;
                q->next = NULL;
                q->data = i;
                if(!tail) head = q;
                else tail->next = q;
                tail = q;
                d[i] = d[s]+1; //zwieksz odleglosc od s o 1
                p[i] = s;
                kolor[i] = 'G'; //zamaluj na szaro
            }
        q=head;
        head=head->next;
        if(!head) tail = NULL;
        delete q;
        cout.width(3);
        cout << s;
        kolor[s] = 'B'; //BLACK - koniec przetwarzania wierzcholka
    }
}

int main() {



  cin >> n >> m;	// Czytamy liczbê wierzcho³ków i krawêdzi
  A = new lista * [n]; // Tworzymy tablicê list s¹siedztwa

  // Tablicê wype³niamy pustymi listami
  for(i = 0; i < n; i++) A[i] = NULL;

  // Odczytujemy kolejne definicje krawêdzi
  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;	// Wierzcho³ek startowy i koñcowy krawêdzi
    c = new lista;		// Tworzymy nowy element
    c->value = v2;      // Numerujemy go jako v2
    c->next = A[v1];    // Dodajemy go na pocz¹tek listy A[v1]
    A[v1] = c;
  }

  cout << endl;

  // Wypisujemy zawartoœæ tablicy list s¹siedztwa
  for(i = 0; i < n; i++)
  {
    cout << "A[" << i << "] =";
    c = A[i];
    while(c)
    {
      cout.width(3);
	  cout << c->value;

      c = c->next;
    }
    cout << endl;
  }






    cout << endl;




    BFS(1);

    cout << endl;
    //kolory
    cout << "KOLORY:" << endl;
    for(i=0;i<n;i++) cout << kolor[i] << " ";
    cout <<endl;

    cout << "ODLEGLOSCI" << endl;
    for(i=0;i<n;i++) cout << d[i] << " ";
    cout << endl;

    cout << "POPRZEDNICY" << endl;
    for(i=0;i<n;i++) cout << p[i] << " ";
    cout << endl;

    //czyszczenie pamieci
    delete [] kolor;
    delete [] p;
    delete [] d;
 // Usuwamy tablicê list s¹siedztwa
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;

    cout << endl;
    return 0;
}

Wyskakuję błąd w linijce 40

error: no match for 'operator==' (operand types are 'lista' and 'int')|
1

Kompilator wszystko opisał.
A[s][i] jest typu lista (w końcu podwójna dereferencja podwójnego wskaźnika), a 1 to int. W kod nie chce mi się wczytywać, bo

  • zmienne globalne
  • magiczne nazwy zmiennych
  • napchane wszystko do jednej funkcji
  • błędu się nie da odtworzyć bo nie znamy danych wejściowych
  • użyty język to C nawet nie z klasami, a z std::cout.
0

No a co to by miało robić: (A[s][i]==1)?

2

Zmienne globalne, czemu algorytm nie bierze grafu? Pseudokod BFS:

def BFS(G, s):
    Put s in data_struct # for BFS data_struct is LIFO
    while data_struct is not empty:
        v = pop data_struct
        if v is unmarked:
            mark v
            record parent v # to get shortest paths tree from s
            for neighborhood w of v:
                put w into data_struct

Zaimplementuj sobie graf, przy użyciu std::vector, Patrz też tutaj: https://link.springer.com/content/pdf/10.1007%2F978-3-319-72547-5.pdf, acha, w STL jest LIFO.

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