图 - DFS深度优先搜索和BFS广度优先搜索

图的概念

  图是一种非线性表数据结构；图中的元素叫顶点（vertex），图中一个顶点可以与任意其他顶点建立连接关系，我们把这种建立的关系叫做边（edge），和顶点相连的边的条数叫度（degree）；在有向图中又分为入度和出度，入度表示多少条边指向这个顶点，出度表示有多少条边是以这个顶点为起点指向其他顶点。

图的存储方法

1. 邻接矩阵（adjacency matrix）

  邻接矩阵底层依赖的是一个二维数组，如果顶点 i 和 j 之间有边，那么就将 A[i][j] 和 A[j][i]标记为1,；如果是有向图，那么顶点 i 指向 j ，那么将 A[i][j]标记为1。如果是带权图，数组中就存储相应的权重。如下图所示：

缺点：
  对于无向图而言，A[i][j] 和 A[j][i] 存储的值是相等的，实际上只需要存储一个即可。因此对于无向图的二维数组中，我们以对角线划分为上下两部分，那只需上面或下面的一半空间即可，浪费了一半空间。
优点：
  邻接矩阵存储简单，基于数组，在获取两个顶点的关系的时候，非常高效；还有一个好处是计算方便，可以将图的运算转换为矩阵运算。

2. 邻接表（adjacency list）

  针对上述缺点，使用邻接表来存储图，每个顶点对应一条链表，链表中存储的是与这个顶点相连的其他顶点。下面是一个有向图的邻接表表示，无向图的可以类似的表示，如下所示：

图搜索

1. BFS（breath first search）广度优先

  广度优先搜索，是一种地毯式的搜索方式，就是从查找的起始顶点开始，依次往外搜索，可以类比图的按照层来进行遍历，一层一层的搜索。如下图所示：

  s是起始顶点，t是终止顶点，先遍历0的相邻的顶点 1 和 3 ，然后接着访问 1 和 3 的相邻顶点 2 和 4，然后再访问5 和 6，这样就找到了终止顶点 6。
  下面是代码实现：

public void bfs(int s, int t) {
	if(s == t) return;
	// 记录是否被遍历过的标志位
	boolean[] visited = new boolean[vertex];
	visited[s] = true;
	// 队列存储已经被访问过，但是相邻顶点还未访问过的顶点
	Queue<Integer> queue = new LinkedList<>();
	queue.add(s);
	// 记录搜索路径，preVertex[1] = 0, 代表 1 是从 0顶点遍历而来
	int[] preVertex = new int[vertex];
	for (int i = 0; i < vertex; i++) {
		preVertex[i] = -1;
	}
	// 开始遍历
	while(!queue.isEmpty()) {
		int v = queue.poll();
		// 访问v顶点，邻接表上的顶点，也即与v相连的顶点
		for (int i = 0; i < adjacencyMatrix[v].size(); i++) {
			int q = adjacencyMatrix[v].get(i);
			if(!visited[q]) {
				// 存储被访问的顶点
				preVertex[q] = v;
				if(q == t) {
					printPath(preVertex, s, t);
					return;
				}
				visited[q] = true;
				queue.add(q);
			}
		}	
	}
}

  下面分析一下它的时间和空间复杂度，最坏的情况下，顶点 t 离 s 很远，需要遍历整个图才能找到，这个时候，每个顶点都需要进出一次队列，每个边也都会被访问一次，所以广度优先搜索的时间复杂度是 O(V + E)，V 是顶点数，E是边数。
  空间复杂度，主要消耗在visited、queue、preVertex 数组上，这三个存储空间大小都不会超过顶点数，所以空间复杂度是 O(V)。

2. DFS （depth first search）深度优先

  深度优先搜索的策略和广度优先搜索的策略完全不一样，可以类比走迷宫，当发现遇到死胡同时，需要退回到之前的岔路口，重新选择一条路继续走，直到找到出口。如下图所示，从s到t，其中实线箭头表示遍历，虚线表示回退。

  深度优先搜索的实现适合使用递归来实现，下面的代码就是使用递归来实现的深度优先搜索：

// 定义成员变量，用于标识已经找到终点
boolean found = false;
public void dfs(int s, int t) {
	found = false;
	boolean[] visited = new boolean[vertex];
	int[] preVertex= new int[vertex];
	for(int i = 0; i < vertex; i++) {
		preVertex[i] = -1;
	}
	
	// 递归调用
	recursionDfs(s, t, visited, preVertex);
	printPath(preVertex, s, t);
}

public void recursionDfs(int w, int t, boolean[] visited, int[] preVertex) {
	if(found == true) return;
	visited[w] = true;
	if(w == t) {
		found = true;
		return;
	}
	// 开始遍历
	for(int i = 0; i < adjacencyMatrix[w].size(); i++) {
		if(found == true) return;
		int q = adjacencyMatrix[w].get(i);
		if(!visited[q]) {
			preVertex[q] = w;
			recursionDfs(q, t, visited, preVertex);
		}
	}
}

  下面分析一下它的时间和空间复杂度，从图中可以看出，每条边最多被访问两次，一次是遍历，一次是回退，所以图的时间复杂度是 O(E)，E表示边数；空间消耗主要是 visited、preVertex数组，以及递归调用的栈，他们的大小和顶点的个数成正比，因此空间复杂度是 O(V)，V表示顶点个数。
  总结一下，广度优先搜索和深度优先搜索，是两种不同搜索的策略，广度优先搜索能够找到一条最佳路径，而深度优先搜索却不能，因为广度优先搜索离它最近的点会最早被访问到。