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.
