一、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();
}
}