Datastrukturer och algoritmer BFS och DFS
Hej,
Jag får inte till det med BFS på följande uppgift:
DFS får jag rätt på:
Hur löser jag det för BFS?
Mitt försök:
Ett tag sen du postade så du kanske har löst det nu, men ...
Tricket med BFS är att så fort du kommer till en nod lägger du till alla dess grannar till din kö (om de inte redan har besökts).
Så, när du börjar med nod 0 har den två grannar, 3 och 1, så vi lägger till dem till kön. Kön består av 3, 1.
Vi börjar beta av kön, och tar det första elementet (3). Den noden har grannarna 4 och 2, så vi lägger direkt till båda två innan vi går vidare. Kön består nu av 1, 4 och 2 (vi har ju precis betat av 3:an).
Längst fram i kön är nu 1:an, så det blir nästa att beta av, osv ...
Tegelhus skrev:Ett tag sen du postade så du kanske har löst det nu, men ...
Tricket med BFS är att så fort du kommer till en nod lägger du till alla dess grannar till din kö (om de inte redan har besökts).
Så, när du börjar med nod 0 har den två grannar, 3 och 1, så vi lägger till dem till kön. Kön består av 3, 1.
Vi börjar beta av kön, och tar det första elementet (3). Den noden har grannarna 4 och 2, så vi lägger direkt till båda två innan vi går vidare. Kön består nu av 1, 4 och 2 (vi har ju precis betat av 3:an).
Längst fram i kön är nu 1:an, så det blir nästa att beta av, osv ...
Tack för förklaringen!
