{"algorithm":"dfs","about":["Depth-first search goes from the vertex it is at to a neighbor it hasn't seen, and from there to the next, as deep as it can. The vertices it has gone through form the search path. When the vertex at the end of the path has no neighbor left to try, the search finishes it and backs up one vertex. Each vertex gets a discovery time when the search enters it and a finish time when it leaves, and the times of a vertex nest inside the times of the vertex it was reached from, like parentheses.","traverse.DFSEvents reports each step as an event and sorts every edge it meets into four kinds. A tree edge leads to a new vertex. A back edge leads to a vertex still on the search path, so it closes a loop. A forward edge leads to a finished vertex discovered after the one the search is at, a descendant reached another way. A cross edge leads to a finished vertex discovered before it, in another branch. An undirected graph has only tree and back edges, and the edge back to the vertex a vertex was reached from is the tree edge itself, not a back edge.","The search costs O(V+E). Use it to find everything a vertex can reach, to explore a maze one branch at a time, or for the back edges, which are how connectivity.FindCycle and the topological sorts by finish time work. The path it follows is rarely the shortest one. For the fewest edges, use Breadth-first."],"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 by following one cable as far as it goes before going back.","params":{"start":"Router"},"result":{"kind":"order","vertices":["Router","Laptop","Printer","Phone","TV","Speaker"]},"answer":"From Router, depth-first visits 6 vertices: Router, Laptop, Printer, Phone, TV and Speaker. It met 5 tree edges and 1 back edge.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"current","label":"On the search path","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Finished","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Tree edge, to a new vertex","color":"#009E73","shape":"thick"},{"id":"back","label":"Back edge, to the search path","color":"#D55E00","shape":"dashed"},{"id":"forward","label":"Forward edge, to a finished descendant","color":"#56B4E9","shape":"dotted"},{"id":"cross","label":"Cross edge, to another branch","color":"#E69F00","shape":"line"}],"panels":[{"id":"times","title":"Discovered / finished","kind":"table"},{"id":"path","title":"Search path, start first","kind":"list"},{"id":"order","title":"Discovery order","kind":"list"}]},"steps":[{"say":"Start at Router. Discover it at time 1, and it begins the search path.","ops":[{"v":"Router","state":"current"},{"panel":"times","set":{"Router":"1"}},{"panel":"path","list":[{"key":"Router"}]},{"panel":"order","list":[{"key":"Router"}]}]},{"say":"Router to Laptop leads to a new vertex, so it is a tree edge. Discover Laptop at time 2, and it joins the search path.","ops":[{"e":["Router","Laptop"],"state":"tree"},{"v":"Laptop","state":"current"},{"panel":"times","set":{"Laptop":"2"}},{"panel":"path","list":[{"key":"Router"},{"key":"Laptop"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"}]}]},{"say":"Laptop to Router leads to Router, which is still on the search path, but it is the tree edge Laptop was discovered by, seen from the other end. On an undirected graph that isn't a back edge, so the search skips it, here and every time it comes up."},{"say":"Laptop to Printer leads to a new vertex, so it is a tree edge. Discover Printer at time 3, and it joins the search path.","ops":[{"e":["Laptop","Printer"],"state":"tree"},{"v":"Printer","state":"current"},{"panel":"times","set":{"Printer":"3"}},{"panel":"path","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Printer"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Printer"}]}]},{"say":"Printer to Router leads to Router, which is still on the search path, so it is a back edge. The path from Router to Printer and this edge make a loop.","ops":[{"e":["Printer","Router"],"state":"back"}]},{"say":"Printer has no neighbor left to try. Finish it at time 4 and back up to Laptop.","ops":[{"v":"Printer","state":"done"},{"panel":"times","set":{"Printer":"3/4"}},{"panel":"path","list":[{"key":"Router"},{"key":"Laptop"}]}]},{"say":"Laptop has no neighbor left to try. Finish it at time 5 and back up to Router.","ops":[{"v":"Laptop","state":"done"},{"panel":"times","set":{"Laptop":"2/5"}},{"panel":"path","list":[{"key":"Router"}]}]},{"say":"Router to Phone leads to a new vertex, so it is a tree edge. Discover Phone at time 6, and it joins the search path.","ops":[{"e":["Router","Phone"],"state":"tree"},{"v":"Phone","state":"current"},{"panel":"times","set":{"Phone":"6"}},{"panel":"path","list":[{"key":"Router"},{"key":"Phone"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Printer"},{"key":"Phone"}]}]},{"say":"Phone has no neighbor left to try. Finish it at time 7 and back up to Router.","ops":[{"v":"Phone","state":"done"},{"panel":"times","set":{"Phone":"6/7"}},{"panel":"path","list":[{"key":"Router"}]}]},{"say":"Router to TV leads to a new vertex, so it is a tree edge. Discover TV at time 8, and it joins the search path.","ops":[{"e":["Router","TV"],"state":"tree"},{"v":"TV","state":"current"},{"panel":"times","set":{"TV":"8"}},{"panel":"path","list":[{"key":"Router"},{"key":"TV"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Printer"},{"key":"Phone"},{"key":"TV"}]}]},{"say":"TV to Speaker leads to a new vertex, so it is a tree edge. Discover Speaker at time 9, and it joins the search path.","ops":[{"e":["TV","Speaker"],"state":"tree"},{"v":"Speaker","state":"current"},{"panel":"times","set":{"Speaker":"9"}},{"panel":"path","list":[{"key":"Router"},{"key":"TV"},{"key":"Speaker"}]},{"panel":"order","list":[{"key":"Router"},{"key":"Laptop"},{"key":"Printer"},{"key":"Phone"},{"key":"TV"},{"key":"Speaker"}]}]},{"say":"Speaker has no neighbor left to try. Finish it at time 10 and back up to TV.","ops":[{"v":"Speaker","state":"done"},{"panel":"times","set":{"Speaker":"9/10"}},{"panel":"path","list":[{"key":"Router"},{"key":"TV"}]}]},{"say":"TV has no neighbor left to try. Finish it at time 11 and back up to Router.","ops":[{"v":"TV","state":"done"},{"panel":"times","set":{"TV":"8/11"}},{"panel":"path","list":[{"key":"Router"}]}]},{"say":"Router has no neighbor left to try. Finish it at time 12, which ends the search.","ops":[{"v":"Router","state":"done"},{"panel":"times","set":{"Router":"1/12"}},{"panel":"path","list":[]}]},{"say":"Done. Depth-first discovered 6 vertices from Router. It met 5 tree edges and 1 back edge."}],"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":"for ev := range traverse.DFSEvents(g, \"Router\") {\n\tif ev.Edge != nil {\n\t\tfmt.Println(ev.Kind, ev.Edge.Source().Label(), ev.Edge.Destination().Label())\n\t}\n}"}
