Computing Connected Components

components(G):
| Input graph G
|
| for all vertices v∈G do
| componentOf[v]=-1
| end for
| compID=0
| for all vertices v∈G do
| | if componentOf[v]=-1 then
| | dfsComponents(G,v,compID) | | compID=compID+1
| | end if
| end for
dfsComponents(G,v,id):
| componentOf[v]=id
| for all vertices w adjacent to v do
|if componentOf[w]=-1 then
|dfsComponents(G,v,id)
|end if
| end for
if componentOf[w]=-1 then dfsComponents(G,w,id)
end if

Algorithm for finding Hamiltonian path:

Exercise #3: Hamiltonian Path

Algorithm to check whether a graph has an Euler path:

Digraph Applications

Exercise #6: Transitive Closure