{"algorithm":"bfs","about":["Breadth-first search keeps a queue of the vertices it has found but not visited yet. It takes the vertex at the front and puts each neighbor it hasn't seen at the back. So every vertex one edge from the start comes out before any vertex two edges away, and so on, one level at a time.","When every edge counts the same, that order gives the fewest edges from the start to each vertex, such as the fewest hops between two machines. gograph marks a vertex as seen when it joins the queue, so each one is visited once and the search costs O(V+E). Vertices the start can't reach are never visited.","The iterator returns one vertex for each call to Next, so a search can stop as soon as it finds what it needs. When edges have different weights, the fewest edges isn't the shortest route, and Closest-first or Dijkstra gives the real distances."],"template":{"id":"office-network","name":"Office network","description":"Switches and rooms in a four-team office, wired through a core switch.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"Core","x":512,"y":320},{"id":"Sales","x":320,"y":192},{"id":"Support","x":704,"y":192},{"id":"Ops","x":704,"y":448},{"id":"Dev","x":320,"y":448},{"id":"Uplink","x":512,"y":64},{"id":"Sales 1","x":128,"y":128},{"id":"Lab","x":160,"y":320},{"id":"Dev 1","x":128,"y":528},{"id":"Dev 2","x":512,"y":576},{"id":"Support 1","x":896,"y":112},{"id":"Shared","x":912,"y":304},{"id":"Ops 1","x":896,"y":544}],"edges":[{"from":"Core","to":"Sales"},{"from":"Core","to":"Support"},{"from":"Core","to":"Ops"},{"from":"Core","to":"Dev"},{"from":"Sales","to":"Uplink"},{"from":"Sales","to":"Sales 1"},{"from":"Sales","to":"Lab"},{"from":"Support","to":"Uplink"},{"from":"Support","to":"Support 1"},{"from":"Support","to":"Shared"},{"from":"Ops","to":"Shared"},{"from":"Ops","to":"Ops 1"},{"from":"Dev","to":"Lab"},{"from":"Dev","to":"Dev 1"},{"from":"Dev","to":"Dev 2"},{"from":"Lab","to":"Dev 1"}],"details":{"vertices":13,"edges":16,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.20512820512820512,"degree":{"min":1,"avg":2.4615384615384617,"max":4},"selfLoops":0,"components":1}},"problem":"Find every switch and room the core switch can reach, the ones fewest hops away first.","params":{"start":"Core"},"result":{"kind":"order","vertices":["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab","Support 1","Shared","Ops 1","Dev 1","Dev 2"]},"answer":"From Core, breadth-first visits 13 vertices: Core, Sales, Support, Ops, Dev, Uplink, Sales 1, Lab, Support 1, Shared, and so on to Dev 2.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Current","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Visited","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Used to reach a vertex","color":"#009E73","shape":"thick"}],"panels":[{"id":"queue","title":"Queue","kind":"list"},{"id":"order","title":"Visit order","kind":"list"}]},"steps":[{"say":"Start at Core. Put it in the queue.","ops":[{"v":"Core","state":"waiting"},{"panel":"queue","list":[{"key":"Core"}]}]},{"say":"Take Core from the front of the queue.","ops":[{"v":"Core","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Core"}]}]},{"say":"Add Sales, Support, Ops and Dev, the unseen neighbors of Core, to the back of the queue.","ops":[{"v":"Core","state":"done"},{"v":"Sales","state":"waiting"},{"e":["Core","Sales"],"state":"tree"},{"v":"Support","state":"waiting"},{"e":["Core","Support"],"state":"tree"},{"v":"Ops","state":"waiting"},{"e":["Core","Ops"],"state":"tree"},{"v":"Dev","state":"waiting"},{"e":["Core","Dev"],"state":"tree"},{"panel":"queue","list":[{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"}]}]},{"say":"Take Sales from the front of the queue.","ops":[{"v":"Sales","state":"current"},{"panel":"queue","list":[{"key":"Support"},{"key":"Ops"},{"key":"Dev"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"}]}]},{"say":"Add Uplink, Sales 1 and Lab, the unseen neighbors of Sales, to the back of the queue.","ops":[{"v":"Sales","state":"done"},{"v":"Uplink","state":"waiting"},{"e":["Sales","Uplink"],"state":"tree"},{"v":"Sales 1","state":"waiting"},{"e":["Sales","Sales 1"],"state":"tree"},{"v":"Lab","state":"waiting"},{"e":["Sales","Lab"],"state":"tree"},{"panel":"queue","list":[{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"}]}]},{"say":"Take Support from the front of the queue.","ops":[{"v":"Support","state":"current"},{"panel":"queue","list":[{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"}]}]},{"say":"Add Support 1 and Shared, the unseen neighbors of Support, to the back of the queue.","ops":[{"v":"Support","state":"done"},{"v":"Support 1","state":"waiting"},{"e":["Support","Support 1"],"state":"tree"},{"v":"Shared","state":"waiting"},{"e":["Support","Shared"],"state":"tree"},{"panel":"queue","list":[{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"}]}]},{"say":"Take Ops from the front of the queue.","ops":[{"v":"Ops","state":"current"},{"panel":"queue","list":[{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"}]}]},{"say":"Add Ops 1, the only unseen neighbor of Ops, to the back of the queue.","ops":[{"v":"Ops","state":"done"},{"v":"Ops 1","state":"waiting"},{"e":["Ops","Ops 1"],"state":"tree"},{"panel":"queue","list":[{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"}]}]},{"say":"Take Dev from the front of the queue.","ops":[{"v":"Dev","state":"current"},{"panel":"queue","list":[{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"}]}]},{"say":"Add Dev 1 and Dev 2, the unseen neighbors of Dev, to the back of the queue.","ops":[{"v":"Dev","state":"done"},{"v":"Dev 1","state":"waiting"},{"e":["Dev","Dev 1"],"state":"tree"},{"v":"Dev 2","state":"waiting"},{"e":["Dev","Dev 2"],"state":"tree"},{"panel":"queue","list":[{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]}]},{"say":"Take Uplink from the front of the queue.","ops":[{"v":"Uplink","state":"current"},{"panel":"queue","list":[{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"}]}]},{"say":"Uplink has no unseen neighbors.","ops":[{"v":"Uplink","state":"done"}]},{"say":"Take Sales 1 from the front of the queue.","ops":[{"v":"Sales 1","state":"current"},{"panel":"queue","list":[{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"}]}]},{"say":"Sales 1 has no unseen neighbors.","ops":[{"v":"Sales 1","state":"done"}]},{"say":"Take Lab from the front of the queue.","ops":[{"v":"Lab","state":"current"},{"panel":"queue","list":[{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"}]}]},{"say":"Lab has no unseen neighbors.","ops":[{"v":"Lab","state":"done"}]},{"say":"Take Support 1 from the front of the queue.","ops":[{"v":"Support 1","state":"current"},{"panel":"queue","list":[{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"}]}]},{"say":"Support 1 has no unseen neighbors.","ops":[{"v":"Support 1","state":"done"}]},{"say":"Take Shared from the front of the queue.","ops":[{"v":"Shared","state":"current"},{"panel":"queue","list":[{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"}]}]},{"say":"Shared has no unseen neighbors.","ops":[{"v":"Shared","state":"done"}]},{"say":"Take Ops 1 from the front of the queue.","ops":[{"v":"Ops 1","state":"current"},{"panel":"queue","list":[{"key":"Dev 1"},{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"}]}]},{"say":"Ops 1 has no unseen neighbors.","ops":[{"v":"Ops 1","state":"done"}]},{"say":"Take Dev 1 from the front of the queue.","ops":[{"v":"Dev 1","state":"current"},{"panel":"queue","list":[{"key":"Dev 2"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"}]}]},{"say":"Dev 1 has no unseen neighbors.","ops":[{"v":"Dev 1","state":"done"}]},{"say":"Take Dev 2 from the front of the queue.","ops":[{"v":"Dev 2","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Core"},{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"},{"key":"Support 1"},{"key":"Shared"},{"key":"Ops 1"},{"key":"Dev 1"},{"key":"Dev 2"}]}]},{"say":"Dev 2 has no unseen neighbors.","ops":[{"v":"Dev 2","state":"done"}]},{"say":"Done. Breadth-first reached 13 vertices from Core."}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"it, err := traverse.NewBreadthFirstIterator(g, \"Core\")\nif err != nil {\n\treturn err\n}\nfor it.HasNext() {\n\tfmt.Println(it.Next().Label())\n}"}