Depth First Search Random Select Node/Vertex

Question

I want to find a path to goal from start node using iterative depth first search using this maze represented in graph. It is a text file containing only pair of numbers like a pairwise connection a.k.a edges/arcs. Like this:

Then my code is like this:

private void performIterativeDFS(MazeGraph G, int node, int goal) {
        ArrayBasedStack arrayStack = new ArrayBasedStack();
        ArrayBasedStack pathStack = new ArrayBasedStack();
        arrayStack.push(node);
        visited[node] = true;
        while (!arrayStack.isEmpty()) {
            int newNode = arrayStack.pop();
            if (newNode == 0) {
                out.print("Starting at " + newNode + " ");
            }
            pathStack.push(newNode);
            if (newNode == goal) {
                out.println("Path if goal found: " + pathStack.toString());
            }
            for (int arc : G.getAdjacencyList(newNode)) {
                if (!visited[arc]) {
                    visited[arc] = true;
                    arrayStack.push(arc);
                }
            }
        }
    }

I have input 0 as a starting node and goal node is 1. Then the path that output is 0,5,7,8,9,10,6,4,1. Unfortunately, that's not like a proper solution where you can go 0,5,4,1 instead. Does iterative depth first search randomly selects which nodes to go next before reaching the goal?

I tried modifying my code to do that but I can't make the path to print like 0,5,4,1. I want to keep it simple as possible so it is for everyone to understand. Any suggestions or advice?

For those who don't know, BFS stands for Breadth First Search — Steve Knabe
I had a breadth-first as well which is fine for me. I just want to know if there is another way of doing that using depth-first search only. — Muhammad Catubig
Basically, Yes. Isn't this optimal for that? Breadth First Search is the best way to find shortest path. — Muhammad Catubig

Tosh Tosh · Accepted Answer · 2015-12-09T23:51:03

You won't get a different answer from your search without changing your algorithm(which would not make it a dfs) or (map which would be a waste of time if you were trying to make it for anything besides this specific data set). you could try implementing a sort of backtrace after the code has found a path to reduces the number of nodes traversed, but that wouldn't be the simple answer you're looking for.

Short answer: no, that's not really how DFS works.

EDIT: missed a bit of your question, there's nothing in your code that makes it random. if, rather than

for (int arc : G.getAdjacencyList(newNode)) {
            if (!visited[arc]) {
                visited[arc] = true;
                arrayStack.push(arc);
            }

you randomly sampled G, then you would have a chance of getting the a different outcome, but as it is there is no random element to it.

Depth First Search Random Select Node/Vertex

1 Answers