Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: graf

Aktivity
Avatar
style
Člen
Avatar
style:7.10.2016 23:51

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.10.2016 23:51
Avatar
Martin Dráb
Tvůrce
Avatar
Martin Dráb:8.10.2016 0:44

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.10.2016 0:44
Nahoru Odpovědět
8.10.2016 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.