{"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":"karate-split","name":"Karate club split","description":"The karate club after the dispute split it in two. Each edge joins two members who spent time together and joined the same side: the instructor's new club around 1, or the old club around the officer, 34. Ties between members who went separate ways are left out.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"1","x":590,"y":680},{"id":"2","x":640,"y":560},{"id":"3","x":420,"y":520},{"id":"4","x":470,"y":760},{"id":"5","x":680,"y":850},{"id":"6","x":750,"y":860},{"id":"7","x":820,"y":760},{"id":"8","x":390,"y":660},{"id":"9","x":520,"y":430},{"id":"10","x":590,"y":230},{"id":"11","x":590,"y":930},{"id":"12","x":400,"y":900},{"id":"13","x":490,"y":890},{"id":"14","x":590,"y":480},{"id":"15","x":460,"y":80},{"id":"16","x":380,"y":70},{"id":"17","x":950,"y":940},{"id":"18","x":830,"y":560},{"id":"19","x":540,"y":110},{"id":"20","x":770,"y":450},{"id":"21","x":90,"y":220},{"id":"22","x":820,"y":640},{"id":"23","x":290,"y":70},{"id":"24","x":120,"y":300},{"id":"25","x":120,"y":690},{"id":"26","x":50,"y":570},{"id":"27","x":220,"y":60},{"id":"28","x":210,"y":490},{"id":"29","x":390,"y":440},{"id":"30","x":170,"y":190},{"id":"31","x":640,"y":300},{"id":"32","x":280,"y":570},{"id":"33","x":250,"y":340},{"id":"34","x":440,"y":260}],"edges":[{"from":"1","to":"2"},{"from":"1","to":"3"},{"from":"1","to":"4"},{"from":"1","to":"5"},{"from":"1","to":"6"},{"from":"1","to":"7"},{"from":"1","to":"8"},{"from":"1","to":"9"},{"from":"1","to":"11"},{"from":"1","to":"12"},{"from":"1","to":"13"},{"from":"1","to":"14"},{"from":"1","to":"18"},{"from":"1","to":"20"},{"from":"1","to":"22"},{"from":"2","to":"3"},{"from":"2","to":"4"},{"from":"2","to":"8"},{"from":"2","to":"14"},{"from":"2","to":"18"},{"from":"2","to":"20"},{"from":"2","to":"22"},{"from":"3","to":"4"},{"from":"3","to":"8"},{"from":"3","to":"9"},{"from":"3","to":"14"},{"from":"4","to":"8"},{"from":"4","to":"13"},{"from":"4","to":"14"},{"from":"5","to":"7"},{"from":"5","to":"11"},{"from":"6","to":"7"},{"from":"6","to":"11"},{"from":"6","to":"17"},{"from":"7","to":"17"},{"from":"10","to":"34"},{"from":"15","to":"33"},{"from":"15","to":"34"},{"from":"16","to":"33"},{"from":"16","to":"34"},{"from":"19","to":"33"},{"from":"19","to":"34"},{"from":"21","to":"33"},{"from":"21","to":"34"},{"from":"23","to":"33"},{"from":"23","to":"34"},{"from":"24","to":"26"},{"from":"24","to":"28"},{"from":"24","to":"30"},{"from":"24","to":"33"},{"from":"24","to":"34"},{"from":"25","to":"26"},{"from":"25","to":"28"},{"from":"25","to":"32"},{"from":"26","to":"32"},{"from":"27","to":"30"},{"from":"27","to":"34"},{"from":"28","to":"34"},{"from":"29","to":"32"},{"from":"29","to":"34"},{"from":"30","to":"33"},{"from":"30","to":"34"},{"from":"31","to":"33"},{"from":"31","to":"34"},{"from":"32","to":"33"},{"from":"32","to":"34"},{"from":"33","to":"34"}],"source":"W. W. Zachary, \"An information flow model for conflict and fission in small groups\", Journal of Anthropological Research 33 (1977).","details":{"vertices":34,"edges":67,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.11942959001782531,"degree":{"min":1,"avg":3.9411764705882355,"max":15},"selfLoops":0,"components":2}},"problem":"After the split, which members are still linked to each other through friends on their own side?","params":{},"result":{"kind":"groups","groups":[["1","2","3","4","5","6","7","8","9","11","12","13","14","17","18","20","22"],["10","15","16","19","21","23","24","25","26","27","28","29","30","31","32","33","34"]]},"answer":"The graph falls into 2 connected components, with 17 and 17 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, 17 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Component 2, 17 vertices","color":"#CC79A7","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 1, the first vertex. Put it in the queue.","ops":[{"v":"1","state":"waiting"},{"panel":"queue","list":[{"key":"1"}]}]},{"say":"Take 1 from the front of the queue. Its neighbors 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 18, 20 and 22 are new, so they join the back of the queue.","ops":[{"v":"1","state":"current"},{"v":"2","state":"waiting"},{"e":["1","2"],"state":"tree"},{"v":"3","state":"waiting"},{"e":["1","3"],"state":"tree"},{"v":"4","state":"waiting"},{"e":["1","4"],"state":"tree"},{"v":"5","state":"waiting"},{"e":["1","5"],"state":"tree"},{"v":"6","state":"waiting"},{"e":["1","6"],"state":"tree"},{"v":"7","state":"waiting"},{"e":["1","7"],"state":"tree"},{"v":"8","state":"waiting"},{"e":["1","8"],"state":"tree"},{"v":"9","state":"waiting"},{"e":["1","9"],"state":"tree"},{"v":"11","state":"waiting"},{"e":["1","11"],"state":"tree"},{"v":"12","state":"waiting"},{"e":["1","12"],"state":"tree"},{"v":"13","state":"waiting"},{"e":["1","13"],"state":"tree"},{"v":"14","state":"waiting"},{"e":["1","14"],"state":"tree"},{"v":"18","state":"waiting"},{"e":["1","18"],"state":"tree"},{"v":"20","state":"waiting"},{"e":["1","20"],"state":"tree"},{"v":"22","state":"waiting"},{"e":["1","22"],"state":"tree"},{"panel":"queue","list":[{"key":"2"},{"key":"3"},{"key":"4"},{"key":"5"},{"key":"6"},{"key":"7"},{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"}]}]},{"say":"Take 2 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"2","state":"current"},{"v":"1","state":"done"},{"panel":"queue","list":[{"key":"3"},{"key":"4"},{"key":"5"},{"key":"6"},{"key":"7"},{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"}]}]},{"say":"Take 3 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"3","state":"current"},{"v":"2","state":"done"},{"panel":"queue","list":[{"key":"4"},{"key":"5"},{"key":"6"},{"key":"7"},{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"}]}]},{"say":"Take 4 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"4","state":"current"},{"v":"3","state":"done"},{"panel":"queue","list":[{"key":"5"},{"key":"6"},{"key":"7"},{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"}]}]},{"say":"Take 5 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"5","state":"current"},{"v":"4","state":"done"},{"panel":"queue","list":[{"key":"6"},{"key":"7"},{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"}]}]},{"say":"Take 6 from the front of the queue. Its neighbor 17 is new, so it joins the back of the queue.","ops":[{"v":"6","state":"current"},{"v":"5","state":"done"},{"v":"17","state":"waiting"},{"e":["6","17"],"state":"tree"},{"panel":"queue","list":[{"key":"7"},{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 7 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"7","state":"current"},{"v":"6","state":"done"},{"panel":"queue","list":[{"key":"8"},{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 8 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"8","state":"current"},{"v":"7","state":"done"},{"panel":"queue","list":[{"key":"9"},{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 9 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"9","state":"current"},{"v":"8","state":"done"},{"panel":"queue","list":[{"key":"11"},{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 11 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"11","state":"current"},{"v":"9","state":"done"},{"panel":"queue","list":[{"key":"12"},{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 12 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"12","state":"current"},{"v":"11","state":"done"},{"panel":"queue","list":[{"key":"13"},{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 13 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"13","state":"current"},{"v":"12","state":"done"},{"panel":"queue","list":[{"key":"14"},{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 14 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"14","state":"current"},{"v":"13","state":"done"},{"panel":"queue","list":[{"key":"18"},{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 18 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"18","state":"current"},{"v":"14","state":"done"},{"panel":"queue","list":[{"key":"20"},{"key":"22"},{"key":"17"}]}]},{"say":"Take 20 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"20","state":"current"},{"v":"18","state":"done"},{"panel":"queue","list":[{"key":"22"},{"key":"17"}]}]},{"say":"Take 22 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"22","state":"current"},{"v":"20","state":"done"},{"panel":"queue","list":[{"key":"17"}]}]},{"say":"Take 17 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"17","state":"current"},{"v":"22","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 1 is complete with 17 vertices.","ops":[{"v":"1","state":"done"},{"v":"2","state":"done"},{"v":"3","state":"done"},{"v":"4","state":"done"},{"v":"5","state":"done"},{"v":"6","state":"done"},{"v":"7","state":"done"},{"v":"8","state":"done"},{"v":"9","state":"done"},{"v":"11","state":"done"},{"v":"12","state":"done"},{"v":"13","state":"done"},{"v":"14","state":"done"},{"v":"18","state":"done"},{"v":"20","state":"done"},{"v":"22","state":"done"},{"v":"17","state":"done"},{"panel":"components","groups":[["1","2","3","4","5","6","7","8","9","11","12","13","14","18","20","22","17"]]}]},{"say":"Start component 2 at 10, the next vertex no search has reached. Put it in the queue.","ops":[{"v":"10","state":"waiting"},{"panel":"queue","list":[{"key":"10"}]}]},{"say":"Take 10 from the front of the queue. Its neighbor 34 is new, so it joins the back of the queue.","ops":[{"v":"10","state":"current"},{"v":"34","state":"waiting"},{"e":["10","34"],"state":"tree"},{"panel":"queue","list":[{"key":"34"}]}]},{"say":"Take 34 from the front of the queue. Its neighbors 15, 16, 19, 21, 23, 24, 27, 28, 29, 30, 31, 32 and 33 are new, so they join the back of the queue.","ops":[{"v":"34","state":"current"},{"v":"10","state":"done"},{"v":"15","state":"waiting"},{"e":["34","15"],"state":"tree"},{"v":"16","state":"waiting"},{"e":["34","16"],"state":"tree"},{"v":"19","state":"waiting"},{"e":["34","19"],"state":"tree"},{"v":"21","state":"waiting"},{"e":["34","21"],"state":"tree"},{"v":"23","state":"waiting"},{"e":["34","23"],"state":"tree"},{"v":"24","state":"waiting"},{"e":["34","24"],"state":"tree"},{"v":"27","state":"waiting"},{"e":["34","27"],"state":"tree"},{"v":"28","state":"waiting"},{"e":["34","28"],"state":"tree"},{"v":"29","state":"waiting"},{"e":["34","29"],"state":"tree"},{"v":"30","state":"waiting"},{"e":["34","30"],"state":"tree"},{"v":"31","state":"waiting"},{"e":["34","31"],"state":"tree"},{"v":"32","state":"waiting"},{"e":["34","32"],"state":"tree"},{"v":"33","state":"waiting"},{"e":["34","33"],"state":"tree"},{"panel":"queue","list":[{"key":"15"},{"key":"16"},{"key":"19"},{"key":"21"},{"key":"23"},{"key":"24"},{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"}]}]},{"say":"Take 15 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"15","state":"current"},{"v":"34","state":"done"},{"panel":"queue","list":[{"key":"16"},{"key":"19"},{"key":"21"},{"key":"23"},{"key":"24"},{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"}]}]},{"say":"Take 16 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"16","state":"current"},{"v":"15","state":"done"},{"panel":"queue","list":[{"key":"19"},{"key":"21"},{"key":"23"},{"key":"24"},{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"}]}]},{"say":"Take 19 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"19","state":"current"},{"v":"16","state":"done"},{"panel":"queue","list":[{"key":"21"},{"key":"23"},{"key":"24"},{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"}]}]},{"say":"Take 21 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"21","state":"current"},{"v":"19","state":"done"},{"panel":"queue","list":[{"key":"23"},{"key":"24"},{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"}]}]},{"say":"Take 23 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"23","state":"current"},{"v":"21","state":"done"},{"panel":"queue","list":[{"key":"24"},{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"}]}]},{"say":"Take 24 from the front of the queue. Its neighbor 26 is new, so it joins the back of the queue.","ops":[{"v":"24","state":"current"},{"v":"23","state":"done"},{"v":"26","state":"waiting"},{"e":["24","26"],"state":"tree"},{"panel":"queue","list":[{"key":"27"},{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"},{"key":"26"}]}]},{"say":"Take 27 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"27","state":"current"},{"v":"24","state":"done"},{"panel":"queue","list":[{"key":"28"},{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"},{"key":"26"}]}]},{"say":"Take 28 from the front of the queue. Its neighbor 25 is new, so it joins the back of the queue.","ops":[{"v":"28","state":"current"},{"v":"27","state":"done"},{"v":"25","state":"waiting"},{"e":["28","25"],"state":"tree"},{"panel":"queue","list":[{"key":"29"},{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"},{"key":"26"},{"key":"25"}]}]},{"say":"Take 29 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"29","state":"current"},{"v":"28","state":"done"},{"panel":"queue","list":[{"key":"30"},{"key":"31"},{"key":"32"},{"key":"33"},{"key":"26"},{"key":"25"}]}]},{"say":"Take 30 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"30","state":"current"},{"v":"29","state":"done"},{"panel":"queue","list":[{"key":"31"},{"key":"32"},{"key":"33"},{"key":"26"},{"key":"25"}]}]},{"say":"Take 31 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"31","state":"current"},{"v":"30","state":"done"},{"panel":"queue","list":[{"key":"32"},{"key":"33"},{"key":"26"},{"key":"25"}]}]},{"say":"Take 32 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"32","state":"current"},{"v":"31","state":"done"},{"panel":"queue","list":[{"key":"33"},{"key":"26"},{"key":"25"}]}]},{"say":"Take 33 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"33","state":"current"},{"v":"32","state":"done"},{"panel":"queue","list":[{"key":"26"},{"key":"25"}]}]},{"say":"Take 26 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"26","state":"current"},{"v":"33","state":"done"},{"panel":"queue","list":[{"key":"25"}]}]},{"say":"Take 25 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"25","state":"current"},{"v":"26","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 2 is complete with 17 vertices.","ops":[{"v":"10","state":"done"},{"v":"34","state":"done"},{"v":"15","state":"done"},{"v":"16","state":"done"},{"v":"19","state":"done"},{"v":"21","state":"done"},{"v":"23","state":"done"},{"v":"24","state":"done"},{"v":"27","state":"done"},{"v":"28","state":"done"},{"v":"29","state":"done"},{"v":"30","state":"done"},{"v":"31","state":"done"},{"v":"32","state":"done"},{"v":"33","state":"done"},{"v":"26","state":"done"},{"v":"25","state":"done"},{"panel":"components","groups":[["1","2","3","4","5","6","7","8","9","11","12","13","14","18","20","22","17"],["10","34","15","16","19","21","23","24","27","28","29","30","31","32","33","26","25"]]}]},{"say":"Done. ConnectedComponents found 2 components. They come out in the order of their first vertex. Every vertex now shows the component it belongs to.","ops":[{"v":"1","state":"component-1"},{"v":"2","state":"component-1"},{"v":"3","state":"component-1"},{"v":"4","state":"component-1"},{"v":"5","state":"component-1"},{"v":"6","state":"component-1"},{"v":"7","state":"component-1"},{"v":"8","state":"component-1"},{"v":"9","state":"component-1"},{"v":"11","state":"component-1"},{"v":"12","state":"component-1"},{"v":"13","state":"component-1"},{"v":"14","state":"component-1"},{"v":"18","state":"component-1"},{"v":"20","state":"component-1"},{"v":"22","state":"component-1"},{"v":"17","state":"component-1"},{"v":"10","state":"component-2"},{"v":"34","state":"component-2"},{"v":"15","state":"component-2"},{"v":"16","state":"component-2"},{"v":"19","state":"component-2"},{"v":"21","state":"component-2"},{"v":"23","state":"component-2"},{"v":"24","state":"component-2"},{"v":"27","state":"component-2"},{"v":"28","state":"component-2"},{"v":"29","state":"component-2"},{"v":"30","state":"component-2"},{"v":"31","state":"component-2"},{"v":"32","state":"component-2"},{"v":"33","state":"component-2"},{"v":"26","state":"component-2"},{"v":"25","state":"component-2"}]}],"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}"}