SaXior Temat założony przez niniejszego użytkownika |
Algorytm BFS - graf » 2016-02-17 11:30:17 Witam.
Jak rozwiązać to zadanie:
W wyniku wykonania algorytmu BFS węzły grafu G:: 1->2;;2->1,3,5,6;;3->4,6;;4->3,8;;5->1,6;;6->7;;7->2,6,8;;
zostaną odwiedzone w następującej kolejności: 5..
Jak to się rozwiązuje ? |
|
Monika90 |
» 2016-02-17 12:10:59 W C++ mamy do tego bardzo fajne biblioteki #include <vector>
#include <iostream>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/breadth_first_search.hpp>
typedef std::vector < std::vector < int >> Graph;
struct PrintVertex
: boost::default_bfs_visitor
{
void finish_vertex( int v, const Graph & ) { std::cout << v << ' '; }
};
int main()
{
Graph g = { { }, { 2 }, { 1, 3, 5, 6 }, { 4, 6 }, { 3, 8 }, { 1, 6 }, { 7 }, { 2, 6, 8 }, { } };
boost::breadth_first_search( g, 5, boost::visitor( PrintVertex() ) );
}
i oto wynik
5 1 6 2 7 3 8 4
|
|
SaXior Temat założony przez niniejszego użytkownika |
» 2016-02-17 12:17:58 Dzięki, wytłumaczysz jeszcze dlaczego tak? :) |
|
Monika90 |
» 2016-02-17 12:58:28 Zaczynamy od wierzchołka numer 5, (bo tak jest napisane w treści zadania): 5 Z piątki da się przejść do jedynki i szóstki, więc dopisujemy do wyniku: 1 6 z 1 da się przejść do 2, a z 6 do 7, dopisujemy: 2 7 Z 2 można przejść do 1, 3, 5 i 6, ale 1, 5 i 6 już było, wiec dopisujemy tylko 3. Z 7 można przejść do 2, 6, 8, ale 2 i 6 odpada, bo już było: 3 8 Z 3 można przejść do 4 i 6, więc dopisujemy 4, a z 8 nigdzie nie można przejść: 4 Z czwórki można przejść tylko do wierzchołków, które były już odwiedzone, a zatem to już jest koniec. |
|
SaXior Temat założony przez niniejszego użytkownika |
» 2016-02-17 13:08:11 Jeszcze raz wielkie dzięki! |
|
| « 1 » |