Avatar
style
Člen
Avatar
style:

Ahoj , snazim sa najst nejaky tutorial na impelentaciu grafov v c++ a bfs v nom. No nemozem nic obstojne najst. Nevie niekto i nejakom dobrom tutoriali?

Dik

 
Odpovědět 7. října 23:51
Avatar
Martin Dráb
Redaktor
Avatar
Martin Dráb:

Jednoduchá implementace (s raw pointery, které případně můžeš nahradit smart pointery).

class Vertex {
public:
  // true <=> byl vrchon prozkouman v ramci BFS
  bool marked;
  // mnozina sousedu (koncu hran z vrcolu vedoucich)
  std::set<Vertex *> neighbors;
  Vertex() : marked(false) {}
}

Pokud máme vytvořený graf a zadaný vrchol startingVertex, může BFS vypadat třeba následovně:

std::list<Vertex *> queue;
// Nejprve prozkoumame startovni vrchol
queue.push_back(startingVertex);
while (!queue.empty()) {
  v = queue.front();
  queue.pop_front();
  // Zde muezeme provest nejakou akci s v, na ktere jsme narazili v ramci BFS
  v->marked = true;
  // A pridame do fronty jeho sousedy, ktere jsme jeste neprozkoumali
  for (auto n : v->neighbors) {
    if (!n->marked)
      queue->push_back(n);
  }
}

Toto BFS bude fungovat jen na souvisle grafy. Pokud potřebuješ, aby běželo dobře i na grafy s více komponentami souvislosti, tak si někde musíš paamtovat všechny vrcholy, které ještě nebyly označeny. Dokud nějaké takové existují, vždy od některého z nich začneš další BFS.

Po dokončení BFS bys měl zrušit jejich označení. Samozřejmě je tu také otázka, zda označení vrcholů uchovávat v instancích vrcholů, ale to záleží dost na tom, co přesně potřebuje udělat.

Editováno 8. října 0:44
Nahoru Odpovědět 8. října 0:44
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.