Full Question:
Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist.
Depth-First Search (DFS)
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.
Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn't finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.
*must see Breadth-First Search (BFS) to compare and understanding graph traversal deeply. Interviewer may ask BFS after DFS.
Below pseudo code shows DFS algorithm.
Not considering edges, the algorithm can be simple.
Describe the algorithm for a depth-first graph traversal.
Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist.
Depth-First Search (DFS)
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.
Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn't finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.
*must see Breadth-First Search (BFS) to compare and understanding graph traversal deeply. Interviewer may ask BFS after DFS.
Below pseudo code shows DFS algorithm.
algorithm DFT(G,v):
label v as visited
for all edges e in G.incidentEdges(v) do
if edge e is unvisited then
w ← G.opposite(v,e)
if vertex w is visited then
label e as a discovery edge
recursively call DFT(G,w)
else
label e as a back edge
label v as visited
for all edges e in G.incidentEdges(v) do
if edge e is unvisited then
w ← G.opposite(v,e)
if vertex w is visited then
label e as a discovery edge
recursively call DFT(G,w)
else
label e as a back edge
Not considering edges, the algorithm can be simple.
algorithm DFT(x)
visit(x); x<-visited;
FOR each y such that (x,y) is an edge DO
IF y != visited THEN
DFT(y)
visit(x); x<-visited;
FOR each y such that (x,y) is an edge DO
IF y != visited THEN
DFT(y)
Describe the Algorithm for a Depth-First Graph Traversal.