Depth-First Search (DFS)

Overview

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

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

The Depth-First Search (DFS) algorithm is based on the principle of backtracking and proceeds as follows:

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 on the top of the stack into the stack, and mark it as visited. If multiple unvisited neighbors exist, select one arbitrarily or according to a predefined 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 within the same connected component as the start node will be traversed. Nodes in other connected components are excluded from the traversal results.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
INSERT (A:default {_id: "A"}),
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (A)-[:default]->(B),
       (A)-[:default]->(D),
       (B)-[:default]->(E),
       (C)-[:default]->(A),
       (E)-[:default]->(F),
       (F)-[:default]->(C),
       (G)-[:default]->(D);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: traverse

File Writeback

UQL
algo(traverse).params({
  projection: "my_hdc_graph",
  return_id_uuid: "id",
  ids: ['B'],
  direction: 'in',
  traverse_type: 'dfs'
}).write({
  file: {
    filename: "visited_nodes"
  }
})

Result:

File: visited_nodes
nodes
B,A,C,F,E,