// globally we have a Graph G of lets say 100 nodes
vector<int>* G = new vector<int>[100];
// globally we also have a vector to store weather or not a node has been visited
vector<bool> visited(100, false);
void DFS( int node ){
// mark the current node as visited
visited[node] = true;
// for all the adjacent nodes of the current node
for( int adj : G[node] ){
// if the adjacent node is not already visited then visit it
if( !visited[adj] )
DFS( adj );
}
}
-
Traversal of Graph, explore Nodes and Edges of a Graph. code
-
Used as a building block in other Algorithms:
- Count Connected Components
- Determine Connectivity
- Find Bridges and Articulation Points in a Graph
-
For a unweighted graph DFS traversal produces
- Minimum Spanning Tree
- All Pair Shortest Path
-
Path Finding between two vertex
-
Determine Cycle in a Graph
-
To test if a graph is Bipartite
-
Topological Sort