14.2.1 深度优先遍历(Depth First Search)
- 深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，反问他的第一个邻接节点，可以这样理解： 每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
- 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问
- 显然深度有限搜索时一个递归的过程
深度优先遍历算法步骤
- 访问初始节点V，并标记节点V已访问
- 查找节点V的第一个邻接节点W
- 若W存在，则继续执行 4，如果W不存在，则返回第一步，将从V的下一个节点继续
- 若W未被访问，对W进行深度优先遍历递归（即把W当做另一个V，然后进行步骤123)
- 查找节点V的W邻接节点的下一个了邻接节点，转到步骤 3
拿上图当个例子，我们是按照A，B，C，D，E这个顺序来创建的数组，所以，我们需要按照这个顺序来进行遍历。
首先看A，他的下一个节点是B，我们发现存在B节点，且未被访问过以及与A存在直接连接关系，因此我们往下走，到B。
我们继续按照顺序来，B节点的下一个是C，我们发现C存在，它没有被访问过，且C与B存在直接连接关系，因此，我们往下走，来到C
我们来到C节点，继续按照顺序来，下一个是D，我们发现C与D节点没有直接连接，因此无法从C到达D节点，因此我们需要返回到B，然后，看看B能不能到达D，我们发现，D存在，未被访问过，而且与B存在直接连接关系，所以我们往下走，来到D。
D接下来是E，虽然E存在且没有被访问过，但是E与D没有直接连接关系，因此我们返回上一层（从哪里来回到那里去），回到B，发现B与E存在直接连接，因此我们向下走，到达E，发现没有需要到达的节点了，完成遍历。
A - B - C (= B) - D (= B) - E // - 表示到达的意思，而 = 表示返回上一层的意思，括号里的是帮助理解的，而最终结果是（A - B - C - D -E）
package graph;
import java.util.ArrayList;
import java.util.Arrays;
public class Graph {
private ArrayList<String> vertexList; // 存储定点集合
private int[][] edges; // 存储图对应的邻接矩阵
private int numOfEdges; // 表示边的数目
// 定义一个数组 boolean[] ，记录某个节点是否被访问
private boolean[] isVisited;
public static void main(String[] args) {
int n = 5; // 节点的个数
String[] vertexs = {"A","B","C","D","E"};
// 创建图对象
Graph graph = new Graph(n);
// 循环添加顶点
for (String vertex : vertexs){
graph.insertVertex(vertex);
}
// 手动添加边
// A - B / A - C / B - C / B - D/ B - E
graph.insertEdge(0,1,1); // A - B
graph.insertEdge(0,2,1); // A - C
graph.insertEdge(1,2,1); // B - C
graph.insertEdge(1,3,1); // B - D
graph.insertEdge(1,4,1); // B - E
// 显示邻接矩阵
graph.showGraph();
// 深度优先遍历
System.out.println("Depth First Search 深度优先遍历");
graph.dfs();
}
// 构造器
private Graph(int n){// 这个n是指有多少个节点或顶点
// 初始化矩阵和vertexList
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0; // 因为我们不知道边有多少条，所以我们初始化为零
isVisited = new boolean[n];
}
// 先写一个方法，得到第一个邻接节点的下标
/**
*
* @param index
* @return 如果存在就返回对应的下标，否则返回-1
*/
public int getFirstNeighbor(int index){
for (int i = 0; i < vertexList.size(); i++) {
if (edges[index][i] > 0){ // 大于零，表示两个节点存在直接连接关系
return i;
}
}
return -1;
}
// 根据前一个邻接节点的下标来获取下一个邻接节点
// 就是当V2没有能够到达未遍历的节点的情况，执行该方法，例如 ：v1就是B节点下标，v2就是C节点下标，与c直接连接的都被访问过了，所以，我们要找C以外的节点，因此是（C）v2+1在（B）v1的周围找
public int getNextNeighbor(int v1, int v2){
for (int j = v2 + 1; j < vertexList.size(); j++){
if (edges[v1][j] > 0){
return j;
}
}
return -1;
}
// 深度优先遍历算法
/**
*
* @param isVisited 用来判断是否被访问
* @param i 访问节点下标，第一次就是0
*/
public void dfs(boolean[] isVisited, int i){
// 首先我们访问该节点。输出
System.out.println(getValueByIndex(i) + "->");
// 将这个节点设置为已经访问
isVisited[i] = true;
// 查找节点i的第一个邻接节点
int w = getFirstNeighbor(i);
while(w != -1){ // 说明存在该节点
if (!isVisited[w]){ // 说明没有被访问过
dfs(isVisited, w);
}
// 如果 W这个节点被访问过了，我们就该查找下一个的下一个
// i 是当前节点，而w是当前节点的下一个节点
w = getNextNeighbor(i, w);
}
}
// dfs 进行重载，遍历我们所有的节点，并进行dfs
public void dfs(){
// 遍历所有的节点，进行dfs[回溯]
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]){
dfs(isVisited,i);
}
}
}
// 插入节点
public void insertVertex(String vertex){
vertexList.add(vertex);
}
// 添加边
/**
*
* @param v1 表示第一个点的对应的下标，即是第几个顶点
* @param v2 表示第二个点的对应的下标，即是第几个顶点
* @param weight 认为规定 1 是表示两个顶点有直接关联，0 表示没有直接关联
*/
public void insertEdge(int v1,int v2, int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight; // 因为我们这个图是无向图，所以反过来也要赋值
numOfEdges++;
}
// 图中常用的方法
// 返回节点的个数
public int getNumOfVertex(){
return vertexList.size();
}
// 得到边的个数
public int getNumOfEdges(){
return numOfEdges;
}
// 返回节点i（下标）对应的数据
public String getValueByIndex(int i){
return vertexList.get(i);
}
// 返回v1和v2的权值
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
// 显示图对应的矩阵
public void showGraph(){
for (int[] link : edges){
System.out.println(Arrays.toString(link));
}
}
}