Java DFS在邻接矩阵中的回溯

Question

我正在执行DFS搜索以在邻接矩阵中运行。有了这个我想解决deuuler路径问题。

我已经有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+1][numVertex+1]; 
} 

public void addEdge(int start, int end){ 
    adj[start][end] = true; 
    adj[end][start] = true; 
} 

List<Integer> visited = new ArrayList<Integer>(); 

public Integer DFS(Graph G, int startVertex){ 
    int i=0; 
    pilha.push(startVertex); 
    for(i=0; i<G.numVertex; i++){ 

     if(G.adj[i][startVertex] != false){ 
      System.out.println("i: " + i); 
      G.adj[i][startVertex] = false; 
      G.adj[startVertex][i] = false; 

      DFS(G, i); 
      pilha.push(i); 

      G.adj[i][startVertex] = true; 
      G.adj[startVertex][i] = true; 
     } 

/*   else{ 
      pilha.pop(); 
     }*/ 

     if(!pilha.isEmpty()){ 
     int c = pilha.pop(); 

     visited.add(c); 
     System.out.println("visited: " + visited); 
     } 

    } 
    return -1; 
} 

Stack<Integer> pilha = new Stack(); 

public static void main(String[] args) { 

    Scanner input = new Scanner(System.in); 

    int numVertices = input.nextInt(); 
    int numLinks = input.nextInt(); 
    int startNode = input.nextInt(); 

    Graph g = new Graph(numVertices, numLinks); 

    for(int i = 0; i<numLinks; i++){ 
     g.addEdge(input.nextInt(),input.nextInt()); 
    } 

    g.DFS(g, startNode); 
} 
} 

的问题是，每当我试图运行被注释掉的流行，我得到的EmptyStackException。关于如何修改我的代码的任何想法，以便它在尝试访问已经访问过的边时会回溯。

Thx提前。

Answer 1

如果startvertex不与某个顶点i相邻，那么你的其他部分就会执行。 只有在startvertex不与任何顶点i相邻的情况下，

我会做这样的事情：

bool hasAdjacent = False; 
for(i=0; i<G.numVertex; i++){ 
    if(G.adj[i][startVertex] != false){ 
     hasAdjacent = True; 
     ... 

    } 
} 
if (!hasAdjacent) { 
    int c = pilha.pop(); 
    visited.add(c); 
} 

我不会给你一个完整的解决方案，但我认为这能解决您的主要逻辑问题。