{"algorithm":"connected-components","about":["Two vertices are in the same connected component when some path joins them. The components are the separate pieces of a graph: no edge runs between two of them, so nothing in one piece can reach anything in another.","gograph searches breadth-first from the first vertex and gives every vertex it reaches the same component. When that search runs out, it starts the next one at the first vertex no search has reached, and so on, so the components come out in the order of their first vertex. Every vertex and edge is looked at once, so it costs O(V+E).","On a directed graph, gograph ignores the edge directions and returns the weakly connected components. It joins the two ends of each edge with union-find instead of searching, since a vertex doesn't keep a list of the edges that end at it. To find the groups that can reach each other along the edge directions, use Tarjan, Kosaraju or Gabow. Use connected components to find the islands of a network after an outage, or to handle each piece of a graph on its own."],"template":{"id":"maze-doors","name":"Locked maze","description":"The maze with four doors locked: between B4 and C4, B5 and C5, B6 and C6, and C2 and D2. Each edge is a passage that is still open, so a walker can only reach the cells on their own side of the locked doors.","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":"B5","to":"B6"},{"from":"C1","to":"C2"},{"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":27,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.06206896551724138,"degree":{"min":1,"avg":1.8,"max":3},"selfLoops":0,"components":4}},"problem":"With four doors locked, which cells of the maze can a walker still get between?","params":{},"result":{"kind":"groups","groups":[["A1","A2","A3","B1","B2","B3","C1","C2"],["A4","A5","A6","B4","B5","B6"],["C3","C4","D1","D2","D3","D4","E1","E2","E3","E4"],["C5","C6","D5","D6","E5","E6"]]},"answer":"The graph falls into 4 connected components, with 8, 6, 10 and 6 vertices. No edge joins two of them, so each vertex can reach only the vertices in its own component.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being checked","color":"#56B4E9","shape":"ring"},{"id":"done","label":"In a component","color":"#009E73","shape":"filled"},{"id":"component-1","label":"Component 1, 8 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Component 2, 6 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-3","label":"Component 3, 10 vertices","color":"#E69F00","shape":"filled"},{"id":"component-4","label":"Component 4, 6 vertices","color":"#F0E442","shape":"dashed-square"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Reached a new vertex","color":"#009E73","shape":"thick"}],"panels":[{"id":"queue","title":"Queue","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"ConnectedComponents searches breadth-first from each vertex no earlier search has reached, in the graph's vertex order. Every vertex a search reaches is in the same component as the vertex it started from. When the queue runs out, the component is complete."},{"say":"Start component 1 at A1, the first vertex. Put it in the queue.","ops":[{"v":"A1","state":"waiting"},{"panel":"queue","list":[{"key":"A1"}]}]},{"say":"Take A1 from the front of the queue. Its neighbor A2 is new, so it joins the back of the queue.","ops":[{"v":"A1","state":"current"},{"v":"A2","state":"waiting"},{"e":["A1","A2"],"state":"tree"},{"panel":"queue","list":[{"key":"A2"}]}]},{"say":"Take A2 from the front of the queue. Its neighbor A3 is new, so it joins the back of the queue.","ops":[{"v":"A2","state":"current"},{"v":"A1","state":"done"},{"v":"A3","state":"waiting"},{"e":["A2","A3"],"state":"tree"},{"panel":"queue","list":[{"key":"A3"}]}]},{"say":"Take A3 from the front of the queue. Its neighbor B3 is new, so it joins the back of the queue.","ops":[{"v":"A3","state":"current"},{"v":"A2","state":"done"},{"v":"B3","state":"waiting"},{"e":["A3","B3"],"state":"tree"},{"panel":"queue","list":[{"key":"B3"}]}]},{"say":"Take B3 from the front of the queue. Its neighbor B2 is new, so it joins the back of the queue.","ops":[{"v":"B3","state":"current"},{"v":"A3","state":"done"},{"v":"B2","state":"waiting"},{"e":["B3","B2"],"state":"tree"},{"panel":"queue","list":[{"key":"B2"}]}]},{"say":"Take B2 from the front of the queue. Its neighbor B1 is new, so it joins the back of the queue.","ops":[{"v":"B2","state":"current"},{"v":"B3","state":"done"},{"v":"B1","state":"waiting"},{"e":["B2","B1"],"state":"tree"},{"panel":"queue","list":[{"key":"B1"}]}]},{"say":"Take B1 from the front of the queue. Its neighbor C1 is new, so it joins the back of the queue.","ops":[{"v":"B1","state":"current"},{"v":"B2","state":"done"},{"v":"C1","state":"waiting"},{"e":["B1","C1"],"state":"tree"},{"panel":"queue","list":[{"key":"C1"}]}]},{"say":"Take C1 from the front of the queue. Its neighbor C2 is new, so it joins the back of the queue.","ops":[{"v":"C1","state":"current"},{"v":"B1","state":"done"},{"v":"C2","state":"waiting"},{"e":["C1","C2"],"state":"tree"},{"panel":"queue","list":[{"key":"C2"}]}]},{"say":"Take C2 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"C2","state":"current"},{"v":"C1","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 1 is complete with 8 vertices.","ops":[{"v":"A1","state":"done"},{"v":"A2","state":"done"},{"v":"A3","state":"done"},{"v":"B3","state":"done"},{"v":"B2","state":"done"},{"v":"B1","state":"done"},{"v":"C1","state":"done"},{"v":"C2","state":"done"},{"panel":"components","groups":[["A1","A2","A3","B3","B2","B1","C1","C2"]]}]},{"say":"Start component 2 at A4, the next vertex no search has reached. Put it in the queue.","ops":[{"v":"A4","state":"waiting"},{"panel":"queue","list":[{"key":"A4"}]}]},{"say":"Take A4 from the front of the queue. Its neighbors A5 and B4 are new, so they join the back of the queue.","ops":[{"v":"A4","state":"current"},{"v":"A5","state":"waiting"},{"e":["A4","A5"],"state":"tree"},{"v":"B4","state":"waiting"},{"e":["A4","B4"],"state":"tree"},{"panel":"queue","list":[{"key":"A5"},{"key":"B4"}]}]},{"say":"Take A5 from the front of the queue. Its neighbor A6 is new, so it joins the back of the queue.","ops":[{"v":"A5","state":"current"},{"v":"A4","state":"done"},{"v":"A6","state":"waiting"},{"e":["A5","A6"],"state":"tree"},{"panel":"queue","list":[{"key":"B4"},{"key":"A6"}]}]},{"say":"Take B4 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"B4","state":"current"},{"v":"A5","state":"done"},{"panel":"queue","list":[{"key":"A6"}]}]},{"say":"Take A6 from the front of the queue. Its neighbor B6 is new, so it joins the back of the queue.","ops":[{"v":"A6","state":"current"},{"v":"B4","state":"done"},{"v":"B6","state":"waiting"},{"e":["A6","B6"],"state":"tree"},{"panel":"queue","list":[{"key":"B6"}]}]},{"say":"Take B6 from the front of the queue. Its neighbor B5 is new, so it joins the back of the queue.","ops":[{"v":"B6","state":"current"},{"v":"A6","state":"done"},{"v":"B5","state":"waiting"},{"e":["B6","B5"],"state":"tree"},{"panel":"queue","list":[{"key":"B5"}]}]},{"say":"Take B5 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"B5","state":"current"},{"v":"B6","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 2 is complete with 6 vertices.","ops":[{"v":"A4","state":"done"},{"v":"A5","state":"done"},{"v":"B4","state":"done"},{"v":"A6","state":"done"},{"v":"B6","state":"done"},{"v":"B5","state":"done"},{"panel":"components","groups":[["A1","A2","A3","B3","B2","B1","C1","C2"],["A4","A5","B4","A6","B6","B5"]]}]},{"say":"Start component 3 at C3, the next vertex no search has reached. Put it in the queue.","ops":[{"v":"C3","state":"waiting"},{"panel":"queue","list":[{"key":"C3"}]}]},{"say":"Take C3 from the front of the queue. Its neighbors C4 and D3 are new, so they join the back of the queue.","ops":[{"v":"C3","state":"current"},{"v":"C4","state":"waiting"},{"e":["C3","C4"],"state":"tree"},{"v":"D3","state":"waiting"},{"e":["C3","D3"],"state":"tree"},{"panel":"queue","list":[{"key":"C4"},{"key":"D3"}]}]},{"say":"Take C4 from the front of the queue. Its neighbor D4 is new, so it joins the back of the queue.","ops":[{"v":"C4","state":"current"},{"v":"C3","state":"done"},{"v":"D4","state":"waiting"},{"e":["C4","D4"],"state":"tree"},{"panel":"queue","list":[{"key":"D3"},{"key":"D4"}]}]},{"say":"Take D3 from the front of the queue. Its neighbor E3 is new, so it joins the back of the queue.","ops":[{"v":"D3","state":"current"},{"v":"C4","state":"done"},{"v":"E3","state":"waiting"},{"e":["D3","E3"],"state":"tree"},{"panel":"queue","list":[{"key":"D4"},{"key":"E3"}]}]},{"say":"Take D4 from the front of the queue. Its neighbor E4 is new, so it joins the back of the queue.","ops":[{"v":"D4","state":"current"},{"v":"D3","state":"done"},{"v":"E4","state":"waiting"},{"e":["D4","E4"],"state":"tree"},{"panel":"queue","list":[{"key":"E3"},{"key":"E4"}]}]},{"say":"Take E3 from the front of the queue. Its neighbor E2 is new, so it joins the back of the queue.","ops":[{"v":"E3","state":"current"},{"v":"D4","state":"done"},{"v":"E2","state":"waiting"},{"e":["E3","E2"],"state":"tree"},{"panel":"queue","list":[{"key":"E4"},{"key":"E2"}]}]},{"say":"Take E4 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"E4","state":"current"},{"v":"E3","state":"done"},{"panel":"queue","list":[{"key":"E2"}]}]},{"say":"Take E2 from the front of the queue. Its neighbors D2 and E1 are new, so they join the back of the queue.","ops":[{"v":"E2","state":"current"},{"v":"E4","state":"done"},{"v":"D2","state":"waiting"},{"e":["E2","D2"],"state":"tree"},{"v":"E1","state":"waiting"},{"e":["E2","E1"],"state":"tree"},{"panel":"queue","list":[{"key":"D2"},{"key":"E1"}]}]},{"say":"Take D2 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"D2","state":"current"},{"v":"E2","state":"done"},{"panel":"queue","list":[{"key":"E1"}]}]},{"say":"Take E1 from the front of the queue. Its neighbor D1 is new, so it joins the back of the queue.","ops":[{"v":"E1","state":"current"},{"v":"D2","state":"done"},{"v":"D1","state":"waiting"},{"e":["E1","D1"],"state":"tree"},{"panel":"queue","list":[{"key":"D1"}]}]},{"say":"Take D1 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"D1","state":"current"},{"v":"E1","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 3 is complete with 10 vertices.","ops":[{"v":"C3","state":"done"},{"v":"C4","state":"done"},{"v":"D3","state":"done"},{"v":"D4","state":"done"},{"v":"E3","state":"done"},{"v":"E4","state":"done"},{"v":"E2","state":"done"},{"v":"D2","state":"done"},{"v":"E1","state":"done"},{"v":"D1","state":"done"},{"panel":"components","groups":[["A1","A2","A3","B3","B2","B1","C1","C2"],["A4","A5","B4","A6","B6","B5"],["C3","C4","D3","D4","E3","E4","E2","D2","E1","D1"]]}]},{"say":"Start component 4 at C5, the next vertex no search has reached. Put it in the queue.","ops":[{"v":"C5","state":"waiting"},{"panel":"queue","list":[{"key":"C5"}]}]},{"say":"Take C5 from the front of the queue. Its neighbors C6 and D5 are new, so they join the back of the queue.","ops":[{"v":"C5","state":"current"},{"v":"C6","state":"waiting"},{"e":["C5","C6"],"state":"tree"},{"v":"D5","state":"waiting"},{"e":["C5","D5"],"state":"tree"},{"panel":"queue","list":[{"key":"C6"},{"key":"D5"}]}]},{"say":"Take C6 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"C6","state":"current"},{"v":"C5","state":"done"},{"panel":"queue","list":[{"key":"D5"}]}]},{"say":"Take D5 from the front of the queue. Its neighbor D6 is new, so it joins the back of the queue.","ops":[{"v":"D5","state":"current"},{"v":"C6","state":"done"},{"v":"D6","state":"waiting"},{"e":["D5","D6"],"state":"tree"},{"panel":"queue","list":[{"key":"D6"}]}]},{"say":"Take D6 from the front of the queue. Its neighbor E6 is new, so it joins the back of the queue.","ops":[{"v":"D6","state":"current"},{"v":"D5","state":"done"},{"v":"E6","state":"waiting"},{"e":["D6","E6"],"state":"tree"},{"panel":"queue","list":[{"key":"E6"}]}]},{"say":"Take E6 from the front of the queue. Its neighbor E5 is new, so it joins the back of the queue.","ops":[{"v":"E6","state":"current"},{"v":"D6","state":"done"},{"v":"E5","state":"waiting"},{"e":["E6","E5"],"state":"tree"},{"panel":"queue","list":[{"key":"E5"}]}]},{"say":"Take E5 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"E5","state":"current"},{"v":"E6","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 4 is complete with 6 vertices.","ops":[{"v":"C5","state":"done"},{"v":"C6","state":"done"},{"v":"D5","state":"done"},{"v":"D6","state":"done"},{"v":"E6","state":"done"},{"v":"E5","state":"done"},{"panel":"components","groups":[["A1","A2","A3","B3","B2","B1","C1","C2"],["A4","A5","B4","A6","B6","B5"],["C3","C4","D3","D4","E3","E4","E2","D2","E1","D1"],["C5","C6","D5","D6","E6","E5"]]}]},{"say":"Done. ConnectedComponents found 4 components. They come out in the order of their first vertex. Every vertex now shows the component it belongs to.","ops":[{"v":"A1","state":"component-1"},{"v":"A2","state":"component-1"},{"v":"A3","state":"component-1"},{"v":"B3","state":"component-1"},{"v":"B2","state":"component-1"},{"v":"B1","state":"component-1"},{"v":"C1","state":"component-1"},{"v":"C2","state":"component-1"},{"v":"A4","state":"component-2"},{"v":"A5","state":"component-2"},{"v":"B4","state":"component-2"},{"v":"A6","state":"component-2"},{"v":"B6","state":"component-2"},{"v":"B5","state":"component-2"},{"v":"C3","state":"component-3"},{"v":"C4","state":"component-3"},{"v":"D3","state":"component-3"},{"v":"D4","state":"component-3"},{"v":"E3","state":"component-3"},{"v":"E4","state":"component-3"},{"v":"E2","state":"component-3"},{"v":"D2","state":"component-3"},{"v":"E1","state":"component-3"},{"v":"D1","state":"component-3"},{"v":"C5","state":"component-4"},{"v":"C6","state":"component-4"},{"v":"D5","state":"component-4"},{"v":"D6","state":"component-4"},{"v":"E6","state":"component-4"},{"v":"E5","state":"component-4"}]}],"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 _, component := range gograph.ConnectedComponents(g) {\n\tvar names []string\n\tfor _, v := range component {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(strings.Join(names, \", \"))\n}"}