'DFS is not working properly for undirected graph
I want to use DFS to find all possible paths from one source vertex to a destination vertex. Being new to recursion, I am just completely lost in how I would have my recursive method perform such a function.
The code I have right now only finds one path and exits the method after the vertex had been found.
The code I have:
public Node DFSTime(Node node) {
// Boolean to check if the destination airport is found and then exit the
// recursive method
boolean ifreached = false;
// Check if the node is the destination airport
if (node.element.equals(destinationAirport)) {
stack.push(node);
return null;
} else {
int index = 0;
stack.push(node);
// Find the exact index of the node in the adjacency list
for (int i = 0; i < adjList.adjMatrix.size(); i++) {
if (adjList.adjMatrix.get(i).head.element.equals(node.element) == true) {
index = i;
break;
}
}
// Check if the node is already visited
if (visited.contains(node.element.toString()) == false) {
visited.add(node.element.toString());
}
Node currentNode = adjList.adjMatrix.get(index).head.nextNode;
// counter to keep track of the number of neighbors visited
int counter = 0;
// Iterating through the linked list at adjMatrix[index]
while (currentNode != null) {
// If visited then skip
if (visited.contains(currentNode.element) == false) {
previousAirport = node.element.toString();
Node temp = DFSTime(currentNode);
//If the destination airport is found then exit the recursive method
if (temp == null) {
ifreached = true;
break;
}
}
//Iterate to the next neighbor
currentNode = currentNode.nextNode;
counter++;
}
// If the destination airport is not found after iterating through the neighbors
// then pop the stack
if (counter == adjList.adjMatrix.get(index).size - 1) {
Node temp = stack.pop();
previousAirport = temp.element.toString();
visited.remove(temp.element.toString());
return temp;
}
}
// If the destination airport is found then return null
if (ifreached == true) {
return null;
}
return node;
}
This question is similar to another question I asked, and so I basically tried to change a few things from that question for my recursive method.
The Stack is a linked list stack I implemented. And the adjacency list is an ArrayList of Linked Lists.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
