C++ Przeszukiwanie grafu.

Mam pytanie.. pisze programik na grafach. chciałbym to raczej zrobić tak, że wczytuje w pętli a i b tak jak tutaj, ale później robię pętle dla pocz += 1; i wielokrotnie wykonuje funkcje w_glab na tym samym niezmienionym wskazniku. Nie wiem jak to zrobić.. jakieś kopie tych wskaźników czy przechowywać jakoś a i b ale jak się poźniej do tego odnieść, a może jakoś do funkcji wysłać ten wskaźnik, ale jak później niby zrobie rekurencje.. :)

Ogólnie to później wypisuje połączenia względem początku(zmienna pocz) czyli od którego wierzchołka ma przeszukiwać graf(DFS). Chciałbym dla różnych wierzcholków zacząć przeszukiwanie grafu. Niekoniecznie zmieniać zmienną pocz w kodzie tylko wykonwać pętlę względem n(czyli liczbie wierzchołków).

czyli:

for(int i = 1; i<n+1; i++) {
 
pocz += 1;
 
w_glab(pocz);
 
} 

Lecz nie mogę tak zrobić ponieważ za pierwszym obiegiem wartości na które wskazuje wskaźnik są zmienione ;/

cały kod:

//www.algorytm.edu.pl
#include<iostream>
#include<vector>
using namespace std;
  
struct wierzcholki{
  //połączenia wychodzące z danego wierzchołka
  vector <unsigned int> polaczenia; 
  //okresla, czy wierzchołek został odwiedzony
  bool odwiedzony; 
  //dodatkowe dane dla danego wierzchołka
  //........................
  //........................
}*w;
  
void w_glab(int k)
{
  cout<<"Odwiedzono "<<k<<" wierzcholek\n";
  w[k].odwiedzony = 1;
  for(int i=0; i<w[k].polaczenia.size(); i++)
  //jesli wierzchołek, do którego chcemy przejsć nie został
  //jeszcze odwiedzony
    if(!w[w[k].polaczenia[i]].odwiedzony) 
    //to przechodzimy do niego
      w_glab(w[k].polaczenia[i]); 
}
  
int main()
{
  unsigned int n, pol, pocz, a, b;
  cout<<"Podaj liczbę wierzcholków w grafie: ";
  cin>>n;
  cout<<"Podaj liczbę połączeń w grafie: ";
  cin>>pol;
  cout<<"Podaj wierzchołek, z którego zaczynamy przeszukiwanie: ";
  cin>>pocz;
  
  w = new wierzcholki[n+1];
  
  cout<<"Podaj kolejne połączenia wierzchołków: \n";
  //wczytanie połączeń grafu
  for(int i=0; i<pol; i++)
  {
    cin>>a>>b;
    cout<<a<<" <--> "<<b<<endl;
    //tworzymy połączenie a --> b
    w[a].polaczenia.push_back(b);
    //tworzymy połączenie b --> a
    w[b].polaczenia.push_back(a);
  }
  cout<<"\nOdwiedzano wierzchołki w następującej kolejnosci:\n";
  w_glab(pocz);
  
  delete [] w;
  
  cin.ignore();
  cin.get();
  
  return 0;
} 

Strasznie zagmatwany opis. Z tego co udało mi się wydedukować z kodu:

1. Dlaczego pocz += 1? Czy masz zagwarantowane, że pocz będzie najmniejszym numerem na początku? I że każda liczba od pocz do pocz+n będzie poprawnym wierzchołkiem?
2. wartości na które wskazuje wskaźnik są zmienione - jakie wartości? Jedyne co zmieniasz to flagę czy wierzchołek został odwiedzony, co jest akurat dobre, bo nie chcesz odwiedzić ponownie tych samych wierzchołków gdy zmieniasz punkt początkowy.

No i używaj vector zamiast

w = new wierzcholki[n+1];

I nazwij zmienne sensownie, a nie n, w, a, b, pol.

1. Tak, mam zagwarantowane :) pocz = 1 jest dla pierwszego wierzchołka.
2. Tak, flaga jest zmieniona, ale w swoim zmieniam jeszcze w funkcji w_glab() polaczenia czyli:
   w[k].polaczenia.pop_back();
3. dlaczego powinienem używać vector zamiast:
   w = new wierzcholki[n+1];
   Przecież są wydajniejsze.
4. Nie zmieniałem nazwy ze względu na to, że kod nie jest mój:
   //www.algorytm.edu.pl (1 komentarz)

szmq napisał(a):

2. Tak, flaga jest zmieniona, ale w swoim zmieniam jeszcze w funkcji w_glab() polaczenia czyli:
   w[k].polaczenia.pop_back();
   Po co? Odwiedzasz wszystkich sąsiadów danego wierzchołka, po co usuwasz te połączenia?

3. dlaczego powinienem używać vector zamiast:
   w = new wierzcholki[n+1];
   Przecież są wydajniejsze.
   Tak? Pokaż mi dowód to uwierzę.
   Natomiast faktem jest, że vector jest wygodniejszy i bezpieczniejszy w użyciu. Dlaczego polaczenia to vector a nie tablica dynamiczna?

 void w_glab(int k)
{
  //cout<<"Odwiedzono "<<k<<" wierzcholek\n";
  sprawdz += 1;
  w[k].odwiedzony = 1;
  for(int i=0; i<w[k].polaczenia.size(); i++)
  //jesli wierzchołek, do którego chcemy przejsć nie został
  //jeszcze odwiedzony

    if(!w[w[k].polaczenia[i]].odwiedzony){
        w[k].polaczenia.pop_back();
      w_glab(w[k].polaczenia[i]);
    }
}

Po prostu gdy nie będzie już kolejnego połączenia np w sytuacji gdy nie przejdę całego grafu czyli:
sprawdz != n
to wypisze konkretną informację.

Dlaczego polaczenia to vector a nie tablica dynamiczna?
Nie wiem, musiałbym już spytać autora kodu. Teraz z tego co czytam w internecie to faktycznie raczej powinno się używać vector dlatego też z takich powodów o których mówiłeś

Tyle że usuwanie wierzchołka nie dość, że jest zbędne to jeszcze wprowadza buga. Przecież odwiedzasz tych sąsiądów od początku, czyli

polaczenia[0]
polaczenia[1]
...

a usuwasz od końca, czyli wcale nie tego którego odwiedziłeś.

Poza tym nadal nie widzę, czemu musisz cokolwiek usuwać. Masz powiedzmy 100 sąsiadów wierzchołka X to odwiedzasz wszystkich 100 i kończysz w_glab(X), cześć do widzenia.

Tak, ale chce zrobić to tak: Użytkownik wprowadza dane czyli ilość wierzchołków i połączenia. Następnie po każdym wierzchołku po kolei sprawdza czy przejdzie graf: tzn idzie w głąb dla każdego połączenia wychodzącego od wierzchołka X i jeżeli skończą się wierzchołki nie cofam się się do wierzchołka, z którego ostatnio przyszedłem czy jakiegokolwiek innego i nie wchodzę z tego miejsca do następnego nieodwiedzonego (jeśli taki jest) tylko po prostu zapisuje informację o niepowodzeniu.

Inaczej mówiąc chcesz sprawdzić czy z każdego wierzchołka da się dojść do każdego innego wierzchołka?
Inaczej mówiąc chcesz sprawdzić czy wszystkie wierzchołki tworzą spójną składową?
Inaczej mówiąc chcesz sprawdzić czy graf jest spójny?

Jeśli odpowiedź brzmi TAK to robisz DFS raz dla dowolnego wierzchołka. Jeśli liczba odwiedzonych wierzchołków jest mniejsza niż liczba wszystkich to znaczy że nie, graf nie jest spójny.

Tak, ale chcę sprawdzić dla każdego wierzchołka po kolei i wypisać odpowiednią wartość na wyjściu czyli np
pocz1 = false
pocz2 = true

Pomyśl: jeśli z jednego wierzchołka nie da się dojść do każdego innego to czy jest możliwe, żeby z jakiegoś innego wierzchołka da się dojść do wszystkich?

Tak. To zależy od połączeń tzw ułożenia grafu.

Ciekawe. Pokaż mi taki przykład to uwierzę.

Bo jak dla mnie to się nie da. Nazwijmy pierwszy wierzchołek, z którego nie da się dojść do wszystkich X. Nazwijmy drugi wierzchołek, z którego da się dojść do wszystkich B. Gdyby taka sytuacja istniała, to można dojść z X do B (bo z B da się dojść do każdego, w szczególności do X). A to oznacza, że z X można dojść do każdego, wystarczy iść najpierw do B a z B już można do każdego. Sprzeczność.

Eh... chyba się nie rozumiemy.. patrz na graf np:
https://computersciencesource.files.wordpress.com/2010/05/dfs_1.png

Z punktu D tak: DBEAC
z punktu B nie przejdziesz ponieważ gdy pojdziesz w strone D nie mozesz sie wrocic wiec AEC nie przejdziesz i odwrotnie to samo.

Zależy mi na takim algorytmie

@szmq Twój problem polega na tym, że myślisz o grafie skierowanym a implementujesz i pokazujesz na obrazku graf nieskierowany. Poczytaj sobie o różnicach między nimi.

no tak, już rozumiem :) graf nieskierowany. Tylko tak myślę czego i co powinienem użyć żeby rozwiązać mój problem ;/