本文介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种：深度优先搜索和广度优先搜索。
广度优先搜索（简称“广搜”或BFS）
广度优先搜索是一种对图进行搜索的算法。如果不太了解图，可以看看图这篇文章假设我们一开始位于某个顶点(即起点),此 时并不知道图的整体结构,而我们的目的是从起点开始顺着边搜索,直到到达指定顶点(即终点)。在此过程中每走到一个顶点,就会判断一次它是否为终点。广度优先搜索会优先从离起点 近的顶点开始搜索。
广度优先搜索实现原理
准备工作：顶点类：顶点名称、布尔类型的访问记录 wasVisited，记录是否有边界，会用到队列的知识，如果还不太懂，可以看一看，然后进行初始化。
举例：假如我们的电脑有C盘、D盘、E盘，现在要去找一张图片叫 “aaa.png” ，当我们打开我的电脑的时候，其实就当于wasVisited 由为访问的false变成了true，同时将他入队。然后我们去C盘根目录中去看有没有 “aaa.png” 这张图片，如果没有就返回到我的电脑，在去D盘根目录中找，如果还是没有，就去E盘，当这3个盘中的根目录都没有 “aaa.png” 这张图片的话，就会去C盘中的更目录的文件夹中找，这样大面积的去找，直到找到。
广度优先搜索实现过程
白色表示未被访问，灰色表示即将访问，蓝色表示已访问
vertexArray数组：存储顶点的数组
adjMat数组：0 表示没有边界，1 表示有边界
队列：队头出元素，队尾进元素
我们可以看到这时候准备搜索，然后点1就被访问过了，看到下面有2,3,4就加入了队列。
然后依次的访问2,3,4，并将它的子节点加入队列。
重复此操作，11,12, 13,14,15加入队列，前面的已经被访问过了，标记为蓝色。
附上一个GIF的动图
代码实现
// 顶点类public class Vertex {public char label; // label: eg.'A'public boolean wasVisited; // 是否访问了public boolean isInTree;public Vertex(char lab) {label = lab;wasVisited = false;}}
// 队列类public class QueueX {private final int SIZE = 20;private int[] queArray;private int front; // 前端边界private int rear; // 后端边界public QueueX() {queArray = new int[SIZE];front = 0;rear = -1;}public void insert(int j) {if (rear == SIZE - 1) {// 后端边界达到队列结尾 则替代为开始的位置之前rear = -1;}queArray[++rear] = j; // 后端边界+1 放入新值}public int remove() {int temp = queArray[front++]; // 获得 要移除的当前前端 前端边界+1if (front == SIZE) {front = 0;}return temp; // 返回 要移除的当前前端}public boolean isEmpty() {return (rear + 1 == front || front + SIZE - 1 == rear);}}
public class Graph {private final int MAX_VERTS = 20;private Vertex vertexArray[]; // 存储顶点的数组private int adjMat[][]; // 存储是否有边界的矩阵数组, 0 表示没有边界，1 表示有边界private int nVerts; // 顶点个数private QueueX queue; // 广度搜索时用来临时存储的队列public Graph() {vertexArray = new Vertex[MAX_VERTS];adjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int i = 0; i < MAX_VERTS; i++) {for (int j = 0; j < MAX_VERTS; j++) {adjMat[i][j] = 0;}}queue = new QueueX();}public void addVertex(char lab) {vertexArray[nVerts++] = new Vertex(lab);}public void addEdge(int start, int end) {adjMat[start][end] = 1;adjMat[end][start] = 1;}public void displayVertex(int v) {System.out.print(vertexArray[v].label);}// returns an unvisited vertex adj to vpublic int getAdjUnvisitedVertex(int v) {for (int i = 0; i < nVerts; i++) {// v 和i 之间有边，且 i 没被访问过if (adjMat[v][i] == 1 && vertexArray[i].wasVisited == false) {return i;}}return -1;}/** 广度优先搜索算法：做四件事 1. 用 remove()方法检查栈顶的顶点 2. 试图找到这个顶点还未访问的邻节点 3. 如果没有找到，该顶点出列 4.* 如果找到这样的顶点，访问这个顶点，并把它放入队列中 深度优先算法中，好像表现的要尽快远离起始点，在广度优先算法中，要尽可能靠近起始点。* 它首先访问其实顶点的所有邻节点，然后再访问较远的区域。这种搜索不能用栈，而要用队列来实现。 广度优先算法类似于从树的跟逐层往下访问直到底层*/public void breadthFirstSearch() {vertexArray[0].wasVisited = true;displayVertex(0);queue.insert(0);int v2;while (!queue.isEmpty()) {int v1 = queue.remove();// until it has no unvisited neighborswhile ((v2 = getAdjUnvisitedVertex(v1)) != -1) {vertexArray[v2].wasVisited = true;displayVertex(v2);queue.insert(v2);}}for (int i = 0; i < nVerts; i++) {vertexArray[i].wasVisited = false;}}}
test类
public static void main(String[] args) {Graph graph = new Graph();graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addVertex('E');graph.addVertex('F');graph.addVertex('G');graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(3, 4);graph.addEdge(4, 5);graph.addEdge(4, 6);graph.addEdge(5, 6);System.out.println("广度优先搜索算法");graph.breadthFirstSearch();}
广度优先搜索的运用广度优先搜索其实就是按照树的层次进行的搜索，如果此层没有搜索完成的情况下不会进行下一层的搜索。所以他并不适合利用在比较大的问题上，而且他的时间复杂程度如果最坏情况需要走完全部过程。广度优先搜索适用范围：在未知树深度情况下，用这种算法很保险和安全。在树体系相对小不庞大的时候，广度优先也会更好些。广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离距离起点越近，搜索结束得也就越快。
补充说明：如果起点和终点是同一个顶点，那么就叫做闭环。像图中没有闭环的图叫做“树”。
深度优先搜索（简称“深搜”或DFS）
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始提索直到到达指定顶点(终点),深度优先搜索会沿着一条路径不断往下搜索直到不能再继续)止,然后再折返,开始搜索下一条候补路径。
深度优先搜索实现原理
准备工作：顶点类：顶点名称、布尔类型的访问记录 wasVisited，记录是否有边界，会用到栈的知识，如果还不太懂，可以看一看，然后进行初始化。
举例：和上个例子一样，假如我们的电脑有C盘、D盘、E盘，现在要去找一张图片叫 “aaa.png” ，当我们打开我的电脑的时候，其实就当于wasVisited 由为访问的false变成了true，同时将他入栈。然后我们去C盘根目录中去看有没有 “aaa.png” 这张图片，如果没有就去找到第一个文件夹，然后在里面一直迭代的寻找，直至出来，C盘如果没找在去找D盘、E盘。
深度优先搜索是一个不断回溯的过程。
深度优先搜索实现过程
白色表示未被访问，灰色表示即将访问，蓝色表示已访问
vertexArray数组：存储顶点的数组
adjMat数组：0 表示没有边界，1 表示有边界
栈：先进后出，只有一头进出，只要没找到就还在栈里，直到不能再找就出栈。
1先进栈，标记被访问，在找到2进栈，标记被访问，再去找5进栈，标记被访问，5发现没有子节点了，然后再回到2，于是5出栈，再去找6进栈，再找11，发现11没有子节点，再回到6，这时11出栈，再找到12，发现12也没有子节点，再回到6，这时12出栈，6也全部找完了，于是出栈，在找7，然后依次类推。
再回到1，去找3，依次类推。
附上一个GIF的动图
代码实现
这里就和上面的广度搜索和在一起了，并加上了一个生成最小树法
// 栈类public class StackX {private final int SIZE = 20;private int[] stack;private int top;public StackX() {stack = new int[SIZE];top = -1;}public void push(int j) {// 入栈stack[++top] = j;// top = top+1; // 索引+1// stack[top] = j; // 在新位置加入新值}public int pop() {// 出栈return stack[top--];// top = top-1; // 索引-1// return stack[top+1]; // 返回出栈的旧值}public int peek() {// 返回栈的边界return stack[top];}public boolean isEmpty() {return (top == -1); // 索引溢出下限}@Overridepublic String toString() {return "StackX [SIZE=" + SIZE + ", stack=" + Arrays.toString(stack) + ", top=" + top + "]";}}
public class Graph {private final int MAX_VERTS = 20;private Vertex vertexArray[]; // 存储顶点的数组private int adjMat[][]; // 存储是否有边界的矩阵数组, 0 表示没有边界，1 表示有边界private int nVerts; // 顶点个数private StackX stack; // 深度搜索时用来临时存储的栈private QueueX queue; // 广度搜索时用来临时存储的队列public Graph() {vertexArray = new Vertex[MAX_VERTS];adjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int i = 0; i < MAX_VERTS; i++) {for (int j = 0; j < MAX_VERTS; j++) {adjMat[i][j] = 0;}}stack = new StackX();queue = new QueueX();}public void addVertex(char lab) {vertexArray[nVerts++] = new Vertex(lab);}public void addEdge(int start, int end) {adjMat[start][end] = 1;adjMat[end][start] = 1;}public void displayVertex(int v) {System.out.print(vertexArray[v].label);}/** 深度优先搜索算法:做四件事 1. 用 peek()方法检查栈顶的顶点 2. 试图找到这个顶点还未访问的邻节点 3. 如果没有找到，出栈 4.* 如果找到这样的顶点，访问这个顶点，并把它放入栈 深度优先算法类似于从树的跟逐个沿不同路径访问到不同的叶节点*/public void depthFirstSearch() {// begin at vertex 0 从第一个顶点开始vertexArray[0].wasVisited = true; // make it 第一个顶点改为已访问displayVertex(0); // 输出第一个顶点stack.push(0); // 第一个顶点入栈while (!stack.isEmpty()) {// get an unvisited vertex adjacent to stack topint v = getAdjUnvisitedVertex(stack.peek()); // 寻找边界的下一个可达到的顶点 vif (v == -1) {// if no such vertex -1 就是没有了stack.pop(); // 出栈} else {// if it existsvertexArray[v].wasVisited = true; // 顶点 v 改为已访问displayVertex(v); // 输出顶点 vstack.push(v); // 顶点 v 入栈}}// stack is empty, so we're donefor (int i = 0; i < nVerts; i++) {vertexArray[i].wasVisited = false;}}// returns an unvisited vertex adj to vpublic int getAdjUnvisitedVertex(int v) {for (int i = 0; i < nVerts; i++) {// v 和i 之间有边，且 i 没被访问过if (adjMat[v][i] == 1 && vertexArray[i].wasVisited == false) {return i;}}return -1;}/** 广度优先搜索算法：做四件事 1. 用 remove()方法检查栈顶的顶点 2. 试图找到这个顶点还未访问的邻节点 3. 如果没有找到，该顶点出列 4.* 如果找到这样的顶点，访问这个顶点，并把它放入队列中 深度优先算法中，好像表现的要尽快远离起始点，在广度优先算法中，要尽可能靠近起始点。* 它首先访问其实顶点的所有邻节点，然后再访问较远的区域。这种搜索不能用栈，而要用队列来实现。 广度优先算法类似于从树的跟逐层往下访问直到底层*/public void breadthFirstSearch() {vertexArray[0].wasVisited = true;displayVertex(0);queue.insert(0);int v2;while (!queue.isEmpty()) {int v1 = queue.remove();// until it has no unvisited neighborswhile ((v2 = getAdjUnvisitedVertex(v1)) != -1) {vertexArray[v2].wasVisited = true;displayVertex(v2);queue.insert(v2);}}for (int i = 0; i < nVerts; i++) {vertexArray[i].wasVisited = false;}}// 最小生成树的方法public void minSpanningTree() {vertexArray[0].wasVisited = true;stack.push(0);while (!stack.isEmpty()) {int currentVertex = stack.peek();int v = getAdjUnvisitedVertex(currentVertex);if (v == -1) {stack.pop();} else {vertexArray[v].wasVisited = true;stack.push(v);displayVertex(currentVertex); // 输出当前顶点displayVertex(v); // 输出下一个顶点System.out.print(" ");}}// stack is empty, so we're donefor (int j = 0; j < nVerts; j++) {vertexArray[j].wasVisited = false;}}}
// 测试类public static void main(String[] args) {Graph graph = new Graph();graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addVertex('E');graph.addVertex('F');graph.addVertex('G');graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(3, 4);graph.addEdge(4, 5);graph.addEdge(4, 6);graph.addEdge(5, 6);System.out.println("广度优先搜索算法");graph.breadthFirstSearch();System.out.println("\n 深度优先搜索算法");graph.depthFirstSearch();System.out.println("\n 最小生成树法");graph.minSpanningTree();}
深度优先搜索的运用深度优先搜索是按照树的深度进行搜索的，所以又叫纵向搜索，在每一层只扩展一个节点，直到为树的规定深度或叶子节点为止。深度优先搜索的范围：在树深度已知情况下，并且树体系相当庞大时，深度优先搜索往往会比广度优先搜索优秀。但是如果树的深度不确定，而且很庞大的时候，用深度优先搜索可能会导致误入无穷分支。所以在选用广度和深度的时候还是要看具体情况而定。
广度和深度的比较
其实广度和深度在操作步骤上却只有一点不同，那就是选择哪一个侯补点作为下一个顶点的基准不同。
广度用的侯补点使用 “ 先入先出 ”（FIFO）的方式来管理的，因此可以使用 “ 队列 ”这个数据结构。深度用的候补点是 “ 后入先出 ”（LIFO）的方式，可以使用 “ 栈 ”这个数据结构。
再来看看广度和深度的比较图吧
