CODEWITHSUNDEEP
algorithmlanguage-agnosticgraph
Morrowless
Morrowless

Reputation: 6958

Finding all unique paths in an undirected graph

I have a problem where I need to search for all unique paths in an undirected graph of degree <=4. The graph is basically a grid, and all connections are between direct neighbors only (4-way).

How do I go about this problem?

enter image description here

Upvotes: 2

Views: 6042

Answers (1)

Argote
Argote

Reputation: 2155

Here's the pseudocode I just came up with:

  1. Start at any node.
  2. Get all of its paths
  3. See where they lead, if it's a node that has not been visited then visit it.
  4. Call the same function recursively for the nodes from the previous paths.
  5. Keep a counter for the number of paths.

This would be this code in Java (untested):

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;
}

This should find the paths from one starting node. You can start it on each node but you'd get some duplicates. To weed them out you'd also need to return the paths though.

Upvotes: 2

Related Questions