dfs
一、DFS定义
深度优先搜索算法（Depth-First-Search，简称DFS）是一种常用于遍历或搜索树或图的算法。从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，尽可能深的搜索树的分支。当节点所在边都己被探寻过，搜索将回溯到发现节点的那条边的起始节点。重复这一过程一直进行到已发现从源节点可达的所有节点为止。
二、DFS过程
深度优先搜索是一个递归的过程。算法的具体实现过程就可以表述如下：
1.访问初始节点v，并标记节点v为已访问；
2.查找节点v的第一个邻接节点w；
3.若w存在，则继续执行4步骤，否则结束算法；
4.若w未被访问，对w进行深度优先搜索递归（将w看做新的初始节点，重复1，2，3）；
5.查找节点v的w邻接节点的下一个邻接节点，转到步骤3。
图1 深度优先搜索示意图
如图1所示，节点1作为初始节点，从该节点开始，并将其标记为已访问，查找节点1的第一个邻节点，为节点2，节点2未被访问过，然后将2看做初始节点，查找节点2的第一个邻接节点，为节点4，节点4未被访问过，将节点4看做初始节点，查找节点4的第一个临接节点，为节点8，节点8未被访问过，将节点8看做初始节点，查找节点8的第一个邻接节点，不存在，所以回溯到节点4，节点4除了节点8之外没有其他临接节点，回溯到节点2，节点2除了节点4这个邻接节点之外，还有一个邻接节点5，节点5未被访问过，将节点5看做初始节点，节点5的临接节点不存在，回溯到2，节点2没有其他临接节点，回溯到节点1，以此继续进行下去，直到遍历完全部的节点。
所以，深度优先遍历顺序为：1->2->4->8->5->3->6->7
三、DFS算法实现
在解决深度优先搜索的问题上，常用递归法和栈这两种方法来实现。
方法一：递归法
/**
* 深度优先搜索（递归法）
*
* */
public class DFSTest {
//存储节点信息
private char[] nodes;
//存储边信息（如果节点连接，为1，否则为0）
private int[][] edges;
//节点个数
private int nodesNum;
//边是否被遍历过
private boolean[] visited;
/**
* 初始化
* 1. 节点个数
* 2. 节点连接信息
* 3. 节点是否被遍历过
*
* */
public DFSTest(int num) {
nodesNum = num;
nodes = new char[num];
edges = new int[num][num];
visited = new boolean[num];
for (int i = 0; i < nodesNum; i++) {
for (int j = 0; j < nodesNum; j++) {
edges[i][j] = 0;
}
}
}
/**
* 添加边信息（节点连接则设置为1，否则为0）
*
* @param num1 通过边连接的节点1
* @param num2 通过边连接的节点2
*
* */
public void addEdge(int num1, int num2) {
if (num1 == num2) {
return;
} else {
edges[num1][num2] = 1;
edges[num2][num1] = 1;
}
}
/**
* 设置节点集
* @param nodes 节点
*
* */
public void setNodes(char[] nodes) {
this.nodes = nodes;
}
/**
* 设置节点访问标记
* @param visited 访问标记
*
* */
public void setVisited(boolean[] visited) {
this.visited = visited;
}
/**
* 打印遍历节点
* @param num 节点
*
* */
public void visit(int i) {
System.out.print(nodes[i] + " ");
}
/**
* 从第i个节点开始深度优先遍历
*
* @param i 第i个节点
*
* */
private void travel(int i) {
visited[i] = true;
visit(i);
for (int j = 0; j < nodesNum; j++) {
if (1 == edges[i][j] && false == visited[j]) {
travel(j);
}
}
}
//图的深度优先遍历（递归法）
public void DFSTravel() {
//初始化节点遍历标记
for (int i = 0; i < nodesNum; i++) {
visited[i] = false;
}
//从没有遍历过的节点开始遍历
for (int i = 0; i < nodesNum; i++) {
if (visited[i] == false) {
travel(i);
}
}
}
public static void main(String[] args) {
DFSTest dfsTest = new DFSTest(8);
char[] nodes = {'1', '2', '3', '4', '5', '6', '7', '8'};
dfsTest.setNodes(nodes);
dfsTest.addEdge(0, 1);
dfsTest.addEdge(0, 2);
dfsTest.addEdge(1, 0);
dfsTest.addEdge(1, 3);
dfsTest.addEdge(1, 4);
dfsTest.addEdge(2, 0);
dfsTest.addEdge(2, 5);
dfsTest.addEdge(2, 6);
dfsTest.addEdge(3, 1);
dfsTest.addEdge(3, 7);
dfsTest.addEdge(4, 1);
dfsTest.addEdge(4, 7);
dfsTest.addEdge(5, 2);
dfsTest.addEdge(5, 6);
dfsTest.addEdge(6, 2);
dfsTest.addEdge(6, 5);
dfsTest.addEdge(7, 3);
dfsTest.addEdge(7, 4);
dfsTest.DFSTravel();
}
}