◀ ▲ ▶Branches / Graph-theory / Algorithm: Get All Components of a Graph

Let \(G(V,E)\) be a undirected graph. Then the following algorithm get_components(G) obtains correctly the set of all components of \(G\) and its time complexity is \(\mathcal O(|V|+|E|)\).

Algorithm: Get All Components of a Graph

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function get_components(G):
    G.unvisit_all_vertices()

    C=set()  # initiate empty set of all components  
    m=0
    for v in G.V:
        if not v.is_visited():
            m += 1  # increase the component number 
            C = C.union(getCOMPONENT(G,v,m))  # obtain the m-th component and add it as an element of C  
        # at this stage, the 'visited' argument of all vertices of the last component is marked by m. 
    return C # return the set of all components

Table of Contents

Proofs: 1 2

Mentioned in:

Algorithms: 1
Definitions: 2

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition