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

Github: ### References

#### Bibliography

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