{"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.","traverse.BFS and traverse.BFSWithDepth return an iter.Seq, so a range loop can break as soon as it finds what it needs, and BFSWithDepth gives each vertex with its number of edges from the start. path.BFSPaths runs the same search and keeps the edge that first found each vertex, so PathTo on its result gives a route with the fewest edges to any vertex, start first, and false for one out of reach. When edges have different weights, the fewest edges isn't the shortest route, and Closest-first or Dijkstra gives the real distances."],"template":{"id":"home-network","name":"Home network","description":"A router and the devices connected to it.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"Router","x":500,"y":320},{"id":"Laptop","x":260,"y":180},{"id":"Phone","x":740,"y":180},{"id":"TV","x":740,"y":480},{"id":"Printer","x":260,"y":480},{"id":"Speaker","x":900,"y":640}],"edges":[{"from":"Router","to":"Laptop"},{"from":"Router","to":"Phone"},{"from":"Router","to":"TV"},{"from":"Router","to":"Printer"},{"from":"Laptop","to":"Printer"},{"from":"TV","to":"Speaker"}],"details":{"vertices":6,"edges":6,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.4,"degree":{"min":1,"avg":2,"max":4},"selfLoops":0,"components":1}},"problem":"Find every device the router can reach, the ones a single hop away first, as a network scan would.","params":{"start":"Router"},"result":{"kind":"order","vertices":["Router","Laptop","Phone","TV","Printer","Speaker"]},"answer":"From Router, breadth-first visits 6 vertices: Router, Laptop, Phone, TV, Printer and Speaker.","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 Router. Put it in the queue.","ops":[{"v":"Router","state":"waiting"},{"panel":"queue","list":[{"key":"Router"}]}]},{"say":"Take Router from the front of the queue.","ops":[{"v":"Router","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Router"}]}]},{"say":"Add Laptop, Phone, TV and Printer, the unseen neighbors of Router, to the back of the queue.","ops":[{"v":"Router","state":"done"},{"v":"Laptop","state":"waiting"},{"e":["Router","Laptop"],"state":"tree"},{"v":"Phone","state":"waiting"},{"e":["Router","Phone"],"state":"tree"},{"v":"TV","state":"waiting"},{"e":["Router","TV"],"state":"tree"},{"v":"Printer","state":"waiting"},{"e":["Router","Printer"],"state":"tree"},{"panel":"queue","list":[{"key":"Laptop"},{"key":"Phone"},{"key":"TV"},{"key":"Printer"}]}]},{"say":"Take Laptop from the front of the queue.","ops":[{"v":"Laptop","state":"current"},{"panel":"queue","list":[{"key":"Phone"},{"key":"TV"},{"key":"Printer"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"}]}]},{"say":"Laptop has no unseen neighbors.","ops":[{"v":"Laptop","state":"done"}]},{"say":"Take Phone from the front of the queue.","ops":[{"v":"Phone","state":"current"},{"panel":"queue","list":[{"key":"TV"},{"key":"Printer"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Phone"}]}]},{"say":"Phone has no unseen neighbors.","ops":[{"v":"Phone","state":"done"}]},{"say":"Take TV from the front of the queue.","ops":[{"v":"TV","state":"current"},{"panel":"queue","list":[{"key":"Printer"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Phone"},{"key":"TV"}]}]},{"say":"Add Speaker, the only unseen neighbor of TV, to the back of the queue.","ops":[{"v":"TV","state":"done"},{"v":"Speaker","state":"waiting"},{"e":["TV","Speaker"],"state":"tree"},{"panel":"queue","list":[{"key":"Printer"},{"key":"Speaker"}]}]},{"say":"Take Printer from the front of the queue.","ops":[{"v":"Printer","state":"current"},{"panel":"queue","list":[{"key":"Speaker"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Phone"},{"key":"TV"},{"key":"Printer"}]}]},{"say":"Printer has no unseen neighbors.","ops":[{"v":"Printer","state":"done"}]},{"say":"Take Speaker from the front of the queue.","ops":[{"v":"Speaker","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Phone"},{"key":"TV"},{"key":"Printer"},{"key":"Speaker"}]}]},{"say":"Speaker has no unseen neighbors.","ops":[{"v":"Speaker","state":"done"}]},{"say":"Done. Breadth-first reached 6 vertices from Router."}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its order is checked against traverse.BFS, and the route it draws to each vertex against PathTo of path.BFSPaths, on every start.","snippet":"for v, depth := range traverse.BFSWithDepth(g, \"Router\") {\n\tfmt.Println(v.Label(), depth)\n}\n\npaths, err := path.BFSPaths(g, \"Router\")\nif err != nil {\n\treturn err\n}\nroute, _ := paths.PathTo(\"Speaker\")\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
