引言
图是计算机科学中一种重要的数据结构，广泛应用于表示网络、关系图、数据流等。图遍历是图算法的基础，包括深度优先搜索（DFS）和广度优先搜索（BFS）。本文将深入解析这两种图遍历算法，并提供Java实现，帮助读者轻松掌握无向图与有向图的遍历之道。
图的基本概念
在开始介绍图遍历算法之前，我们先回顾一下图的基本概念。
图的定义
图由节点（顶点）和连接这些节点的边组成。根据边的方向，图可以分为：
无向图：边的方向没有限制。
有向图：边有方向，表示节点之间的关系是单向的。
图的表示方法
图的表示方法主要有两种：
邻接矩阵：使用二维数组表示，其中元素表示节点之间的连接关系。
邻接表：使用链表表示，每个节点包含一个链表，链表中的元素表示与该节点相连的其他节点。
深度优先搜索（DFS）
DFS算法原理
深度优先搜索是一种非线性图遍历算法，它从某个节点开始，沿着一条路径深入探索，直到该路径的尽头，然后回溯，继续探索其他路径。
DFS算法步骤
从起始节点开始，将其标记为已访问。
遍历该节点的所有未访问的邻接节点，递归执行DFS算法。
当所有邻接节点都访问完毕后，回溯到上一个节点，继续探索其他路径。
DFS算法Java实现
public void dfs(int v) {
visited[v] = true;
System.out.print(v + ” “);
for (int i = 0; i < vexnum; i++) {
if (adjMatrix[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
public void DFSTraverse() {
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
dfs(i);
}
}
}
广度优先搜索（BFS）
BFS算法原理
广度优先搜索是一种线性图遍历算法，它从起始节点开始，逐层遍历相邻的节点，直到所有节点都被访问。
BFS算法步骤
创建一个队列，用于存储待访问的节点。
将起始节点入队，并将其标记为已访问。
从队列中取出一个节点，访问其所有未访问的邻接节点，并将它们标记为已访问，然后入队。
重复步骤3，直到队列为空。
BFS算法Java实现
public void bfs(int v) {
visited[v] = true;
System.out.print(v + " ");
Queue
queue.offer(v);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int i = 0; i < vexnum; i++) {
if (adjMatrix[node][i] == 1 && !visited[i]) {
visited[i] = true;
System.out.print(i + " ");
queue.offer(i);
}
}
}
}
public void BFSTraverse() {
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
bfs(i);
}
}
}
总结
本文深入解析了Java图遍历中的深度优先搜索和广度优先搜索算法，并提供了详细的Java实现。通过学习本文，读者可以轻松掌握无向图与有向图的遍历之道，为后续学习图算法打下坚实基础。