Start a depth-first search from each as-yet unlabelled vertex, propagating a fresh component number:A search follows only edges, so every vertex it labels is reachable from its root. Conversely, if a reachable vertex remained unlabelled, a path to it would contain a first edge from a visited vertex to an unvisited one; scanning that edge would visit the latter, a contradiction. Thus each search labels exactly one connected component, proving both directions of the required equivalence.
component = 0
for u in V:
cc[u] = UNLABELLED
for u in V:
if cc[u] == UNLABELLED:
visit(u, component)
component = component + 1
visit(u, label):
cc[u] = label
for v in adjacency[u]:
if cc[v] == UNLABELLED:
visit(v, label) Articles by others on the same topic
There are currently no matching articles.