C++ Programming FAQ

Submit Interview FAQ
Home » Interview FAQ » C++ ProgrammingRSS Feeds

What is DFS (Depth First Search) in dfs (data file structure)?

  Shared By: Sean Brown    Date: May 06    Category: C++ Programming    Views: 1743


A depth first search of an arbitrary graph can be used to perform a traversal of a general graph. The strategy is as follows. A node s is picked as a start node and marked. An unmarked adjacent node to s is now selected and marked, becoming the new start node; possibly leaving the original start node with unexplored edges for the present. The search continues in the graph until the current path ends at a node with outdegree zero or at a node with all adjacent nodes already marked. Then the search returns to the last node which still has unmarked adjacent nodes and continues marking until all nodes are marked. Since adjacent nodes are needed during the traversal, the most efficient representation again is an adjacency list.


Your Comment
  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].