Java深度优先搜索
时间：2020-02-23 14:34:03 来源:igfitidea点击:
在本教程中，我们将看到如何在Java中实现深度第一搜索(DFS)。
图遍历算法
- 广度首次搜索Java
- 深度首次搜索Java
在DFS中，我们从无访问的节点开始并开始挑选相邻节点，直到我们无法选择，然后我们回溯，直到我们有另一个选择要选择一个节点，如果没有，则选择另一个未访问的节点。
DFS可以以两种方式实现。
- 递归
- 迭代
迭代
可以使用迭代方法实现深度第一搜索。
让我们在举例的帮助下看：
我们从节点40开始。
然后，它分别访问节点20，节点50，节点70，因为它们直接连接。
之后，它分别向节点20和访问节点60，节点30和节点10来回溯。
//Iterative DFS using stack
public void dfsUsingStack(Node node)
{
Stack<Node> stack=new Stack<Node>();
stack.add(node);
while (!stack.isEmpty())
{
Node element=stack.pop();
if(!element.visited)
{
System.out.print(element.data + " ");
element.visited=true;
}
List<Node> neighbours=element.getNeighbours();
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
stack.add(n);
}
}
}
}
递归
深度首先搜索也可以使用递归来实现。
我们不需要维护外部堆栈，它将通过递归进行保养。
//Recursive DFS
public void dfs(Node node)
{
System.out.print(node.data + " ");
List neighbours=node.getNeighbours();
node.visited=true;
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
dfs(n);
}
}
}
Java DFS示例
有两种方法来表示图。
- 使用邻居列表
- 使用邻接矩阵
使用邻居列表
在此，我们可以将列表<node>作为节点类中的邻居。
static class Node
{
int data;
boolean visited;
List<Node> neighbours;
Node(int data)
{
this.data=data;
this.neighbours=new ArrayList<>();
}
public void addneighbours(Node neighbourNode)
{
this.neighbours.add(neighbourNode);
}
public List getNeighbours() {
return neighbours;
}
public void setNeighbours(List neighbours) {
this.neighbours = neighbours;
}
}
以下是用于迭代和递归方法的DFS实现的完整Java程序。
package org.arpit.theitroad;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class DepthFirstSearch示例 NeighbourList
{
static class Node
{
int data;
boolean visited;
List<Node> neighbours;
Node(int data)
{
this.data=data;
this.neighbours=new ArrayList<>();
}
public void addneighbours(Node neighbourNode)
{
this.neighbours.add(neighbourNode);
}
public List<Node> getNeighbours() {
return neighbours;
}
public void setNeighbours(List<Node> neighbours) {
this.neighbours = neighbours;
}
}
//Recursive DFS
public void dfs(Node node)
{
System.out.print(node.data + " ");
List<Node> neighbours=node.getNeighbours();
node.visited=true;
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
dfs(n);
}
}
}
//Iterative DFS using stack
public void dfsUsingStack(Node node)
{
Stack<Node> stack=new Stack<Node>();
stack.add(node);
while (!stack.isEmpty())
{
Node element=stack.pop();
if(!element.visited)
{
System.out.print(element.data + " ");
element.visited=true;
}
List<Node> neighbours=element.getNeighbours();
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
stack.add(n);
}
}
}
}
public static void main(String arg[])
{
Node node40 =new Node(40);
Node node10 =new Node(10);
Node node20 =new Node(20);
Node node30 =new Node(30);
Node node60 =new Node(60);
Node node50 =new Node(50);
Node node70 =new Node(70);
node40.addneighbours(node10);
node40.addneighbours(node20);
node10.addneighbours(node30);
node20.addneighbours(node10);
node20.addneighbours(node30);
node20.addneighbours(node60);
node20.addneighbours(node50);
node30.addneighbours(node60);
node60.addneighbours(node70);
node50.addneighbours(node70);
DepthFirstSearch示例 NeighbourList dfs示例 = new DepthFirstSearch示例 NeighbourList();
System.out.println("The DFS traversal of the graph using stack ");
dfs示例 .dfsUsingStack(node40);
System.out.println();
//Resetting the visited flag for nodes
node40.visited=false;
node10.visited=false;
node20.visited=false;
node30.visited=false;
node60.visited=false;
node50.visited=false;
node70.visited=false;
System.out.println("The DFS traversal of the graph using recursion ");
dfs示例 .dfs(node40);
}
}
运行上面的程序时，我们将得到以下输出
The DFS traversal of the graph using stack 40 20 50 70 60 30 10 The DFS traversal of the graph using recursion 40 10 30 60 70 20 50
使用邻接矩阵
Addacency_Matrix用于在两个节点之间找到连接。
如果Addacency_matrix [i] [j] == 1，则连接索引i和索引j处的节点
下图将有助于我们了解邻接矩阵。
创建DepthFirstSearch示例 .java.
package org.arpit.theitroad.graph;
import java.util.ArrayList;
import java.util.Stack;
public class DepthFirstSearch示例
{
static ArrayList<Node> nodes=new ArrayList<>();
static class Node
{
int data;
boolean visited;
Node(int data)
{
this.data=data;
}
}
//find neighbors of node using adjacency matrix
//if adjacency_matrix[i][j]==1, then nodes at index i and index j are connected
public ArrayList<Node> findNeighbours(int adjacency_matrix[][],Node x)
{
int nodeIndex=-1;
ArrayList<Node> neighbours=new ArrayList<>();
for (int i = 0; i < nodes.size(); i++) {
if(nodes.get(i).equals(x))
{
nodeIndex=i;
break;
}
}
if(nodeIndex!=-1)
{
for (int j = 0; j < adjacency_matrix[nodeIndex].length; j++) {
if(adjacency_matrix[nodeIndex][j]==1)
{
neighbours.add(nodes.get(j));
}
}
}
return neighbours;
}
//Recursive DFS
public void dfs(int adjacency_matrix[][], Node node)
{
System.out.print(node.data + " ");
ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,node);
node.visited=true;
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null && !n.visited)
{
dfs(adjacency_matrix,n);
}
}
}
//Iterative DFS using stack
public void dfsUsingStack(int adjacency_matrix[][], Node node)
{
Stack<Node> stack=new Stack<>();
stack.add(node);
while (!stack.isEmpty())
{
Node element=stack.pop();
if(!element.visited)
{
System.out.print(element.data + " ");
element.visited=true;
}
ArrayList<Node> neighbours=findNeighbours(adjacency_matrix,element);
for (int i = 0; i < neighbours.size(); i++) {
Node n=neighbours.get(i);
if(n!=null &&!n.visited)
{
stack.add(n);
}
}
}
}
public static void main(String arg[])
{
Node node40 =new Node(40);
Node node10 =new Node(10);
Node node20 =new Node(20);
Node node30 =new Node(30);
Node node60 =new Node(60);
Node node50 =new Node(50);
Node node70 =new Node(70);
nodes.add(node40);
nodes.add(node10);
nodes.add(node20);
nodes.add(node30);
nodes.add(node60);
nodes.add(node50);
nodes.add(node70);
int adjacency_matrix[][] = {
{0,1,1,0,0,0,0}, //Node 1: 40
{0,0,0,1,0,0,0}, //Node 2 :10
{0,1,0,1,1,1,0}, //Node 3: 20
{0,0,0,0,1,0,0}, //Node 4: 30
{0,0,0,0,0,0,1}, //Node 5: 60
{0,0,0,0,0,0,1}, //Node 6: 50
{0,0,0,0,0,0,0}, //Node 7: 70
};
DepthFirstSearch示例 dfs示例 = new DepthFirstSearch示例 ();
System.out.println("The DFS traversal of the graph using stack ");
dfs示例 .dfsUsingStack(adjacency_matrix, node40);
System.out.println();
clearVisitedFlags();
System.out.println("The DFS traversal of the graph using recursion ");
dfs示例 .dfs(adjacency_matrix, node40);
}
public static void clearVisitedFlags()
{
for (int i = 0; i < nodes.size(); i++) {
nodes.get(i).visited=false;
}
}
}
运行上面的程序时，我们将得到以下输出
The DFS traversal of the graph using stack 40 20 50 70 60 30 10 The DFS traversal of the graph using recursion 40 10 30 60 70 20 50
