我在邻接矩阵中进行 DFS 回溯时遇到问题。这是我的代码: (我将测试添加到主程序中,以防有人想测试它)
public class Graph {
private int numVertex;
private int numEdges;
private boolean[][] adj;
public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.numEdges = numEdges;
this.adj = new boolean[numVertex][numVertex];
}
public void addEdge(int start, int end){
adj[start-1][end-1] = true;
adj[end-1][start-1] = true;
}
List<Integer> visited = new ArrayList<Integer>();
public Integer DFS(Graph G, int startVertex){
int i=0;
if(pilha.isEmpty())
pilha.push(startVertex);
for(i=1; i<G.numVertex; i++){
pilha.push(i);
if(G.adj[i-1][startVertex-1] != false){
G.adj[i-1][startVertex-1] = false;
G.adj[startVertex-1][i-1] = false;
DFS(G,i);
break;
}else{
visited.add(pilha.pop());
}
System.out.println("Stack: " + pilha);
}
return -1;
}
Stack<Integer> pilha = new Stack();
public static void main(String[] args) {
Graph g = new Graph(6, 9);
g.addEdge(1, 2);
g.addEdge(1, 5);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
g.addEdge(6, 4);
g.DFS(g, 1);
}
}
我正在尝试解决欧拉路径问题。该程序解决了基本图形,但当它需要回溯时,它就是不这样做。我认为问题可能出在堆栈操作或递归 dfs 调用中。我已经尝试了很多事情,但似乎仍然无法弄清楚为什么它不回溯。有人可以帮助我吗?
最佳答案
我只对此进行了测试,所以不要相信我的代码。
public class Graph {
private int numVertex;
private boolean[][] adj;
public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.adj = new boolean[numVertex][numVertex];
}
public void addEdge(int start, int end){
adj[start-1][end-1] = true;
adj[end-1][start-1] = true;
}
List<Integer> visited = new ArrayList<Integer>();
public void DFS(Graph G, int startVertex){
int i=0;
pilha.push(startVertex);
while (!pilha.empty()) {
int v = pilha.peek();
Boolean hasNeighbor = false;
for (i = 1; i <= G.numVertex; i++) {
if(G.adj[i-1][v-1] != false) {
hasNeighbor = true;
pilha.push(i);
G.adj[i-1][v-1] = false;
G.adj[v-1][i-1] = false;
break;
}
}
if (!hasNeighbor) {
visited.add(0, pilha.pop());
}
}
System.out.println("Path: " + visited);
}
Stack<Integer> pilha = new Stack<Integer>();
public static void main(String[] args) {
Graph g = new Graph(6, 9);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.addEdge(6, 4);
g.addEdge(4, 2);
g.addEdge(2, 1);
g.DFS(g, 1);
}
}
此外,您应该编辑同一问题,而不是在尝试解决同一问题时多次发布同一问题。
关于java - 使用java进行DFS回溯,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9830920/