图的深度优先遍历举例
图是计算机科学中的一个重要概念，在许多领域都有应用，比如计算机网络、物流配送、电路设计等等。在对图进行操作时，遍历是一种常用的方式，而深度优先遍历又是遍历中的一种方法。本文将为读者介绍图的深度优先遍历，从算法步骤、Java代码示例以及时间复杂度等方面分析。
算法步骤
深度优先遍历（Depth-First Search，简称DFS）是一种用于遍历图的算法。这种算法最开始访问根节点（起点），然后沿着树的深度遍历下去，直到遇到叶子节点。当最后一个节点被访问后，算法将回溯到上一个节点，然后将其访问其未被访问的子节点。该步骤将重复执行，直到所有节点都被访问为止。
实际上，DFS不同于BFS（广度优先遍历），它在访问邻居节点时不按层级，而是不断向下遍历。以下是DFS的基本步骤：
1. 选择一个起点开始遍历。
2. 访问该节点。
3. 标记所访问的节点为已访问。
4. 找到该节点的邻接节点。
5. 遍历该节点的邻接节点。
6. 重复步骤3-5，直至遍历完所有节点。
Java代码示例
下面的Java示例程序根据邻接表来实现DFS：
```
import java.util.Stack;
import java.util.Scanner;
public class DepthFirstSearch {
private Stack
private int numberOfVertices;
private int adjacencyMatrix[][];
public DepthFirstSearch(int numberOfVertices) {
this.numberOfVertices = numberOfVertices;
adjacencyMatrix = new int[numberOfVertices][numberOfVertices];
stack = new Stack<>();
}
public void dfs(int startVertex) {
boolean visited[] = new boolean[numberOfVertices];
int element = startVertex;
System.out.print(element + "\t");
visited[startVertex] = true;
stack.push(startVertex);
while (!stack.isEmpty()) {
element = stack.peek();
int i = element;
while (i < numberOfVertices) {
if (adjacencyMatrix[element][i] == 1 && !visited[i]) {
stack.push(i);
visited[i] = true;
System.out.print(i + "\t");
element = i;
i = -1;
}
i++;
}
stack.pop();
}
}
public static void main(String... arg) {
int numberOfVertices, startVertex;
Scanner scanner = null;
try {
System.out.println("Enter the number of vertices in the graph");
scanner = new Scanner(System.in);
numberOfVertices = scanner.nextInt();
int adjacencyMatrix[][] = new int[numberOfVertices][numberOfVertices];
System.out.println("Enter the adjacency matrix");
for (int i = 0; i < numberOfVertices; i++)
for (int j = 0; j < numberOfVertices; j++)
adjacencyMatrix[i][j] = scanner.nextInt();
System.out.println("Enter the starting vertex");
startVertex = scanner.nextInt();
DepthFirstSearch dfs = new DepthFirstSearch(numberOfVertices);
dfs.dfs(startVertex);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
if (scanner != null)
scanner.close();
}
}
}
```
时间复杂度
在最坏情况下，每条边只会被遍历一次，时间复杂度为O(E+V)，其中 E 是边的数量，V 是节点的数量。这可以很好地解释为什么使用 DFS 时需要避免无限循环，因为这将导致遍历时间一直增加。
