隣接行列でDFSバックトラッキングに問題があります。ここに私のコードは次のとおりです。 (私は、誰かがそれをテストしたい場合には、メインにテストを追加しました)DFSバックトラックwith java
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呼び出しで問題が発生している可能性があります。私はたくさんのことを試しましたが、なぜそれが逆戻りしないのか分かりません。誰かが私を助けることができますか?
numEdgesは役に立たない。 – ysdx
今は役に立たない、そうだよ。 –
返品するDFSとは何ですか? -1だけを返すことができます。 – ysdx