当涉及到从Java中给定的数据结构访问数据时，搜索和/或者遍历同样重要。图和树是可以使用不同方法搜索和/或者遍历的数据结构示例。

深度优先搜索，简称DFS，从一个未访问的节点开始，然后开始选择一个相邻的节点，直到没有剩余的节点为止。在这个“过程”之后，我们将回溯到有另一个选择来选择一个节点，如果没有，那么只需选择另一个未访问的节点。

使用堆栈实现

上图访问节点的顺序是：5 10 25 30 35 40 15 20

使用堆栈数据结构实现DFS

节点.java表示上图中的每个“球”或者“圆”。它有一个表示每个球的“值”的 val，还有一个名为 visited的布尔变量，顾名思义，它表示遍历是否访问过一个节点。Node类的第三个实例变量是一个ArrayList，它表示当前节点的所有邻接(或者邻居)，称为adjacents。(如果我们想了解更多关于ArrayList的信息，可以查看本教程。)

就这个类中的方法而言，有一个简单的构造函数，它接受一个值并创建一个空的ArrayList、Setter和Getter方法以及一个允许添加相邻节点的方法。

节点.java

import java.util.*;

public class Node{
  private int val;
  private boolean visited;
  private List<Node> adjecents;

  public Node(int val) {
      this.val = val;
      this.adjecents = new ArrayList<>();
  }

  public void addAdjecents(Node n) {
      this.adjecents.add(n);
  }

  public List<Node> getAdjacenets() {
      return adjecents;
  }

  public int getVal() {
      return this.val;
  }

  public boolean isVisited() {
      return this.visited;
  }

  public void setVal(int v) {
      this.val = v;
  }

  public void setVisited(boolean visited) {
      this.visited = visited;
  }
}

DFS.java

这个类只有一个方法：解决方案。

它使用堆栈数据结构，以节点为元素。它将指定的元素添加到节点，然后将其标记为已访问。之后，会有一个while循环来检查堆栈是否为空。如果不是，则从堆栈中移除一个元素，获取要移除的元素的邻居。然后，还有另一个循环，其目的是将每个邻居节点标记为已访问，并将该邻居节点添加到堆栈中。

import java.util.*;

public class DFS {
  public void stackSolution(Node node) {
		Stack<Node> DFS_stack = new Stack<Node>();
		DFS_stack.add(node);
		node.setVisited(true);
		while (!DFS_stack.isEmpty()) {
			Node nodeRemove = DFS_stack.pop();
			System.out.print(nodeRemove.getVal() + " ");

			List<Node> adjs = nodeRemove.getAdjacenets();
			for (int i = 0; i < adjs.size(); i++) {
				Node currentNode = adjs.get(i);
				if(currentNode != null && !currentNode.isVisited()) {
					DFS_stack.add(currentNode);
					currentNode.setVisited(true);
				}
			}
		}
	}
}

主类

这个类中的main方法创建了节点类的8个实例并传递了一些值。(请记住，下面的示例使用上面的图形(图像)。我们正在添加不同的节点作为不同节点的邻居。之后，我们从node5开始遍历它。

import java.util.*;

public class Main {
  public static void main(String [] args) {
      Node node5 = new Node(5);
      Node node10 = new Node(10);
      Node node15 = new Node(15);
      Node node20 = new Node(20);
      Node node25 = new Node(25);
      Node node30 = new Node(30);
      Node node35 = new Node(35);
      Node node40 = new Node(40);

      node5.addAdjecents(node10);
      node10.addAdjecents(node15);
      node15.addAdjecents(node20);
      node10.addAdjecents(node25);
      node25.addAdjecents(node35);
      node35.addAdjecents(node40);
      node25.addAdjecents(node30);

      DFS demo = new DFS();

      System.out.println("DFS traversal of above graph: ");
      demo.stackSolution(node5);
  }
}

输出

DFS traversal of above graph:
5 10 25 30 35 40 15 20