Java: Depth First Search returns path in wrong order

I am trying to implement a graph class with a depth first search algorithm, following an undirected graph interface of an assignment. I am new to this kind of algorithm and not sure I am doing it right.

The depth first search method is supposed to return a path between two given nodes, but mine returns a path with the wrong order. Ï would really appreciate some help. I hope I haven’t forgotten to include anything. If so, please let me know.

Part of Node class:

class Node<T> { 

    private T id;
    private ArrayList<Edge<T>> edgeList;

    public Node(T id) {
        this.id = id;
        edgeList = new ArrayList<Edge<T>>();
    }

    public T getNodeID() {
        return id;
    }

    public void addEdge(Edge<T> edge) {
        edgeList.add(edge);
    }

    public ArrayList<Edge<T>> getEdgeList() {
        return edgeList;
    }

Part of Edge class:

class Edge<T> {

    private Node<T> firstNode;
    private Node<T> secondNode;
    private int weight;

    public Edge(Node<T> firstNode, Node<T> secondNode, int weight) {
        this.firstNode = firstNode;
        this.secondNode = secondNode;
        this.weight = weight;
    }

    public Node<T> getFirstNode() {
        return firstNode;
    }

    public Node<T> getSecondNode() {
        return secondNode;
    }

Graph class has a hash map of node ID keys and node values:

private HashMap<T, Node<T>> nodeMap = new HashMap<>();

Depth first search code:

public List<T> depthFirstSearch(T start, T end) {

if (start == null || end == null) {
    return null;
}

List<T> visited = new ArrayList<>();
Stack<T> stack = new Stack<>();

stack.push(start);

if (start.equals(end)) {
    return stack;
}

while (!stack.isEmpty()) {

    T topNode = stack.pop();
    visited.add(topNode);

    for (T neighbor : getNodeNeighbors(topNode)) {

        if (!visited.contains(neighbor)) {

            if (neighbor.equals(end)) {
                
                stack.push(end);
                visited.add(end);
                return visited;
            
            } else {
                stack.push(neighbor);
            }
        }
    }
}

return visited;
}

public ArrayList<T> getNodeNeighbors(T nodeID) {

Node<T> n = nodeMap.get(nodeID);

if (n == null) {
    return null;
}

ArrayList<T> neighbors = new ArrayList<T>();

for (Edge<T> e : n.getEdgeList()) {

    // Add the nodes neighbor ID, not the nodes ID
    if (!e.getFirstNode().getNodeID().equals(nodeID)) {
        neighbors.add(e.getFirstNode().getNodeID());
    }

    if (!e.getSecondNode().getNodeID().equals(nodeID)) {
        neighbors.add(e.getSecondNode().getNodeID());
    }
        
}

return neighbors;

}


Read more here: https://stackoverflow.com/questions/66343551/java-depth-first-search-returns-path-in-wrong-order

Content Attribution

This content was originally published by Nathalie at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: