深度优先遍历，也称为深度优先搜索。简称DFS
它从图中的某个顶点V出发，访问该顶点，然后从v的未被访问的邻接点（出度的点）出发，深度优先遍历图，直至图中所有和v有路径的想通的顶点都被访问到
-
算法准备
a. 记录是否遍历过的数组
b. 取得某顶点的第一个邻接点下标方法
c. 取得某顶点从某邻接点后的第一个邻接点下标方法
-
算法思路（递归）
a. 从某顶点开始
b. 取出第一个邻接点下标
c. while循环，循环条件为邻接点权值不为-1
d. 如果该邻接点没输出过则输出，并记录
e. 递归该邻接点
f. 邻接点递归结束后
g. 取出该顶点从该邻接点后的第一个邻接点继续循环
public class Graph> {
// 顶点数组
private T[] vertexs;
// 邻接表元素数组
private VertexNeighborNode[] neighborArray;
// 邻接矩阵
private int[][] matrix;
// 度数组
private Edge[] edges;
// 泛型对象的类文件
private Class Class;
// 顶点数量
private int size;
// 常亮：未连接
public static final int NO_LINK = -1;
/**
* 构造方法
* @param Class 类对象
* @param vertexs 顶点可选数组
*/
public Graph(Class Class, T... vertexs) {
super();
this.vertexs = vertexs;
this.size = vertexs.length;
this.Class = Class;
}
/**
* 构造方法
* @param vertexs 可选数组
*/
public Graph(T... vertexs) {
super();
this.vertexs = vertexs;
this.size = vertexs.length;
}
/**
* 深度优先遍历方法（递归）
*/
public void depthFirst() {
// 建立记录数组
boolean[] isVisited = new boolean[size];
// 顶点数组循环
for (int i = 0; i < vertexs.length; i++) {
// 全部遍历标记，为节省资源
boolean isAllTrue = true;
// 遍历记录数组是否已全部记录
for (int j = 0; j < isVisited.length; j++) {
// 如果有一个没记录
if (isVisited[j] == false) {
// 则将全部遍历标记设置为false
isAllTrue = false;
// 跳出该循环
break;
}
}
// 如果已全部遍历
if (isAllTrue) {
// 跳出循环，不再继续
break;
}
// 判断当前顶点是否已遍历，如果没有则进行遍历
if (!isVisited[i]) {
// 遍历该顶点
depthFirst(isVisited, i);
}
}
}
/**
* 深度优先遍历实现方法（递归）
* @param isVisited 遍历记录数组
* @param i 遍历的起点
*/
private void depthFirst(boolean[] isVisited, int i) {
// 将当前顶点设置为已遍历
isVisited[i] = true;
// 找到该顶点的第一个出度顶点下标
int weight = getFirstNeighbor(i);
// 深度遍历出度顶点，直到没有出度顶点
while (weight != -1) {
// 判断出度顶点是否已遍历过，如果没遍历过则进行遍历
if (!isVisited[weight]) {
// 输出该出度顶点的信息
System.out.println("第" + weight + "个顶点被访问：" + vertexs[weight]);
// 深度遍历该出度顶点
depthFirst(isVisited, weight);
}
// 如果没有出度顶点，则查找该顶点下一个出度顶点
weight = getNextNeighbor(i, weight);
}
}
/**
* 得到该顶点的第一个出度顶点下标
* @param i 顶点数组下标
* @return 第一个出度顶点下标
*/
private int getFirstNeighbor(int i) {
// 循环矩阵中顶点的出度数组
for (int j = 0; j < size; j++) {
// 如果该出度不为0，并且相连
if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK) {
// 返回出度顶点下标
return j;
}
}
// 返回未连接
return NO_LINK;
}
/**
* 得到该顶点从某位置后的第一个出度顶点下标
* @param i 顶点数组下标
* @param weight 位置
* @return 出度顶点下标
*/
private int getNextNeighbor(int i, int weight) {
// 从某位置开始循环矩阵中顶点的出度数组
for (int j = weight + 1; j < size; j++) {
// 如果该出度不为0，并且相连
if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK) {
// 返回出度顶点下标
return j;
}
}
// 返回未连接
return NO_LINK;
}
}
更新
