Jump to content
Please Use CODE Tags

how is a breadth first search performed on a graph?

Mrcrysis2000
By Mrcrysis2000
in Programming
 Share
Go to solution Solved by DavidTheWin,

(Imagine there are lines below)

 

                 A

 

   B           C               D

 

D E        F G H            I

 

Breadth first means you first look at all the child nodes of the parent node before looking at any child nodes of the child nodes. If A is the parent node then breadth first means examining B C and D first then DE FGH and I in that order.

 

Depth first search would be exhausting all child nodes of one node before continuing to the others, e.g. here it would look at D first (A->B->D) then E then B then C F G H D I A

 

 

Basically, at a high level, it expands out like a pool of water and it stops whenever it gets to its target, it just moves one step outward, dumbly.

 

Visualized: https://qiao.github.io/PathFinding.js/visual/

 
This is a very particular type of graph. The case I listed is a more general form.
Posted

Hi Guys my exam is like 2 days away and i feel a million times better about it thanks to you guys!

 

There just one question stumping me again.

 

how is a breadth first search performed on a graph?

 

So some help on this and i feel like im set to do well in this one :)

 

Thanks guys! 

 

 

Link to comment
Share on other sites
Link to post
Share on other sites
Posted

Basically, at a high level, it expands out like a pool of water and it stops whenever it gets to its target, it just moves one step outward, dumbly.

 

Visualized: https://qiao.github.io/PathFinding.js/visual/

Ensure a job for life: https://github.com/Droogans/unmaintainable-code

Actual comment I found in legacy code: // WARNING! SQL injection here!

Link to comment
Share on other sites
Link to post
Share on other sites
Posted
  • Solution

(Imagine there are lines below)

 

                 A

 

   B           C               D

 

D E        F G H            I

 

Breadth first means you first look at all the child nodes of the parent node before looking at any child nodes of the child nodes. If A is the parent node then breadth first means examining B C and D first then DE FGH and I in that order.

 

Depth first search would be exhausting all child nodes of one node before continuing to the others, e.g. here it would look at D first (A->B->D) then E then B then C F G H D I A

 

 

Basically, at a high level, it expands out like a pool of water and it stops whenever it gets to its target, it just moves one step outward, dumbly.

 

Visualized: https://qiao.github.io/PathFinding.js/visual/

 
This is a very particular type of graph. The case I listed is a more general form.
Link to comment
Share on other sites
Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share
Go to topic listing Programming

×