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.