在人工智能和运筹学的领域中求解与图有关的许多应用中，这两个算法被
证明是非常有用的。并且，如需高效地研究图的基本性质，例如图的连通性以及图是否存
在环，这些算法也是必不可少的。
深度优先查找可以从任意顶点开始访问图的项点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。（如果有若干个这样的顶点，可以任意选择一个顶点。但在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。在我们的例子中，我们总是根据顶点的字母顺序来选择顶点。)
这个过程一直持续，直到遇到一个终点——该顶点的所有邻接顶点都已被访问过。在该终点上，该算法沿着来路后退一条边，并试着继续从那里访问未访问的顶点。在后退到起始顶点，并且起始顶点也是一个终点时，该算法最终停了下来。这样，起始顶点所在的连通分量的所有顶点都被访问过了。如果未访问过的顶点仍然存在，该算法必须从其中任一顶点开始，重复上述过程。
在深度优先查找遍历的时候构造一个所谓的深度优先查找森林(depth-first search forest)也是非常有用的。
DFS(G)
//实现给定图的深度优先查找遍历
//输入：图G=<V,E>
//输出：图G的顶点，按照被DFS第一次访问到的先后次序，用连续的整数标记将V中的每个顶点标记为0，表示还”未访问“
count <- 0
for each vertex v in V do
if v is marked with 0
dfs(v)
dfs(v)
//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值
//根据遇到它们的先后次序，给它们附上相应的值
count <- count+1;mark v with count
for each vertex in V adjacent to do
if w is marked with 0
dfs(w)
package com.算法;
import java.util.LinkedList;
import java.util.List;
/**
* @Author Lanh
**/
public class DFSDemo {
public static void main(String[] args) {
List<Vertex> Graph = new LinkedList<>();
Vertex A = new Vertex('A',new LinkedList<>());
Vertex B = new Vertex('B',new LinkedList<>());
Vertex C = new Vertex('C',new LinkedList<>());
Vertex D = new Vertex('D',new LinkedList<>());
Graph.add(A);Graph.add(B);Graph.add(C);Graph.add(D);
//添加边
A.list.add(B);
A.list.add(C);
B.list.add(D);
C.list.add(B);
C.list.add(D);
DFS(Graph);
Graph.forEach(V -> {
System.out.println(V.mark+"："+V.v);
});
}
static int count = 0;
public static void DFS(List<Vertex> Graph){
Graph.forEach(V -> {
if (V.mark==0) dfs(V);
});
}
private static void dfs(Vertex vertex){
count++;
vertex.mark = count;
if (vertex.list != null && vertex.list.size() >0){
vertex.list.forEach(V -> {
if (V.mark==0) dfs(V);
});
}
}
static class Vertex{
char v;
List<Vertex> list = null;
int mark = 0;
public Vertex(char v,List<Vertex> list){
this.v = v;
this.list = list;
}
}
}
结果如下：
如果说深度优先查找遍历表现出来的是一种勇气（该算法尽可能地离“家”远些），广度优先查找遍历表现出来的则是一种谨慎。它按照一种同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后是离它两条边的所有未访问顶点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点，该算法必须从图的其他连通分量中的任意顶点重新开始。
使用队列（注意它和深度优先查找的区别！）来跟踪广度优先查找的操作是比较方便的。该队列先从遍历的初始顶点开始，将该顶点标记为已访问。在每次迭代的时候，该算法找出所有和队头顶点邻接的未访问顶点，把它们标记为已访问，再把它们入队。然后，将队头顶点从队列中移去。
BFS(G)
//实现给定图的广度优先查找遍历
//输入：图G=<V,E>
//输出：图G的顶点，按照被BFS遍历访问到的先后次序，用连续的整数标记将V中的每个顶点标记为0，表示还”未访问“
count <- 0
for each vertex v in V do
if v is marked with 0
bfs(v)
bfs(v)
//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值
//根据遇到它们的先后次序，给它们附上相应的值
count <- count+1;mark v with count;initalize a queue with v
while the queue is not empty do
for each vertex in V adjacent to do
if w is marked with 0
count++;mark w with count
add w to the queue
remove the front vertex from the queue
package com.算法;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* @Author Lanh
**/
public class BFSDemo {
public static void main(String[] args) {
List<Vertex> Graph = new LinkedList<>();
Vertex A = new Vertex('A',new LinkedList<>());
Vertex B = new Vertex('B',new LinkedList<>());
Vertex C = new Vertex('C',new LinkedList<>());
Vertex D = new Vertex('D',new LinkedList<>());
Graph.add(A);Graph.add(B);Graph.add(C);Graph.add(D);
//添加边
A.list.add(B);
A.list.add(C);
B.list.add(D);
C.list.add(B);
C.list.add(D);
BFS(Graph);
Graph.forEach(V -> {
System.out.println(V.mark+"："+V.v);
});
}
static int count = 0;
public static void BFS(List<Vertex> Graph){
Graph.forEach(V -> {
if (V.mark==0) bfs(V);
});
}
private static void bfs(Vertex vertex) {
count++;
vertex.mark = count;
Queue<Vertex> queue = new LinkedList<>();
queue.offer(vertex);
while (!queue.isEmpty()){
vertex = queue.poll();
if (vertex.list!=null && vertex.list.size() > 0){
vertex.list.forEach(v -> {
if (v.mark==0){
count++;
v.mark = count;
queue.offer(v);
}
});
}
}
}
static class Vertex{
char v;
List<Vertex> list = null;
int mark = 0;
public Vertex(char v,List<Vertex> list){
this.v = v;
this.list = list;
}
}
}
结果如下：
