Connectivity algorithm

Task number: 4263

Design an algorithm that for a given graph finds its components of connectivity.

  • Solution

    We will search the graph so that each vertex that has a neighbor in some component will belong to the same. Each time we need a new vertex, we start a new component. The pseudocode of the algorithm follows:

    • Initialization: All vertices receive an empty mark.
    • \( i = 0 \)
    • As long as there is an unmarked vertex \( u \) in the graph, repeat:
      • \( i ++ \)
      • Mark \( u \) with \( i \)
      • As long as there is an unmarked vertex \( v \) in the graph, its neighbor has the mark \( i \), then marke \( v \) with \( i \)
    • Answer: The graph has \( i \) components. Vertices that lie in the same component have the same marks.
Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email