DFS(深度优先搜索)指的是从图的某个顶点出发，访问其所有能到达的顶点，并且尽可能深的搜索其中一支支路径的搜索算法。遍历过的点存放到形成的树中。树中每个结点的祖先结点都位于它的所有子树中，它的祖先结点包括它父亲结点和它父亲的祖先结点。DFS一般采用递归或者栈实现，其算法流程如下：
public static void dfs(int[][] graph, boolean[] visited, int n, int i) {
visited[i] = true;
System.out.print(i + " ");
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[i][j] == 1) {
dfs(graph, visited, n, j);
}
}
}
其中，graph是图的邻接矩阵，visited是标记数组，n是图中顶点数量，i是遍历的起始顶点。
BFS(广度优先搜索)指的是先访问已知起始顶点的直接相邻顶点，再依次访问这些相邻顶点的相邻顶点，并标记为已访问。采用队列的方式实现，算法流程如下：
public static void bfs(int[][] graph, boolean[] visited, int n, int i) {
visited[i] = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
while (!queue.isEmpty()) {
int curr = queue.poll();
System.out.print(curr + " ");
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[curr][j] == 1) {
visited[j] = true;
queue.offer(j);
}
}
}
}
其中，graph是图的邻接矩阵，visited是标记数组，n是图中顶点数量，i是遍历的起始顶点。
以如下二维数组表示的图为例：
int[][] graph = {
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 0, 1, 1, 0}
};
其中，每行表示一个顶点和其他顶点的连边情况，1表示连通，0表示不连通。
如果起始顶点为2，使用DFS算法，遍历整张图，会输出如下序列：
2 0 1 3 4
如果起始顶点为2，使用BFS算法，遍历整张图，会输出如下序列：
2 0 1 4 3
以如下二维数组表示的图为例：
int[][] graph = {
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 0},
{0, 1, 0, 1, 1},
{1, 0, 1, 0, 1},
{0, 0, 1, 1, 0}
};
其中，每行表示一个顶点和其他顶点的连边情况，1表示连通，0表示不连通。
如果起始顶点为0，使用DFS算法，遍历整张图，会输出如下序列：
0 1 2 3 4
如果起始顶点为0，使用BFS算法，遍历整张图，会输出如下序列：
0 1 3 2 4
本文链接：http://task.lmcjl.com/news/8046.html