CODEWITHSUNDEEP
algorithmdata-structuresgraphdirected-graph
Ashera
Ashera

Reputation: 141

Finding all possible paths in a cyclic directed graph given a starting vertex and a depth limitation

Consider the directed cyclic graph given below;

enter image description here

If a starting point (eg: vertex 0) and a maximum depth allowed is specified (eg: 5), what algorithm can be used to find all possible paths (note: a given vertex can be visited more than once)?

What is the most efficient algorithm to implement this graph problem?

Some of the possible paths for the above graph are given below in no particular order (starting with vertex 0 and maximum depth allowed is 5).

Upvotes: 1

Views: 1072

Answers (1)

shapiro yaacov
shapiro yaacov

Reputation: 2346

Pseudo algorithm for this will be an augmented BFS that keeps track of the path it has gone through. When it hits the required depth, it registers the path and then terminates.

Something like this (node.js style syntax):

const requiredDepth = X
const relevantPaths = {}

const runBFS = (curNode, curPath = []) => {
    if (crPath.length === requiredDepth) {
        relevantPaths.push(curPath)
        return
    }

    for (let neighbor of curNode.neighbors) {
        const newPath = [ ...curPath, getEdge(curNode, neighbor) ]
        runBFS(neighbor, newPath)
    }
}

runBFS(root)

Hope this helps

Upvotes: 1

Related Questions