Depth-First Search (DFS)

Overview

Graph traversal is a search technique used to visit and explore all the nodes of a graph systematically. The primary goal of graph traversal is to uncover and examine the structure and connections of the graph. There are two common strategies for graph traversal:

• Breadth-First Seach (BFS)
• Depth-First Search (DFS)

The Depth-First Search (DFS) algorithm operates based on the backtracking principle and follows these steps:

1. Create a stack (last in, first out) to keep track of visited nodes.
2. Start from a selected node, push it into the stack, and mark it as visited.
3. Push any unvisited neighbor of the node at the top of the stack into the stack, and mark it as visited. If there are multiple unvisited neighbors, choose one arbitrarily or based on a certain order.
4. Repeat step 3 until there are no more unvisited neighbors to push into the stack.
5. When there are no new nodes to visit, backtrack to the previous node (the one from which the current node was explored) by popping the top node from the stack.
6. Repeat steps 3, 4 and 5 until the stack is empty.

Below is an example of traversing the graph using the DFS approach, starting from node A and assuming to visit neighbors in alphabetical order (A~Z):

Considerations

• Only nodes that are in the same connected component as the start node can be traversed. Nodes in different connect components will not be included in the traversal results.

Syntax

• Command: algo(traverse)
• Parameters:

Examples

File Writeback

UQL
algo(traverse).params({
  ids: ['B'],
  direction: 'in',
  traverse_type: 'dfs'
}).write({
  file: {
      filename: 'result'
  }
})

Results: File result

File
F,C
E,F
C,A
B,B
A,B