• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

C++ przeszukanie grafu - łatwa modyfikacja

0 głosów
256 wizyt
pytanie zadane 21 października 2015 w C i C++ przez szmq Pasjonat (22,820 p.)
edycja 22 października 2015 przez szmq

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

 

2 odpowiedzi

0 głosów
odpowiedź 22 października 2015 przez szmq Pasjonat (22,820 p.)
Odświeżam temat :)
–1 głos
odpowiedź 21 października 2015 przez niezalogowany

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).

komentarz 21 października 2015 przez szmq Pasjonat (22,820 p.)

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

  }

 

komentarz 21 października 2015 przez szmq Pasjonat (22,820 p.)
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.
komentarz 21 października 2015 przez niezalogowany
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ć?
komentarz 21 października 2015 przez szmq Pasjonat (22,820 p.)

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

Podobne pytania

0 głosów
0 odpowiedzi 93 wizyt
+1 głos
1 odpowiedź 986 wizyt
pytanie zadane 11 maja 2015 w C i C++ przez keresmi Użytkownik (770 p.)
0 głosów
1 odpowiedź 169 wizyt
pytanie zadane 26 kwietnia 2015 w C i C++ przez keresmi Użytkownik (770 p.)

88,720 zapytań

137,331 odpowiedzi

306,818 komentarzy

58,907 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...