{"algorithm":"dfs","about":["Depth-first search keeps a stack instead of a queue. It takes the vertex on top, the one found most recently, and pushes each neighbor it hasn't seen. So it follows one branch as far as it goes before it turns back to a vertex it found earlier.","gograph marks a vertex as seen when it goes on the stack, so each vertex is pushed once and the search costs O(V+E). The last neighbor pushed comes out first. The order can differ from a recursive depth-first search, which marks a vertex when it reaches it and tries its first neighbor first.","Use it to find everything a vertex can reach, or to explore a maze or a tree of choices one branch at a time. The path it follows is rarely the shortest one. For the fewest edges, use Breadth-first."],"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":"Trace the wiring from the core switch: follow one cable as far as it goes, then go back to the last switch with a cable left to follow.","params":{"start":"Core"},"result":{"kind":"order","vertices":["Core","Dev","Dev 2","Dev 1","Lab","Ops","Ops 1","Shared","Support","Support 1","Uplink","Sales","Sales 1"]},"answer":"From Core, depth-first visits 13 vertices: Core, Dev, Dev 2, Dev 1, Lab, Ops, Ops 1, Shared, Support, Support 1, and so on to Sales 1.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"On stack","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":"stack","title":"Stack, top first","kind":"list"},{"id":"order","title":"Visit order","kind":"list"}]},"steps":[{"say":"Start at Core. Push it on the stack.","ops":[{"v":"Core","state":"waiting"},{"panel":"stack","list":[{"key":"Core"}]}]},{"say":"Pop Core from the top of the stack.","ops":[{"v":"Core","state":"current"},{"panel":"stack","list":[]},{"panel":"order","list":[{"key":"Core"}]}]},{"say":"Push Sales, Support, Ops and Dev, the unseen neighbors of Core, on the stack. Dev is on top, so it comes off next.","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":"stack","list":[{"key":"Dev"},{"key":"Ops"},{"key":"Support"},{"key":"Sales"}]}]},{"say":"Pop Dev from the top of the stack.","ops":[{"v":"Dev","state":"current"},{"panel":"stack","list":[{"key":"Ops"},{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"}]}]},{"say":"Push Lab, Dev 1 and Dev 2, the unseen neighbors of Dev, on the stack. Dev 2 is on top, so it comes off next.","ops":[{"v":"Dev","state":"done"},{"v":"Lab","state":"waiting"},{"e":["Dev","Lab"],"state":"tree"},{"v":"Dev 1","state":"waiting"},{"e":["Dev","Dev 1"],"state":"tree"},{"v":"Dev 2","state":"waiting"},{"e":["Dev","Dev 2"],"state":"tree"},{"panel":"stack","list":[{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Support"},{"key":"Sales"}]}]},{"say":"Pop Dev 2 from the top of the stack.","ops":[{"v":"Dev 2","state":"current"},{"panel":"stack","list":[{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"}]}]},{"say":"Dev 2 has no unseen neighbors.","ops":[{"v":"Dev 2","state":"done"}]},{"say":"Pop Dev 1 from the top of the stack.","ops":[{"v":"Dev 1","state":"current"},{"panel":"stack","list":[{"key":"Lab"},{"key":"Ops"},{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"}]}]},{"say":"Dev 1 has no unseen neighbors.","ops":[{"v":"Dev 1","state":"done"}]},{"say":"Pop Lab from the top of the stack.","ops":[{"v":"Lab","state":"current"},{"panel":"stack","list":[{"key":"Ops"},{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"}]}]},{"say":"Lab has no unseen neighbors.","ops":[{"v":"Lab","state":"done"}]},{"say":"Pop Ops from the top of the stack.","ops":[{"v":"Ops","state":"current"},{"panel":"stack","list":[{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"}]}]},{"say":"Push Shared and Ops 1, the unseen neighbors of Ops, on the stack. Ops 1 is on top, so it comes off next.","ops":[{"v":"Ops","state":"done"},{"v":"Shared","state":"waiting"},{"e":["Ops","Shared"],"state":"tree"},{"v":"Ops 1","state":"waiting"},{"e":["Ops","Ops 1"],"state":"tree"},{"panel":"stack","list":[{"key":"Ops 1"},{"key":"Shared"},{"key":"Support"},{"key":"Sales"}]}]},{"say":"Pop Ops 1 from the top of the stack.","ops":[{"v":"Ops 1","state":"current"},{"panel":"stack","list":[{"key":"Shared"},{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"}]}]},{"say":"Ops 1 has no unseen neighbors.","ops":[{"v":"Ops 1","state":"done"}]},{"say":"Pop Shared from the top of the stack.","ops":[{"v":"Shared","state":"current"},{"panel":"stack","list":[{"key":"Support"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"},{"key":"Shared"}]}]},{"say":"Shared has no unseen neighbors.","ops":[{"v":"Shared","state":"done"}]},{"say":"Pop Support from the top of the stack.","ops":[{"v":"Support","state":"current"},{"panel":"stack","list":[{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Support"}]}]},{"say":"Push Uplink and Support 1, the unseen neighbors of Support, on the stack. Support 1 is on top, so it comes off next.","ops":[{"v":"Support","state":"done"},{"v":"Uplink","state":"waiting"},{"e":["Support","Uplink"],"state":"tree"},{"v":"Support 1","state":"waiting"},{"e":["Support","Support 1"],"state":"tree"},{"panel":"stack","list":[{"key":"Support 1"},{"key":"Uplink"},{"key":"Sales"}]}]},{"say":"Pop Support 1 from the top of the stack.","ops":[{"v":"Support 1","state":"current"},{"panel":"stack","list":[{"key":"Uplink"},{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Support"},{"key":"Support 1"}]}]},{"say":"Support 1 has no unseen neighbors.","ops":[{"v":"Support 1","state":"done"}]},{"say":"Pop Uplink from the top of the stack.","ops":[{"v":"Uplink","state":"current"},{"panel":"stack","list":[{"key":"Sales"}]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Support"},{"key":"Support 1"},{"key":"Uplink"}]}]},{"say":"Uplink has no unseen neighbors.","ops":[{"v":"Uplink","state":"done"}]},{"say":"Pop Sales from the top of the stack.","ops":[{"v":"Sales","state":"current"},{"panel":"stack","list":[]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Support"},{"key":"Support 1"},{"key":"Uplink"},{"key":"Sales"}]}]},{"say":"Push Sales 1, the only unseen neighbor of Sales, on the stack. Sales 1 is on top, so it comes off next.","ops":[{"v":"Sales","state":"done"},{"v":"Sales 1","state":"waiting"},{"e":["Sales","Sales 1"],"state":"tree"},{"panel":"stack","list":[{"key":"Sales 1"}]}]},{"say":"Pop Sales 1 from the top of the stack.","ops":[{"v":"Sales 1","state":"current"},{"panel":"stack","list":[]},{"panel":"order","list":[{"key":"Core"},{"key":"Dev"},{"key":"Dev 2"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Ops"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Support"},{"key":"Support 1"},{"key":"Uplink"},{"key":"Sales"},{"key":"Sales 1"}]}]},{"say":"Sales 1 has no unseen neighbors.","ops":[{"v":"Sales 1","state":"done"}]},{"say":"Done. Depth-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.NewDepthFirstIterator(g, \"Core\")\nif err != nil {\n\treturn err\n}\nfor it.HasNext() {\n\tfmt.Println(it.Next().Label())\n}"}