图的遍历 --- 深度优先遍历
在讲深度优先遍历之前，先来回顾一下图这种数据结构。
1. 是什么？
图，也是一种数据结构，其节点可以具有零个或者多个相邻元素，两个节点之间的连接称为边，节点也称为顶点，图表示的是多对多的关系。
无向图
2. 图的常用概念：
-
顶点：就是节点，上图中的ABCDEFGH都是顶点；
-
边：每个节点之间的连线叫做边；
-
路径：从一个顶点到另一个顶点的通路，比如从A到G的路径有：
A ---> B ---> G和A ---> F ---> G； -
无向图：上面的就是无向图，就是节点之间的连线是没有方向的，A可以到B，B也可以到A；
-
有向图：节点之间的连线是有方向的；
-
带权图：边具有权值的图叫做带权图，也叫网。
3. 图的表示方式：
-
邻接矩阵：也就是用二维数组表示。假如总共有n个顶点，那么就需要一个 n*n 的二维数组。两个顶点之间如果是连通的就用1表示，反之用0表示。这种方式的缺点就是，假如n很大，但是相互连通的顶点却很少，即一个二维数组中真正有用的数据特别少，那么就会造成空间的浪费；
-
邻接表：邻接表只关心存在的边，即只关注能相互连通的顶点，因此没有空间浪费。邻接表用数组和链表组合实现。数组下标表示顶点编号，数组中存的值是一条链表，链表中的数据就是数组该下标对应顶点连通的顶点编号。比如顶点0可以和顶点2，3，6连通，那么数组第一个位置存放的就是
2 ---> 3 ---> 6这条链表。
4. 无向图的创建(邻接矩阵)：
开篇所示的无向图，怎么用邻接矩阵代码实现呢？思路如下：
-
创建一个
List<String>，用来保存各个顶点； -
创建一个二维数组，用来保存顶点之间的边，顶点与顶点之间有连线的用1表示，反之用0。所以这个二位数组就是：
A B C D E F G H
A[0, 1, 0, 0, 0, 1, 0, 1]
B[1, 0, 1, 0, 0, 0, 1, 0]
C[0, 1, 0, 1, 1, 0, 0, 0]
D[0, 0, 1, 0, 0, 0, 0, 1]
E[0, 0, 1, 0, 0, 0, 1, 0]
F[1, 0, 0, 0, 0, 0, 1, 0]
G[0, 1, 0, 0, 1, 1, 0, 0]
H[1, 0, 0, 1, 0, 0, 0, 0]
- 所以，创建图也就是创建这个邻接矩阵，代码如下：
public class UnDirectionGraph {
private List<String> vertexList; // 存放顶点
private int[][] edges; // 邻接矩阵，存放图的边
private boolean[] isVisited; // 顶点是否被访问
/**
* 构造器
* @param vertexCount 顶点的个数
*/
public UnDirectionGraph(int vertexCount, List<String> vertex){
this.vertexList = vertex;
this.edges = new int[vertexCount][vertexCount];
this.isVisited = new boolean[vertexCount];
}
/**
* 构建无向图
* @param vertex1 顶点1
* @param vertex2 顶点2
* @param isConnected 顶点1和顶点2是否连通，0:未连通 1:已连通
*/
public void buildGraph(String vertex1, String vertex2, int isConnected){
edges[vertexList.indexOf(vertex1)][vertexList.indexOf(vertex2)] = isConnected;
edges[vertexList.indexOf(vertex2)][vertexList.indexOf(vertex1)] = isConnected;
}
/**
* 打印邻接矩阵
*/
public void printGraph(){
for(int[] arr : edges){
System.out.println(Arrays.toString(arr));
}
}
}
测试代码：
public static void main(String[] args) {
int vertexCount = 8;
List<String> vertexList = new ArrayList<>();
vertexList.add("A");
vertexList.add("B");
vertexList.add("C");
vertexList.add("D");
vertexList.add("E");
vertexList.add("F");
vertexList.add("G");
vertexList.add("H");
UnDirectionGraph graph = new UnDirectionGraph(vertexCount, vertexList);
graph.buildGraph("A", "B", 1);
graph.buildGraph("A", "H", 1);
graph.buildGraph("A", "F", 1);
graph.buildGraph("B", "G", 1);
graph.buildGraph("B", "C", 1);
graph.buildGraph("C", "D", 1);
graph.buildGraph("C", "E", 1);
graph.buildGraph("D", "H", 1);
graph.buildGraph("E", "G", 1);
graph.buildGraph("F", "G", 1);
graph.printGraph();
}
5. 无向图的遍历：
(1). 遍历分类：
图的遍历分为两种：
-
深度优先：depth first search，简称DFS。先从初始顶点出发，访问第一个邻接顶点，然后再以这个被访问到的邻接顶点作为初始顶点，访问它的第一个邻接顶点。可以理解为一条路走到底，而不是把一个顶点的所有邻接顶点先进行横向访问，而是纵向优先，所以也叫深度优先。
-
广度优先：broad first search，简称BFS。类似于二叉树的层序遍历，具体的本文不做介绍。
(2). 深度优先算法步骤：
以开篇中的图为例：
-
访问A，并将A标记为已访问；
-
找到A的第一个未被访问邻接顶点，怎么找？看矩阵：
A B C D E F G H
A[0, 1, 0, 0, 0, 1, 0, 1]
第一个1对应的是B，所以A的第一个邻接顶点是B，所以第二个遍历出来的是B，并且标记B为已访问；
- 找到B的第一个未被访问的邻接顶点，方式一样，看矩阵：
A B C D E F G H
B[1, 0, 1, 0, 0, 0, 1, 0]
找到的是C，所以第三个遍历出来的是C，并且标记C为已访问；
-
找到C的第一个未被访问的邻接顶点，是D，打印D，并标记为已访问；
-
找到D的第一个未被访问的邻接顶点，是H，打印H，并标记为已访问；
-
找到H的第一个未被访问的邻接顶点，发现没有，也就是这条路走到底了，那么开始往回走；
-
回到D，没有未被访问的，再往回，直到回到C；
-
回到C，找到C的第一个邻接顶点D的后一个邻接顶点：
A B C D E F G H
C[0, 1, 0, 1, 1, 0, 0, 0]
说白了就是这一行的D后面的那个1，就是E，打印E，并标记为已访问；
-
找到E的第一个未被访问的邻接顶点G，打印G；
-
找到G的第一个未被访问的邻接顶点F，打印F；
-
到了F，发现F的所有邻接顶点都被访问过了，往回走，发现所有顶点的邻接顶点都被访问过了，就遍历完了，所以遍历的结果就是：
A --- B --- C --- D --- H --- E --- G --- F
其实概括地说就是：从第一个顶点开始，每次都选择该顶点的第一个邻接顶点往下走，走到死胡同的时候，就往回走，回到最后一次有岔路的地方，换另一条岔路走，又走到死胡同继续往回走……
(3). 深度优先遍历代码：
首先得在UnDirectionGraph类中加一个变量，用来表示该顶点有没有被访问过，如下：
private boolean[] isVisited; // 顶点是否被访问
然后在UnDirectionGraph中再增加如下方法：
/**
* 查找顶点vertex的第一个邻接顶点
* @param vertex
*/
public int findFstNeighbor(String vertex){
// 拿到vertex的索引
int vertexIndex = vertexList.indexOf(vertex);
// 遍历二维数组的第 vertexIndex 行
int[] arr = edges[vertexIndex];
for (int i = 0; i < arr.length; i++) {
// 如果arr[i] = 1，说明i对应的顶点就是vertex的邻接顶点
if (arr[i] == 1){
return i;
}
}
return -1;
}
/**
* 根据vertex的前一个邻接顶点priorVertexIndex，找到下一个邻接顶点
* @param vertex
* @param priorVertexIndex
* @return
*/
public int findNeighborByPriorNeighbor(String vertex, int priorVertexIndex){
// 拿到vertex的索引
int vertexIndex = vertexList.indexOf(vertex);
// 从(priorVertexIndex + 1)开始遍历二维数组的第 vertexIndex 行
int[] arr = edges[vertexIndex];
for (int i = priorVertexIndex + 1; i < arr.length; i++) {
if (arr[i] == 1){
return i;
}
}
return -1;
}
/**
* 深度优先遍历
* @param vertex
*/
private void dfs(String vertex, boolean[] isVisited){
// 打印当前顶点
System.out.print(vertex + " --- ");
// 标记当前顶点已经访问
isVisited[vertexList.indexOf(vertex)] = true;
// 找到当前顶点第一个邻接顶点
int neighbor = findFstNeighbor(vertex);
// 不等于-1，就打印，并且把第一个邻接顶点当成当前顶点，再去找它的第一个邻接顶点
while (neighbor != -1){
// 如果neighbor没有被访问过
if (!isVisited[neighbor]){
dfs(vertexList.get(neighbor), isVisited);
} else {
// 如果neighbor被访问过了，就找下一个邻接顶点
neighbor = findNeighborByPriorNeighbor(vertex, neighbor);
}
}
// 跳出循环，说明一条路走到底了，就应该开始回溯，怎么回溯？
// 其实外面再写个方法，循环vertexList，让每个未被访问过的顶点都调用这个方法就好了
}
public void dfs() {
for (String str : vertexList){
if (!isVisited[vertexList.indexOf(str)]){
dfs(str, isVisited);
}
}
}
深度优先遍历的方法都写了详细注释，这里不再赘述。说一说找某个顶点的第一个邻接顶点(findFstNeighbor)和找某个顶点指定邻接顶点后面的那个邻接顶点(findNeighborByPriorNeighbor)这两个方法。
- findFstNeighbor：我们构建好了二维数组，即邻接矩阵，所以找某个顶点的邻接顶点直接在矩阵中找就可以。比如我要找
A的第一个邻接顶点，那就遍历A所在的那一行，找到第一个1出现位置的索引，该索引对应的就是A的第一个邻接顶点。如下：
A B C D E F G H
A[0, 1, 0, 0, 0, 1, 0, 1]
A对应的就是这一行，第一个1出现的位置的索引是1，1在vertexList中对应的是B，所以A的第一个邻接顶点就是B。
- findNeighborByPriorNeighbor：这个方法是什么意思呢？比如我传入的参数是
A，1，意思就是我要找A的邻接顶点，找什么要的邻接顶点？就是在
A B C D E F G H
A[0, 1, 0, 0, 0, 1, 0, 1]
这一行中，找到位置1后面的那个邻接顶点，即找到位置1后面的1第一次出现的位置的索引，显然对应的索引是5，在vertexList中对应的是F。
