圖的遍歷
從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)眷柔，且使每一個(gè)頂點(diǎn)僅被訪問一次，這一過程就叫做圖的遍歷（Traversing Graph）乳幸。
深度優(yōu)先遍歷
深度優(yōu)先搜索（Depth First Search）遍歷類似于樹的先序遍歷飞袋，是樹的先序遍歷的推廣蔗包，簡(jiǎn)稱為 DFS。
深度優(yōu)先搜索的基本方法是：從圖中某個(gè)頂點(diǎn) v 出發(fā)甫题，訪問此頂點(diǎn)馁筐，然后依次從 v 的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v 有路徑相通的頂點(diǎn)都被訪問到坠非；若此時(shí)圖中尚有頂點(diǎn)未被訪問敏沉，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程麻顶，直至圖中所有頂點(diǎn)都被訪問到為止赦抖。
以上圖（a）中無向圖為例舱卡，對(duì)其進(jìn)行深度優(yōu)先搜索遍歷的過程如圖（c）所示辅肾，其中黑色的實(shí)心箭頭代表訪問方向，空心箭頭代表回溯方向轮锥，箭頭旁的數(shù)字代表搜索順序矫钓，頂點(diǎn) a 是起點(diǎn)。遍歷過程如下：首先訪問頂點(diǎn) a舍杜，然后
a) 頂點(diǎn) a 的未曾訪問的鄰接點(diǎn)有 b新娜、d、e既绩，選擇鄰接點(diǎn) b 進(jìn)行訪問概龄；
b) 頂點(diǎn) b 的未曾訪問的鄰接點(diǎn)有 c、e饲握，選擇鄰接點(diǎn) c 進(jìn)行訪問私杜；
c) 頂點(diǎn) c 的未曾訪問的鄰接點(diǎn)有 e、f救欧，選擇鄰接點(diǎn) e 進(jìn)行訪問衰粹；
d) 頂點(diǎn) e 的未曾訪問的鄰接點(diǎn)只有 f，訪問 f笆怠；
e) 頂點(diǎn) f 無未曾訪問的鄰接點(diǎn)铝耻，回溯至 e；
f) 頂點(diǎn) e 無未曾訪問的鄰接點(diǎn)蹬刷，回溯至 c瓢捉；
g) 頂點(diǎn) c 無未曾訪問的鄰接點(diǎn)，回溯至 b办成；
h) 頂點(diǎn) b 無未曾訪問的鄰接點(diǎn)泡态，回溯至 a；
i) 頂點(diǎn) a 還有未曾訪問的鄰接點(diǎn) d诈火，訪問 d城菊；
j) 頂點(diǎn) d 無未曾訪問的鄰接點(diǎn)悠栓，回溯至 a粉洼。
到此，a 再?zèng)]有未曾訪問的鄰接點(diǎn)惊科，也不能向前回溯，從 a 出發(fā)能夠訪問的頂點(diǎn)均已訪問亮钦，并且此時(shí)圖中再?zèng)]有未曾訪問的頂點(diǎn)馆截，因此遍歷結(jié)束。由以上過程得到的遍歷序列為：a蜂莉，b蜡娶，c，e映穗，f窖张，d。
對(duì)于有向圖而言蚁滋，深度優(yōu)先搜索的執(zhí)行過程一樣宿接，例如上圖（b）中有向圖的深度優(yōu)先搜索過程如圖（d）所示。在這里需要注意的是從頂點(diǎn) a 出發(fā)深度優(yōu)先搜索只能訪問到 a , b , c , e , f辕录，而無法訪問到圖中所有頂點(diǎn)睦霎，所以搜索需要從圖中另一個(gè)未曾訪問的頂點(diǎn) d 開始進(jìn)行新的搜索，即圖（d）中的第 9 步走诞。
廣度優(yōu)先遍歷
廣度優(yōu)先搜索（Breadth First Search）遍歷類似于樹的層序遍歷副女，它是樹的按層遍歷的推廣，簡(jiǎn)稱為 BFS蚣旱。 例如下圖中碑幅，將第一幅圖稍微變形成第二幅圖，這樣就比較有層次感姻锁，此時(shí)在視覺上圖的形狀發(fā)生了改變枕赵，其實(shí)頂點(diǎn)和邊的關(guān)系還是完全相同的。
代碼實(shí)現(xiàn)
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @author wangxiaojian
*/
public class AMWGraph {
private ArrayList vertexList;// 存儲(chǔ)頂點(diǎn)的鏈表
private int[][] edges;// 鄰接矩陣位隶，用來存儲(chǔ)邊
private int numOfEdges;// 邊的數(shù)目
boolean[] isVisited;
public AMWGraph(int n) {
// 初始化矩陣拷窜，一維數(shù)組，和邊的數(shù)目
edges = new int[n][n];
vertexList = new ArrayList(n);
numOfEdges = 0;
}
// 得到結(jié)點(diǎn)的個(gè)數(shù)
public int getNumOfVertex() {
return vertexList.size();
}
// 得到邊的數(shù)目
public int getNumOfEdges() {
return numOfEdges;
}
// 返回結(jié)點(diǎn)i的數(shù)據(jù)
public Object getValueByIndex(int i) {
return vertexList.get(i);
}
// 返回v1,v2的權(quán)值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
// 插入結(jié)點(diǎn)
public void insertVertex(Object vertex) {
vertexList.add(vertexList.size(), vertex);
}
// 插入結(jié)點(diǎn)
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
numOfEdges++;
}
// 刪除結(jié)點(diǎn)
public void deleteEdge(int v1, int v2) {
edges[v1][v2] = 0;
numOfEdges--;
}
// 得到第一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)
public int getFirstNeighbor(int index) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
// 根據(jù)前一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)來取得下一個(gè)鄰接結(jié)點(diǎn)
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;
}
// 私有函數(shù)涧黄，深度優(yōu)先遍歷
private void depthFirstSearch(boolean[] isVisited, int i) {
// 首先訪問該結(jié)點(diǎn)篮昧，在控制臺(tái)打印出來
System.out.print(getValueByIndex(i) + " ");
// 置該結(jié)點(diǎn)為已訪問
isVisited[i] = true;
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isVisited[w]) {
depthFirstSearch(isVisited, w);
}
w = getNextNeighbor(i, w);
}
}
// 對(duì)外公開函數(shù)，深度優(yōu)先遍歷笋妥，與其同名私有函數(shù)屬于方法重載
public void depthFirstSearch() {
isVisited = new boolean[vertexList.size()];
for (int i = 0; i < getNumOfVertex(); i++) {
// 因?yàn)閷?duì)于非連通圖來說懊昨，并不是通過一個(gè)結(jié)點(diǎn)就一定可以遍歷所有結(jié)點(diǎn)的。
if (!isVisited[i]) {
depthFirstSearch(isVisited, i);
}
}
}
// 私有函數(shù)春宣，廣度優(yōu)先遍歷
private void broadFirstSearch(boolean[] isVisited, int i) {
int u, w;
LinkedList queue = new LinkedList();
// 訪問結(jié)點(diǎn)i
System.out.print(getValueByIndex(i) + " ");
isVisited[i] = true;
// 結(jié)點(diǎn)入隊(duì)列
queue.addLast(i);
while (!queue.isEmpty()) {
u = ((Integer) queue.removeFirst()).intValue();
w = getFirstNeighbor(u);
while (w != -1) {
if (!isVisited[w]) {
// 訪問該結(jié)點(diǎn)
System.out.print(getValueByIndex(w) + " ");
// 標(biāo)記已被訪問
isVisited[w] = true;
// 入隊(duì)列
queue.addLast(w);
}
// 尋找下一個(gè)鄰接結(jié)點(diǎn)
w = getNextNeighbor(u, w);
}
}
}
// 對(duì)外公開函數(shù)酵颁，廣度優(yōu)先遍歷
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;// 分別代表結(jié)點(diǎn)個(gè)數(shù)和邊的數(shù)目
String labels[] = { "1", "2", "3", "4", "5", "6", "7", "8" };// 結(jié)點(diǎn)的標(biāo)識(shí)
AMWGraph graph = new AMWGraph(n);
for (String label : labels) {
graph.insertVertex(label);// 插入結(jié)點(diǎn)
}
// 插入九條邊
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("深度優(yōu)先搜索序列為：");
graph.depthFirstSearch();
System.out.println();
System.out.println("廣度優(yōu)先搜索序列為：");
graph.broadFirstSearch();
}
}
運(yùn)行結(jié)果：
深度優(yōu)先搜索序列為：
1 2 4 8 5 3 6 7
廣度優(yōu)先搜索序列為：
1 2 3 4 5 6 7 8
