Is Depth-First Search Order for Graph Traversal Direction-Agnostic?

Click For Summary

Homework Help Overview

The discussion revolves around the concept of depth-first search (DFS) in graph traversal. Participants are exploring the order of traversal starting from a specific node and questioning the directionality of the search process.

Discussion Character

  • Exploratory, Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • Participants are considering different traversal orders from a starting node and questioning the validity of various paths. There is confusion regarding what constitutes a legitimate traversal in a graph context versus a tree.

Discussion Status

Some participants have provided insights into the nature of depth-first search and its application to graphs, noting that processing unvisited neighbors is essential. However, there remains uncertainty about specific traversal sequences and what is permissible.

Contextual Notes

There is a lack of clarity regarding the rules of traversal in graphs, with participants questioning the legitimacy of certain movements and the implications of starting from different nodes.

gfd43tg
Gold Member
Messages
949
Reaction score
48
ImageUploadedByPhysics Forums1407629937.062203.jpg


Hello, I drew up this graph to try and understand the concept of depth-first search. Starting at node C, I was wondering if its correct for the order to be C-A-B-D or C-B-A-D? It seems like you can traverse in either direction without a problem.
 
Physics news on Phys.org
For me, both are valid. You could certainly look at all the children, order them by some preference and visit each one in that order.
 
I'm confused as to what movements are not allowed? It seems very unclear to me what is a legitimate traversal and what isn't. Can you go C-D-B-A or C-D-A-B? What counts as not being permitted?
 
Depth-first means the whole subtree of each child node is processed before any other child nodes are processed. Does that make sense? Your example tree is a bad example because the children of C have no children themselves.

Oh sorry, you are talking about a graph, not a tree. Hmm.
 
Ok, for a graph, depth-first must mean, process every unvisited neighbor before backtracking. CAD -- not allowed.
 

Similar threads

How to check if search problem has no solution in depth limit search?
  • · Replies 2 ·
Replies
2
Views
2K
Python Solving UnboundLocalError for Python Iterative Deepening Depth First Search
  • · Replies 1 ·
Replies
1
Views
2K
Comp Sci Exception has occurred: UnboundLocalError local variable 'depth' refer
  • · Replies 2 ·
Replies
2
Views
2K
Python Confused about recursion in python-depth first search-:
  • · Replies 3 ·
Replies
3
Views
1K
The first and second derivatives at various points on a drawn graph
  • · Replies 22 ·
Replies
22
Views
3K
Strong Induction, Tangled Graph
  • · Replies 3 ·
Replies
3
Views
3K
Graphing Derivatives: Concavity and Inflection Points
  • · Replies 4 ·
Replies
4
Views
3K
C data structures and algorithms - graph problem
  • · Replies 2 ·
Replies
2
Views
2K
Solutions of first-order matrix differential equations
  • · Replies 5 ·
Replies
5
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
3K