Let \(G(V,E)\) be a directed or undirected graph and let \(f\) be its adjacency list representation. Let \(v\in V\) be one of its vertices and \(m\in\mathbb N\).

The following algorithm \(\mathtt{getCOMPONENT(G,v,m)}\) obtains correctly the component containing \(v\).

The time complexity of the algorithm is \(\mathcal O (|V|+|E|)\).

Implementation notes

Please note that the for-next loop in the lines \(1\) to \(3\) has to be omitted, if the algorithm is used as a subprogram of more general algorithms also making use of the array visited, e.g. the algorithm to obtain all components of a graph get_components(G). Otherwise, this loop would destroy the information about visited nodes obtained during the more general algorithm.

Algorithm: Get the Component Induced by Vertices Connected to a Given Vertex

FOR v_i\in V\setminus{v} visited[v_i]:=NIL; // unmark all other vertices in \(G\) (still unvisited) NEXT visited[v]:=m; // mark \(v\) as visited

L:=(v); // create a list \(L\) containing only the vertex \(v\) WHILE L\neq () DO // while L is not empty u:=L.removeFirst(); // remove the first node from \(L\) and denoted it by \(u\) FOR n\in f(u)// for all successors (neighbors) \(n\) of \(u\) IF visited[n] = NIL THEN // if the neighbor \(n\) has not yet been visited visited[n]:=m; // visit neighbor node L.append(n); // and append it to the list \(L\) ENDIF NEXT ENDWHILE

G':=\emptyset; // create an empty graph FOR v\in V IF visited[v]\neq NIL THEN G':=G' + G[v]; // add all visited vertices to the component \(G'\) (including all adjacent edges) ENDIF NEXT

RETURN G';// return component induced by all visited nodes in \(G\).

Proofs: 1 2

Proofs: 1


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

Github:
bookofproofs


References

Bibliography

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