Diskuze: graf
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Zobrazeno 2 zpráv z 2.
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
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.
Zobrazeno 2 zpráv z 2.