Нахождение всех уникальных путей в неориентированном графе

Question

У меня проблема с поиском всех уникальных путей в неориентированном графе степени <= 4.Граф в основном представляет собой сетку, и все соединения между прямыми соседями (4-сторонние). </p>

• Путь не может посещать одну и ту же вершину более одного раза.
• Путь может посещать любое количество вершин для создания пути.
• Путь содержит как минимум 2 вершины.

Как мне решить эту проблему?

Answer 1

Вот псевдокод, который я только что придумал:

1. Начать с любого узла.
2. Получить все его пути
3. Посмотрите, куда они ведут, если этоузел, который не был посещен, затем посетите его.
4. Вызовите ту же функцию рекурсивно для узлов из предыдущих путей.
5. Сохраните счетчик для числа путей.

Это будет следующий код на Java (не проверено):

public int getPaths (Node n, Set<Node> nodesVisited) {
    int pathCount = 0;
    for (Path p : n.getPaths()) {
        Node otherSide = p.getOtherNode(n); // Where this function basically takes a node and gets the other node in the path
        if (!(nodesVisited.contains(otherSide))) {
            nodesVisited.add(otherSide);
            pathCount += 1 + getPaths(otherSide, new Set<Nodes>(nodesVisited));
        }
    }
    return pathCount;
}

Это должно найти пути от одного начального узла.Вы можете запустить его на каждом узле, но вы получите несколько дубликатов.Чтобы отсеять их, вы также должны вернуть пути.