Java实现深度优先搜索

图的遍历

图的遍历就是访问图中的每个节点并且每个节点只访问一次。但图中有那么多节点，要如何进行访问就是一个问题，所以我们需要有特定的策略来进行访问这些节点。图的访问策略一般有两种：深度优先搜索和广度优先搜索

深度优先搜索基本思想

从初始节点开始出发访问，访问该节点的第一个相邻节点，然后以该相邻节点为起点，继续访问其相邻节点，反复持续该过程直到图中所有节点已全部被访问；简单总结就是：访问完当前节点后就去访问当前节点的第一个相邻节点。这样一来，图的访问顺序就是向深处访问，而不是横向访问。

我们将要访问的节点称为头节点，相邻节点称为表节点；头节点中存储数据和第一个表节点，表节点中存储头节点的下标和头节点的下一个相邻节点；头节点使用顺序（链表）存储，表节点使用链表存储；

如下图，其深度优先搜索顺序可以是 v1, v2, v4, v8, v5, v3, v6, v7，注意：深度优先搜索的顺序不是唯一的，这取决于访问起点和表节点的顺序。

实现思路

访问头节点，并将该头节点标记为以访问过
访问表节点中第一个没有被访问过的头节点，这里需要循环
以该头节点为起点，继续上面两步操作直到访问完所有节点，这里需要递归

代码实现

定义头节点和表节点

//头节点
public class HNode<T> {public T data; //数据域public boolean isVisit; //标识该头节点是否已经被访问过public TNode firstArc; //指针域，指向第一个表节点public HNode(T data) {this.data = data;}public HNode() {}@Overridepublic String toString() {return "HNode{" +"data=" + data +", isVisit=" + isVisit +", firstArc=" + firstArc +'}';}
}//表节点
class TNode {public int hNodeIndex;//存储头节点下标public TNode nextArc; //指针域，指向下一个相邻的表节点public TNode(int hNodeIndex) {this.hNodeIndex = hNodeIndex;}}

定义一个 Graph 类，一个Graph类就表示一个图

class Graph {private HNode[] vertices; //存储头节点public Graph(HNode[] vertices) {this.vertices = vertices;}//构建图public void build(Object data) {}//图的深度优先搜索//index表示从顺序表中的第几个节点开始遍历public void dfs(int index) {//访问index对应的头节点System.out.println(vertices[index].data);//设置当前节点为已访问vertices[index].isVisit = true;//临时变量，用于辅助遍历表节点TNode temp = vertices[index].firstArc;//通过表节点访问未被访问过的头节点while (temp != null) {if (vertices[temp.hNodeIndex].isVisit) {//当前节点已经被访问过，无需再访问，继续往后寻找temp = temp.nextArc; //后移} else {//当前表节点对应的头节点没有被访问过，以该头节点为起点，继续执行上面代码的逻辑：访问-寻找为访问的表节点-访问-寻找完毕，退出dfs(temp.hNodeIndex);}}}}

在main方法中测试

public class DFSDemo {public static void main(String[] args) {HNode[] nodes = new HNode[5];for (int i = 0; i < nodes.length; i++) {HNode<String> node = new HNode<>("张三-" + (i + 1));nodes[i] = node;}TNode node1 = new TNode(2);node1.nextArc = new TNode(3);nodes[0].firstArc = node1;TNode node2 = new TNode(0);node2.nextArc = new TNode(4);nodes[1].firstArc = node2;TNode node3 = new TNode(1);node3.nextArc = new TNode(3);nodes[2].firstArc = node3;TNode node4 = new TNode(0);node4.nextArc = new TNode(1);nodes[3].firstArc = node4;TNode node5 = new TNode(3);node5.nextArc = new TNode(2);nodes[4].firstArc = node5;for (HNode node : nodes) {System.out.println(node);}Graph graph = new Graph(nodes);System.out.println("--------------深度优先搜索--------------");graph.dfs(0);}
}