C++ przeszukanie grafu - łatwa modyfikacja

Question

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ść... Fajnie byłoby gdyby ktos pomógł  :) A może jakoś do funkcji wysłać ten wskaźnik, ale jak później niby zrobie rekurencje.. :)

Oczywiścię za dobre pokazanie drogi daje naj :)
 

//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;
}

 

Answer 1

Odświeżam temat :)

Answer 2

Dobra, mam chwilę i na star kilka uwag:

Po pierwsze: napisz jeszcze raz to co chcesz osiągnąć, ale bez używania nazw obiektów z twojego kodu (tak jakbyś przedstawiał problem algorytmiczny, tzn w opisie określasz czym są dla ciebie konkretne zmienne), np

a, b - wierzchołki grafu; zadaniem funkcji w_glab() jest ...

Po drugie: Opisz czym są twoje zmienne w kodzie (np "pocz" zgaduje, że początek, ale czego?)

Po trzecie: polskie nazewnictwo jest słodkie, ale zazwyczaj nie oddaje to czym faktycznie jest np zmienna, nawet tobie byłoby łatwiej szukać pomocy w internecie gdybyś kod miał po angielsku (nie musiałbyś sobie zawsze tłumaczyć fragmentów kodu).

Comments

jest opisane, np:
 

cout<<"Podaj wierzchołek, z którego zaczynamy przeszukiwanie: ";

cin>>pocz;

cout<<"Podaj liczbę wierzcholków w grafie: ";

  cin>>n;

  cout<<"Podaj liczbę połączeń w grafie: ";

  cin>>pol;

//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);

  }

 

---

2. To nie moj kod wiec nie zmienialem nazewnictwa. Na topie masz komentarz:

//www.algorytm.edu.pl

3. Po prostu wyłwołać funkcje w_glab dla iterowanej wartosci zmiennej poczatek.

---

1. opis bez kodu, a podałeś kod

2. w tej wersji co mi dałeś na PW nie było źródła, a tutaj nie patrzylem dokladanie

3. Co przez to rozumiesz? Jak wyobrażasz sobie działanie tego? Podajesz do funkcji argument "poczatek" i za co ta zmienna ma odpowiadać (narysuj przykładowy graf i oznacz jakoś element "początek")

Naszło mnie jeszcze pytanie, na jakim grafie chcesz pracować?

---

Ogólnie to później wypisuje połączenia względem początku czyli od którego wierzchołka ma przeszukiwać graf(DFS). Chciałbym dla różnych wierzcholków. 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 ;/