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) { = id;
        edgeList = new ArrayList<Edge<T>>();

    public T getNodeID() {
        return id;

    public void addEdge(Edge<T> 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<>();


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

while (!stack.isEmpty()) {

    T topNode = stack.pop();

    for (T neighbor : getNodeNeighbors(topNode)) {

        if (!visited.contains(neighbor)) {

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

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)) {

    if (!e.getSecondNode().getNodeID().equals(nodeID)) {

return neighbors;


Read more here:

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: