{"algorithm":"find-cycle","about":["Cycle detection says whether a graph has a cycle. FindCycle also says where: it returns the vertices of one cycle in order, so a build tool can tell which packages import each other in a loop instead of only that some do.","It runs traverse.DFSEventsAll, a depth-first search from each vertex no earlier search reached, and keeps the search path. An edge to a vertex that is still on the path is a back edge: the path runs from that vertex down to the one the search is at, and the edge leads back up, so together they are a cycle. FindCycle returns that part of the path at the first back edge. An edge to a finished vertex can't close a cycle, since nothing that vertex leads to reaches back to the path.","On an undirected graph, the edge back to the vertex a vertex was reached from is the same edge seen from the other end, so it doesn't count, and every other cycle has at least three vertices. A self-loop is a cycle of one vertex.","The search stops at the first back edge and costs O(V+E) at most. The cycle it returns is the first one it closes, not the shortest one. A graph created with gograph.Acyclic returns false without a search. To list every vertex that is on some cycle, use the strongly connected components."],"template":{"id":"maze","name":"Maze","description":"A maze of 30 cells in five rows, A to E, and six columns, 1 to 6, so C4 is row C, column 4. Each edge is an open passage between two cells. The way from A1 to E6 winds through most of the maze, and two short loops give a few cells a second route.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"A1","x":100,"y":180},{"id":"A2","x":260,"y":180},{"id":"A3","x":420,"y":180},{"id":"A4","x":580,"y":180},{"id":"A5","x":740,"y":180},{"id":"A6","x":900,"y":180},{"id":"B1","x":100,"y":340},{"id":"B2","x":260,"y":340},{"id":"B3","x":420,"y":340},{"id":"B4","x":580,"y":340},{"id":"B5","x":740,"y":340},{"id":"B6","x":900,"y":340},{"id":"C1","x":100,"y":500},{"id":"C2","x":260,"y":500},{"id":"C3","x":420,"y":500},{"id":"C4","x":580,"y":500},{"id":"C5","x":740,"y":500},{"id":"C6","x":900,"y":500},{"id":"D1","x":100,"y":660},{"id":"D2","x":260,"y":660},{"id":"D3","x":420,"y":660},{"id":"D4","x":580,"y":660},{"id":"D5","x":740,"y":660},{"id":"D6","x":900,"y":660},{"id":"E1","x":100,"y":820},{"id":"E2","x":260,"y":820},{"id":"E3","x":420,"y":820},{"id":"E4","x":580,"y":820},{"id":"E5","x":740,"y":820},{"id":"E6","x":900,"y":820}],"edges":[{"from":"A1","to":"A2"},{"from":"A2","to":"A3"},{"from":"A3","to":"B3"},{"from":"A4","to":"A5"},{"from":"A4","to":"B4"},{"from":"A5","to":"A6"},{"from":"A6","to":"B6"},{"from":"B1","to":"B2"},{"from":"B1","to":"C1"},{"from":"B2","to":"B3"},{"from":"B4","to":"C4"},{"from":"B5","to":"B6"},{"from":"B5","to":"C5"},{"from":"B6","to":"C6"},{"from":"C1","to":"C2"},{"from":"C2","to":"D2"},{"from":"C3","to":"C4"},{"from":"C3","to":"D3"},{"from":"C4","to":"D4"},{"from":"C5","to":"C6"},{"from":"C5","to":"D5"},{"from":"D1","to":"E1"},{"from":"D2","to":"E2"},{"from":"D3","to":"E3"},{"from":"D4","to":"E4"},{"from":"D5","to":"D6"},{"from":"D6","to":"E6"},{"from":"E1","to":"E2"},{"from":"E2","to":"E3"},{"from":"E3","to":"E4"},{"from":"E5","to":"E6"}],"details":{"vertices":30,"edges":31,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.07126436781609195,"degree":{"min":1,"avg":2.066666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Find a loop in the maze: a way around that comes back to a cell without going back along a passage.","params":{},"result":{"kind":"cycle","vertices":["B6","B5","C5","C6"]},"answer":"FindCycle returns a cycle of 4 vertices: B6 – B5 – C5 – C6 – B6. It is the first cycle the search closes, and the graph can have others.","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"},{"id":"loop","label":"On the cycle","color":"#D55E00","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Followed to a new vertex","color":"#009E73","shape":"thick"},{"id":"finished","label":"To a finished vertex, can't close a cycle","color":"#CC79A7","shape":"dotted"},{"id":"loop","label":"On the cycle","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"path","title":"Search path, start first","kind":"list"},{"id":"cycle","title":"Cycle","kind":"list"}]},"steps":[{"say":"FindCycle searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and keeps the vertices on the current search path. The first edge to a vertex still on the path closes a cycle. On an undirected graph, the edge back to the vertex a vertex was reached from doesn't count."},{"say":"Start at A1, the first vertex in the graph's order. It begins the search path.","ops":[{"v":"A1","state":"current"},{"panel":"path","list":[{"key":"A1"}]}]},{"say":"Follow A1 to A2, a new vertex. A2 joins the search path.","ops":[{"e":["A1","A2"],"state":"tree"},{"v":"A2","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"}]}]},{"say":"A2 to A1 leads back to A1, the vertex A2 was reached from. That is the same edge seen from the other end, so it doesn't count, here or anywhere else it comes up."},{"say":"Follow A2 to A3, a new vertex. A3 joins the search path.","ops":[{"e":["A2","A3"],"state":"tree"},{"v":"A3","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"}]}]},{"say":"Follow A3 to B3, a new vertex. B3 joins the search path.","ops":[{"e":["A3","B3"],"state":"tree"},{"v":"B3","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"}]}]},{"say":"Follow B3 to B2, a new vertex. B2 joins the search path.","ops":[{"e":["B3","B2"],"state":"tree"},{"v":"B2","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"}]}]},{"say":"Follow B2 to B1, a new vertex. B1 joins the search path.","ops":[{"e":["B2","B1"],"state":"tree"},{"v":"B1","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"}]}]},{"say":"Follow B1 to C1, a new vertex. C1 joins the search path.","ops":[{"e":["B1","C1"],"state":"tree"},{"v":"C1","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"}]}]},{"say":"Follow C1 to C2, a new vertex. C2 joins the search path.","ops":[{"e":["C1","C2"],"state":"tree"},{"v":"C2","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"}]}]},{"say":"Follow C2 to D2, a new vertex. D2 joins the search path.","ops":[{"e":["C2","D2"],"state":"tree"},{"v":"D2","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"}]}]},{"say":"Follow D2 to E2, a new vertex. E2 joins the search path.","ops":[{"e":["D2","E2"],"state":"tree"},{"v":"E2","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"}]}]},{"say":"Follow E2 to E1, a new vertex. E1 joins the search path.","ops":[{"e":["E2","E1"],"state":"tree"},{"v":"E1","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E1"}]}]},{"say":"Follow E1 to D1, a new vertex. D1 joins the search path.","ops":[{"e":["E1","D1"],"state":"tree"},{"v":"D1","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E1"},{"key":"D1"}]}]},{"say":"D1 has no edges left to follow. It is finished and leaves the search path.","ops":[{"v":"D1","state":"done"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E1"}]}]},{"say":"E1 has no edges left to follow. It is finished and leaves the search path.","ops":[{"v":"E1","state":"done"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"}]}]},{"say":"Follow E2 to E3, a new vertex. E3 joins the search path.","ops":[{"e":["E2","E3"],"state":"tree"},{"v":"E3","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"}]}]},{"say":"Follow E3 to D3, a new vertex. D3 joins the search path.","ops":[{"e":["E3","D3"],"state":"tree"},{"v":"D3","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"}]}]},{"say":"Follow D3 to C3, a new vertex. C3 joins the search path.","ops":[{"e":["D3","C3"],"state":"tree"},{"v":"C3","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"}]}]},{"say":"Follow C3 to C4, a new vertex. C4 joins the search path.","ops":[{"e":["C3","C4"],"state":"tree"},{"v":"C4","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"}]}]},{"say":"Follow C4 to B4, a new vertex. B4 joins the search path.","ops":[{"e":["C4","B4"],"state":"tree"},{"v":"B4","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"}]}]},{"say":"Follow B4 to A4, a new vertex. A4 joins the search path.","ops":[{"e":["B4","A4"],"state":"tree"},{"v":"A4","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"}]}]},{"say":"Follow A4 to A5, a new vertex. A5 joins the search path.","ops":[{"e":["A4","A5"],"state":"tree"},{"v":"A5","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"},{"key":"A5"}]}]},{"say":"Follow A5 to A6, a new vertex. A6 joins the search path.","ops":[{"e":["A5","A6"],"state":"tree"},{"v":"A6","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"},{"key":"A5"},{"key":"A6"}]}]},{"say":"Follow A6 to B6, a new vertex. B6 joins the search path.","ops":[{"e":["A6","B6"],"state":"tree"},{"v":"B6","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"},{"key":"A5"},{"key":"A6"},{"key":"B6"}]}]},{"say":"Follow B6 to B5, a new vertex. B5 joins the search path.","ops":[{"e":["B6","B5"],"state":"tree"},{"v":"B5","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"},{"key":"A5"},{"key":"A6"},{"key":"B6"},{"key":"B5"}]}]},{"say":"Follow B5 to C5, a new vertex. C5 joins the search path.","ops":[{"e":["B5","C5"],"state":"tree"},{"v":"C5","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"},{"key":"A5"},{"key":"A6"},{"key":"B6"},{"key":"B5"},{"key":"C5"}]}]},{"say":"Follow C5 to C6, a new vertex. C6 joins the search path.","ops":[{"e":["C5","C6"],"state":"tree"},{"v":"C6","state":"current"},{"panel":"path","list":[{"key":"A1"},{"key":"A2"},{"key":"A3"},{"key":"B3"},{"key":"B2"},{"key":"B1"},{"key":"C1"},{"key":"C2"},{"key":"D2"},{"key":"E2"},{"key":"E3"},{"key":"D3"},{"key":"C3"},{"key":"C4"},{"key":"B4"},{"key":"A4"},{"key":"A5"},{"key":"A6"},{"key":"B6"},{"key":"B5"},{"key":"C5"},{"key":"C6"}]}]},{"say":"C6 to B6 leads to B6, which is still on the search path. The path from B6 to C6 and this edge close a cycle: B6 – B5 – C5 – C6 – B6. FindCycle stops here.","ops":[{"v":"B6","state":"loop"},{"e":["B6","B5"],"state":"loop"},{"v":"B5","state":"loop"},{"e":["B5","C5"],"state":"loop"},{"v":"C5","state":"loop"},{"e":["C5","C6"],"state":"loop"},{"v":"C6","state":"loop"},{"e":["C6","B6"],"state":"loop"},{"panel":"cycle","list":[{"key":"B6"},{"key":"B5"},{"key":"C5"},{"key":"C6"}]}]},{"say":"Done. FindCycle returns the 4 vertices of the cycle in order, starting where the back edge leads. The search stopped at the first cycle it closed, and a shorter one can exist."}],"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":"cycle, ok := connectivity.FindCycle(g)\nif !ok {\n\treturn // no cycle\n}\nfor _, v := range cycle {\n\tfmt.Print(v.Label(), \"->\")\n}\nfmt.Println(cycle[0].Label())"}
