图的深度优先遍历举例

图是计算机科学中的一个重要概念，在许多领域都有应用，比如计算机网络、物流配送、电路设计等等。在对图进行操作时，遍历是一种常用的方式，而深度优先遍历又是遍历中的一种方法。本文将为读者介绍图的深度优先遍历，从算法步骤、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 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 时需要避免无限循环，因为这将导致遍历时间一直增加。