Editing Component (graph theory) (section)

==Algorithms==
It is straightforward to compute the components of a finite graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either [[breadth-first search]] or [[depth-first search]]. In either case, a search that begins at some particular {{nowrap|vertex <math>v</math>}} will find the entire component {{nowrap|containing <math>v</math>}} (and no more) before returning. All components of a graph can be found by looping through its vertices, starting a new breadth-first or depth-first search whenever the loop reaches a vertex that has not already been included in a previously found component.  {{harvtxt|Hopcroft|Tarjan|1973}} describe essentially this algorithm, and state that it was already "well known".{{r|hoptar}}

[[Connected-component labeling]], a basic technique in computer [[image analysis]], involves the construction of a graph from the image and component analysis on the graph.
The vertices are the subset of the [[pixel]]s of the image, chosen as being of interest or as likely to be part of depicted objects. Edges connect [[pixel connectivity|adjacent pixels]], with adjacency defined either orthogonally according to the [[Von Neumann neighborhood]], or both orthogonally and diagonally according to the [[Moore neighborhood]]. Identifying the connected components of this graph allows additional processing to find more structure in those parts of the image or identify what kind of object is depicted.  Researchers have developed component-finding algorithms specialized for this type of graph, allowing it to be processed in pixel order rather than in the more scattered order that would be generated by breadth-first or depth-first searching. This can be useful in situations where sequential access to the pixels is more efficient than random access, either because the image is represented in a hierarchical way that does not permit fast random access or because sequential access produces better [[memory access pattern]]s.{{r|dst}}

There are also efficient algorithms to dynamically track the components of a graph as vertices and edges are added, by using a [[disjoint-set data structure]] to keep track of the partition of the vertices into equivalence classes, replacing any two classes by their union when an edge connecting them is added. These algorithms take [[amortized analysis|amortized]] time <math>O(\alpha(n))</math> per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and <math>\alpha</math>  is a very slowly growing inverse of the very quickly growing [[Ackermann function]].{{r|bengalloun}} One application of this sort of incremental connectivity algorithm is in [[Kruskal's algorithm]] for [[minimum spanning tree]]s, which adds edges to a graph in sorted order by length and includes an edge in the minimum spanning tree only when it connects two different components of the previously-added subgraph.{{r|skiena}} When both edge insertions and edge deletions are allowed, [[dynamic connectivity]] algorithms can still maintain the same information, in amortized time <math>O(\log^2 n/\log\log n)</math> per change and time <math>O(\log n/\log\log n)</math> per connectivity query,{{r|wulff-nilsen}} or in near-logarithmic randomized [[expected time]].{{r|hhkp}}

Components of graphs have been used in [[computational complexity theory]] to study the power of [[Turing machine]]s that have a working memory limited to a [[logarithm]]ic number of bits, with the much larger input accessible only through read access rather than being modifiable. The problems that can be solved by machines limited in this way define the [[complexity class]] [[L (complexity)|L]]. It was unclear for many years whether connected components could be found in this model, when formalized as a [[decision problem]] of testing whether two vertices belong to the same component, and in 1982 a related complexity class, [[SL (complexity)|SL]], was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space [[Reduction (complexity)|reductions]].{{r|lewpap}} It was finally proven in 2008 that this connectivity problem can be solved in logarithmic space, and therefore that {{nowrap|SL {{=}} L.{{r|reingold}}}}

In a graph represented as an [[adjacency list]], with random access to its vertices, it is possible to estimate the number of connected components, with constant probability of obtaining [[absolute error|additive (absolute) error]] at most <math>\varepsilon n</math>, in [[sublinear time]] <math>O(\varepsilon^{-2}\log\varepsilon^{-1})</math>.{{r|berkramal}}