图的遍历
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。
深度优先遍历
深度优先搜索（Depth First Search）遍历类似于树的先序遍历，是树的先序遍历的推广，简称为 DFS。
深度优先搜索的基本方法是：从图中某个顶点 v 出发，访问此顶点，然后依次从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
以上图（a）中无向图为例，对其进行深度优先搜索遍历的过程如图（c）所示，其中黑色的实心箭头代表访问方向，空心箭头代表回溯方向，箭头旁的数字代表搜索顺序，顶点 a 是起点。遍历过程如下：首先访问顶点 a，然后
a) 顶点 a 的未曾访问的邻接点有 b、d、e，选择邻接点 b 进行访问；
b) 顶点 b 的未曾访问的邻接点有 c、e，选择邻接点 c 进行访问；
c) 顶点 c 的未曾访问的邻接点有 e、f，选择邻接点 e 进行访问；
d) 顶点 e 的未曾访问的邻接点只有 f，访问 f；
e) 顶点 f 无未曾访问的邻接点，回溯至 e；
f) 顶点 e 无未曾访问的邻接点，回溯至 c；
g) 顶点 c 无未曾访问的邻接点，回溯至 b；
h) 顶点 b 无未曾访问的邻接点，回溯至 a；
i) 顶点 a 还有未曾访问的邻接点 d，访问 d；
j) 顶点 d 无未曾访问的邻接点，回溯至 a。
到此，a 再没有未曾访问的邻接点，也不能向前回溯，从 a 出发能够访问的顶点均已访问，并且此时图中再没有未曾访问的顶点，因此遍历结束。由以上过程得到的遍历序列为：a，b，c，e，f，d。
对于有向图而言，深度优先搜索的执行过程一样，例如上图（b）中有向图的深度优先搜索过程如图（d）所示。在这里需要注意的是从顶点 a 出发深度优先搜索只能访问到 a , b , c , e , f，而无法访问到图中所有顶点，所以搜索需要从图中另一个未曾访问的顶点 d 开始进行新的搜索，即图（d）中的第 9 步。
广度优先遍历
广度优先搜索（Breadth First Search）遍历类似于树的层序遍历，它是树的按层遍历的推广，简称为 BFS。 例如下图中，将第一幅图稍微变形成第二幅图，这样就比较有层次感，此时在视觉上图的形状发生了改变，其实顶点和边的关系还是完全相同的。
代码实现
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @author wangxiaojian
*/
public class AMWGraph {
private ArrayList vertexList;// 存储顶点的链表
private int[][] edges;// 邻接矩阵，用来存储边
private int numOfEdges;// 边的数目
boolean[] isVisited;
public AMWGraph(int n) {
// 初始化矩阵，一维数组，和边的数目
edges = new int[n][n];
vertexList = new ArrayList(n);
numOfEdges = 0;
}
// 得到结点的个数
public int getNumOfVertex() {
return vertexList.size();
}
// 得到边的数目
public int getNumOfEdges() {
return numOfEdges;
}
// 返回结点i的数据
public Object getValueByIndex(int i) {
return vertexList.get(i);
}
// 返回v1,v2的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
// 插入结点
public void insertVertex(Object vertex) {
vertexList.add(vertexList.size(), vertex);
}
// 插入结点
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
numOfEdges++;
}
// 删除结点
public void deleteEdge(int v1, int v2) {
edges[v1][v2] = 0;
numOfEdges--;
}
// 得到第一个邻接结点的下标
public int getFirstNeighbor(int index) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
// 根据前一个邻接结点的下标来取得下一个邻接结点
public int getNextNeighbor(int v1, int v2) {
for (int j = v2 + 1; j < vertexList.size(); j++) {
if (edges[v1][j] > 0) {
return j;
}
}
return -1;
}
// 私有函数，深度优先遍历
private void depthFirstSearch(boolean[] isVisited, int i) {
// 首先访问该结点，在控制台打印出来
System.out.print(getValueByIndex(i) + " ");
// 置该结点为已访问
isVisited[i] = true;
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isVisited[w]) {
depthFirstSearch(isVisited, w);
}
w = getNextNeighbor(i, w);
}
}
// 对外公开函数，深度优先遍历，与其同名私有函数属于方法重载
public void depthFirstSearch() {
isVisited = new boolean[vertexList.size()];
for (int i = 0; i < getNumOfVertex(); i++) {
// 因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。
if (!isVisited[i]) {
depthFirstSearch(isVisited, i);
}
}
}
// 私有函数，广度优先遍历
private void broadFirstSearch(boolean[] isVisited, int i) {
int u, w;
LinkedList queue = new LinkedList();
// 访问结点i
System.out.print(getValueByIndex(i) + " ");
isVisited[i] = true;
// 结点入队列
queue.addLast(i);
while (!queue.isEmpty()) {
u = ((Integer) queue.removeFirst()).intValue();
w = getFirstNeighbor(u);
while (w != -1) {
if (!isVisited[w]) {
// 访问该结点
System.out.print(getValueByIndex(w) + " ");
// 标记已被访问
isVisited[w] = true;
// 入队列
queue.addLast(w);
}
// 寻找下一个邻接结点
w = getNextNeighbor(u, w);
}
}
}
// 对外公开函数，广度优先遍历
public void broadFirstSearch() {
isVisited = new boolean[vertexList.size()];
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
broadFirstSearch(isVisited, i);
}
}
}
public static void main(String args[]) {
int n = 8, e = 9;// 分别代表结点个数和边的数目
String labels[] = { "1", "2", "3", "4", "5", "6", "7", "8" };// 结点的标识
AMWGraph graph = new AMWGraph(n);
for (String label : labels) {
graph.insertVertex(label);// 插入结点
}
// 插入九条边
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
graph.insertEdge(3, 7, 1);
graph.insertEdge(4, 7, 1);
graph.insertEdge(2, 5, 1);
graph.insertEdge(2, 6, 1);
graph.insertEdge(5, 6, 1);
graph.insertEdge(1, 0, 1);
graph.insertEdge(2, 0, 1);
graph.insertEdge(3, 1, 1);
graph.insertEdge(4, 1, 1);
graph.insertEdge(7, 3, 1);
graph.insertEdge(7, 4, 1);
graph.insertEdge(6, 2, 1);
graph.insertEdge(5, 2, 1);
graph.insertEdge(6, 5, 1);
System.out.println("深度优先搜索序列为：");
graph.depthFirstSearch();
System.out.println();
System.out.println("广度优先搜索序列为：");
graph.broadFirstSearch();
}
}
运行结果：
深度优先搜索序列为：
1 2 4 8 5 3 6 7
广度优先搜索序列为：
1 2 3 4 5 6 7 8
