ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Find All Paths in a Graph Using Depth-First Search

Cypher (Neo4j)

Goal -- WPM

Ready
Exercise Algorithm Area
1MATCH (startNode:Node {id: $startId}), (endNode:Node {id: $endId})

2CALL {

3WITH startNode, endNode

4// Helper function to perform DFS recursively

5FUNCTION dfsPaths(currentNode, targetNode, visitedNodes, currentPath)

6{

7// Base case: If the current node is the target node, return the current path.

8IF currentNode = targetNode THEN

9RETURN currentPath + [currentNode.id]

10END

11

12// Mark the current node as visited to prevent cycles.

13SET visitedNodes = visitedNodes + [currentNode.id]

14

15// Initialize an empty list to store all paths found from this node.

16LET allFoundPaths = []

17

18// Iterate over all neighbors of the current node.

19FOR neighbor IN CALL apoc.neighbors.nodes(currentNode) WHERE NOT neighbor.id IN visitedNodes

20{

21// Recursively call DFS for each unvisited neighbor.

22LET pathsFromNeighbor = dfsPaths(neighbor, targetNode, visitedNodes, currentPath + [currentNode.id])

23

24// Add all paths found from the neighbor to the list of all found paths.

25FOREACH path IN pathsFromNeighbor DO

26SET allFoundPaths = allFoundPaths + [path]

27END

28}

29

30// Return all paths found starting from this node.

31RETURN allFoundPaths

32}

33

34// Initial call to the DFS helper function.

35// Start with the startNode, targetNode, an empty visited set, and an empty path.

36RETURN dfsPaths(startNode, endNode, [], []) AS paths

37}

38RETURN paths
Algorithm description viewbox

Find All Paths in a Graph Using Depth-First Search

Algorithm description:

This Cypher query implements a recursive Depth-First Search (DFS) algorithm to find all possible paths between a specified start node and end node in a graph. It's useful for analyzing network connectivity, exploring relationships in social networks, or finding all possible routes in a map-like structure.

Algorithm explanation:

The algorithm uses a recursive DFS approach. The `dfsPaths` function takes the current node, target node, a list of visited nodes, and the current path as arguments. The base case is when the `currentNode` equals the `targetNode`, at which point the current path is returned. To prevent infinite loops in graphs with cycles, the algorithm maintains a `visitedNodes` list. Before exploring neighbors, the current node is added to `visitedNodes`. For each neighbor that has not been visited, the `dfsPaths` function is called recursively. The paths returned from these recursive calls are aggregated. The time complexity is roughly O(V + E) in a Directed Acyclic Graph (DAG), but can be exponential in graphs with many cycles, as it explores all possible paths. The space complexity is O(V) for the recursion stack and visited set in the worst case.

Pseudocode:

FUNCTION dfsPaths(currentNode, targetNode, visitedNodes, currentPath):
  IF currentNode IS targetNode:
    RETURN currentPath + [currentNode.id]
  END

  ADD currentNode.id TO visitedNodes
  LET allFoundPaths = []

  FOR EACH neighbor OF currentNode:
    IF neighbor.id IS NOT IN visitedNodes:
      LET pathsFromNeighbor = dfsPaths(neighbor, targetNode, visitedNodes, currentPath + [currentNode.id])
      ADD pathsFromNeighbor TO allFoundPaths
    END
  END

  RETURN allFoundPaths
END FUNCTION

// Main execution:
CALL dfsPaths(startNode, endNode, [], [])