Related data structure**:
Algorithm Data_Structure Graph DFS
Graph Depth-First Search is a traversal method that prioritise going as far as possible and then backtracks when no further paths are available.
Implementation
The “go as far as possible and return” algorithm paradigm is usually implemented based on recursion. Similar to Graph Breadth-First Search (BFS), in DFS, we also use a hash set visited
to record all visited vertices to avoid revisiting.
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
List<Vertex> res = new ArrayList<>();
Set<Vertex> visited = new HashSet<>();
def(graph, visited, res, startVet);
return res;
}
void dfs(GrapghAdjList graph, Set<Vertex> visited, List<vertex> res, Vertex vet) {
res.add(vet);
visited.add(vet);
for (Vertex adjVet : graph.adjList.get(vet)) {
if (visited.contains(adjVet))
continue;
// recursive call
dfs(graph, visited, res, adjVet);
}
}
Time complexity
All vertices will be visited once, using time, all edges will be visited twice for undirected graph using ; with overall time complexity .
Back to parent node: ADT - Graph
Reference: