Нахождение всех возможных путей в ориентированном графе cycli c с учетом начальной вершины и ограничения глубины

Question

Рассмотрим направленный график циклических c, приведенный ниже;

Если указана начальная точка (например, вершина 0) и максимально допустимая глубина (например, 5), какой алгоритм можно использовать для найти все возможные пути (примечание: определенная вершина может быть посещена более одного раза)?

Какой самый эффективный алгоритм для реализации этой задачи графа?

Некоторые из возможных путей для вышеупомянутого ниже приведены графики в произвольном порядке (начиная с вершины 0 и максимально допустимой глубиной 5).

• 0 -> 1 -> 2 -> 4 -> 1 -> 3
• 0 -> 1 -> 2 -> 4 -> 5 -> 1
• 0 -> 1 -> 2 -> 4 -> 5 -> 6
• 0 -> 1 -> 3 -> 5 -> 1 -> 3

Answer 1

Псевдоалгоритмом для этого будет расширенная BFS, которая отслеживает пройденный путь. Когда он достигает необходимой глубины, он регистрирует путь и затем завершается.

Примерно так (синтаксис стиля node.js):

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)

Надеюсь, это поможет