javascript-algorithms

javascript-algorithms copied to clipboard

Hi,

I would like to know if you have an algorithm to find all possible paths (cyclic or acyclic) in a directed graph from certain node A to B. Although both depth and breadth search are on the folder '/src/algorithms/graph/', I must have certain creativity to extract the routes by given callback function.

I really appreciate the work you have done here.

Best regards, Bruno P.

The list could easily be infinite for a simple A <-> B. You'd need to define the problem better.

A first step would be to find all possible cycles in a graph. How: A first approach is to depth-search from an origin node: If one of the neighbors to current node belongs to the current route, persist the cycle in a list and backtrack it, removing from LocalPathList;

A second step is to go along a route with inbetween cycles: every cycle may be traversed only once along the same route.

Example: Given a graph with adjacency matrix given by object {'A': ['B'], 'B": ['C'], 'C': ['D', 'E', 'F'], 'D': [], 'E': ['B'], 'F': ['B']}, the possible paths from A to D must be ['ABCD', 'ABCEBD', 'ABCFBD'].