深度优先搜索的java实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18896251/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
java implementation of Depth First Search
提问by jake
the following code has no errors,but the output i am getting is not correct
以下代码没有错误，但我得到的输出不正确
import java.io.*;
class dfs
{
static void dfs(int a[][], int m[], int i, int n)
{
int j;
System.out.println("\t" + (i+1));
m[i] = 1;
for(j=0; j<n; j++)
if(a[i][j]==1 && m[j]==0)
dfs(a,m,j,n);
}
public static void main(String args[]) throws IOException
{
int n, i, j;
System.out.println("No. of vertices : ");
BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
n =Integer.parseInt(br.readLine());
int m[]= new int[n];
int a[][] = new int[n][n];
for (i=0; i<n; i++)
{
m[i] = 0;
}
System.out.println("\n\nEnter 1 if edge is present, 0 if not");
for (i=0; i<n; i++)
{
System.out.println("\n");
for (j=i; j<n; j++)
{
System.out.println("Edge between " + (i+1) + " and " + (j+1)+ " : ");
a[i][j] =Integer.parseInt(br.readLine());
a[j][i]=a[i][j];
}
a[i][i] = 0;
}
System.out.println("\nOrder of accessed nodes : \n");
for (i=0; i<n; i++)
if (m[i]==0)
dfs(a,m,i,n);
}
}
Output Example
输出示例
No of vertices : 8
edges
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 8
7 8
the DFS path should be : 1 2 4 8 5 3 6 7
DFS 路径应该是：1 2 4 8 5 3 6 7
the output i am getting is : 1 2 4 8 5 6 3 7
我得到的输出是：1 2 4 8 5 6 3 7
notice that the 6 th and 7 th terms are interchanged
请注意，第 6 项和第 7 项是互换的
can anyone tell me how to correct this.thanks for your help
谁能告诉我如何纠正这个。谢谢你的帮助
采纳答案by ajb
The output you're getting is correct for an undirected graph. The list of edges you provided includes (6,8), but a DFS can travel from 8 to 6 just as well as from 6 to 8 since it's undirected. If you want a directed graph, you'll have to make a couple changes in how the aarray is set up.
您获得的输出对于无向图是正确的。您提供的边列表包括 (6,8)，但 DFS 可以从 8 到 6 以及从 6 到 8 行进，因为它是无向的。如果需要有向图，则必须对a数组的设置方式进行一些更改。
回答by user902383
i change implementation of your dfs, now it shopuld works, if you use names of variables, to make them more recognizable, you can get your help quicker
我改变了你的 dfs 的实现，现在它可以工作了，如果你使用变量名，让它们更容易识别，你可以更快地得到你的帮助
static void dfs(int adjacencyMatrix[][], int vertex, int[] visited) {
System.out.println("visiting " + (vertex + 1) );
for (int j = vertex + 1; j < adjacencyMatrix[vertex].length; j++)
if (adjacencyMatrix[vertex][j] == 1 && visited[j] == 0) {
visited[j] = 1;
dfs(adjacencyMatrix, j, visited);
}
}
回答by Filipe Gon?alves
The output is correct. With your example, the recursion stops when i = 4 in dfs() (stops in vertex 5), and it winds back to vertex 8, where it came from (with i = 7). In this call, we have just returned from j = 4 (the one that had no more adjacent vertexes). The loop index is incremented (j++), and because vertex 8 is connected to vertex 6 (j = 5), the next recursive call will have i = 5, so you are visiting vertex 6. From vertex 6, the recursion goes to 3 and then 7, and then everything winds back.
输出是正确的。在您的示例中，递归在 dfs() 中的 i = 4 时停止（在顶点 5 中停止），并返回到它来自的顶点 8（i = 7）。在这个调用中，我们刚刚从 j = 4（没有更多相邻顶点的那个）返回。循环索引递增（j++），并且因为顶点 8 连接到顶点 6（j = 5），所以下一次递归调用将有 i = 5，所以你正在访问顶点 6。从顶点 6 开始递归到 3然后是 7，然后一切又回来了。
回答by Mohammad
You can try this implementation of DFS:
你可以试试这个 DFS 的实现：
import java.util.ArrayList;
import java.util.List;
public class TreeTraverse {
static class Node{
Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
int data;
Node left;
Node right;
boolean visited;
}
public static void main(String[] args) {
//The tree:
// 1
// / \
// 7 9
// \ / \
// 8 2 3
Node node1 = new Node(1);
Node node7 = new Node(7);
Node node9 = new Node(9);
Node node8 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node7;
node1.right = node9;
node7.right = node8;
node9.right = node3;
node9.left = node2;
System.out.println("DFS: ");
depthFirstSearch(node1);
}
private static void depthFirstSearch(Node node){
if(node.left == null && node.right == null){
System.out.print(node.data+" ");
node.visited = true;
}else if(node.left == null || node.left.visited){
depthFirstSearch(node.right);
System.out.print(node.data+" ");
node.visited = true;
}else{
depthFirstSearch(node.left);
node.visited = true;
System.out.print(node.data+" ");
depthFirstSearch(node.right);
}
}
}
This is a recursive implementation of it. For more information please visit: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java. I hope it helps.
这是它的递归实现。更多信息请访问：https: //github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java。我希望它有帮助。
