目录
图的遍历
给定一个图G和其中任意一个顶点v0，从v0出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。"遍历"即对结点进行某种操作的意思。
在二叉树中，我们对树的最多的操作就是各种遍历，而二叉树的前、中、后序遍历都是深度优先遍历，层序遍历就是广度优先遍历。
而二叉树可以被视为一种特殊类型的图。具体来说，二叉树是一种特殊的有向无环图（Directed Acyclic Graph，DAG）。
在一棵二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。这种结构符合图的定义，其中节点之间通过边（或连接）相互关联。
注意：两个遍历均基于【图（1）】上篇博客的邻接矩阵实现。
一、图的广度优先遍历（bfs）
类似于树，我们从起始顶点开始，同样一层一层遍历：
还是用这个简单图举例：
假设以B顶点开始广度优先遍历：
结合邻接矩阵我们可以清晰得出结论：每遍历一层顶点后，下一层需要遍历的顶点为该层顶点能指向的所有顶点。
下面模拟一下过程（与树的层序遍历相同，需要一个队列）：
- 从B开始，遍历矩阵B对应的这一行，权值不为0的即B指向的顶点（A，C），将它们入队。
- A，C入队，对A，C进行相同的操作（poll）。而遍历A这一行发现A又指向了B，但B已经访问过，不能再次访问，因此在遍历前我们需要一个数组来记录每个顶点是否被访问过。再看A指向D，将D入队。
- poll出C，遍历C这一行，发现B，D都已经访问过，不需要操作。
- poll出D，同上。得到结果：B->A->C->D
综上，只要对二叉树的各种遍历非常熟悉（这里主要是层序遍历），然后刷过一些层序遍历、递归回溯的算法，图的广度优先遍历就非常简单了。
/**
* 图的广度优先遍历
*
* @param v 开始遍历的顶点
*/
public void bfs(char v) {
//1.定义一个数组标记当前顶点是否已经访问过
boolean[] visited = new boolean[arrayV.length];
//2.申请队列进行bfs
Queue<Integer> queue = new ArrayDeque<>();
int index = getIndexOfV(v); //记录当前顶点下标，也对应要遍历的行数
queue.offer(index);
visited[index] = true; //v位置设置为true
while (!queue.isEmpty()) {
index = queue.poll();
System.out.print(arrayV[index] + " ");
//遍历矩阵的第index行
for (int i = 0; i < arrayV.length; i++) {
//当前有连通节点且visited为false才能入队
if (matrix[index][i] != 0 && !visited[i]) {
queue.offer(i);
visited[i] = true;
}
}
}
}测试（基于上篇博客的邻接矩阵类）：
public static void main(String[] args) {
GraphByMatrix graphByMatrix = new GraphByMatrix(4, false);
char[] array = {'A', 'B', 'C', 'D'};
graphByMatrix.initArrayV(array);
graphByMatrix.addEdge('A', 'B', 1);
graphByMatrix.addEdge('A', 'D', 1);
graphByMatrix.addEdge('B', 'A', 1);
graphByMatrix.addEdge('B', 'C', 1);
graphByMatrix.addEdge('C', 'B', 1);
graphByMatrix.addEdge('C', 'D', 1);
graphByMatrix.addEdge('D', 'A', 1);
graphByMatrix.addEdge('D', 'C', 1);
//graphByMatrix.printGraph();
System.out.println("顶点A的度：" + graphByMatrix.getDevOfV('A'));
System.out.print("bfs: ");
graphByMatrix.bfs('B');
System.out.println();
System.out.print("dfs: ");
graphByMatrix.dfs('B');
} 
二、图的深度优先遍历（dfs）
图例：
还是来看前面那个简单的图：
总结：每次访问该顶点指向的第一个顶点，直到最后一个顶点指向的所有顶点都被访问过，开始回溯。
下面还是模拟一下过程：
- 从顶点B开始，遍历B这一行，发现B指向A，递归到A这一层再访问。
- 同样遍历A这一行，发现A又指向B了，那我们肯定不能进入这一层（回溯算法中的剪枝操作）。因此再遍历的同时同样需要一个标记数组来记录顶点是否被访问过。再继续遍历A，发现A指向D，D没被访问过，再递归进入D这一层。
- 遍历D这一行，D指向A，剪枝；继续遍历，D指向C，C没被访问过，再递归进入C这一层。
- 遍历C，发现C所有指向的顶点都已经被访问过。遍历结束后开始回溯。
- 回溯过程中，发现所有顶点都已经访问过，即都会被剪掉，因此再不会进入任何的递归操作。直到回到最开始的B这一层，循环结束，遍历完成。顺序：B->A->D->C。
/**
* 图的深度优先遍历
*
* @param v 起始顶点
*/
public void dfs(char v) {
visited = new boolean[arrayV.length];
int index = getIndexOfV(v);
dfsChild(index);
}
boolean[] visited; //记录当前顶点是否被访问过
private void dfsChild(int index) {
System.out.print(arrayV[index] + " ");
visited[index] = true;
//看矩阵中index这行, 是否还有未访问过的顶点
for (int i = 0; i < arrayV.length; i++) {
if (matrix[index][i] != 0 && !visited[i]) {
dfsChild(i);
}
}
}测试（基于上篇博客的邻接矩阵类）：
public static void main(String[] args) {
GraphByMatrix graphByMatrix = new GraphByMatrix(4, false);
char[] array = {'A', 'B', 'C', 'D'};
graphByMatrix.initArrayV(array);
graphByMatrix.addEdge('A', 'B', 1);
graphByMatrix.addEdge('A', 'D', 1);
graphByMatrix.addEdge('B', 'A', 1);
graphByMatrix.addEdge('B', 'C', 1);
graphByMatrix.addEdge('C', 'B', 1);
graphByMatrix.addEdge('C', 'D', 1);
graphByMatrix.addEdge('D', 'A', 1);
graphByMatrix.addEdge('D', 'C', 1);
//graphByMatrix.printGraph();
System.out.println("顶点A的度：" + graphByMatrix.getDevOfV('A'));
System.out.print("bfs: ");
graphByMatrix.bfs('B');
System.out.println();
System.out.print("dfs: ");
graphByMatrix.dfs('B');
}
