邻接矩阵实现深度优先遍历,Java
时间: 2024-05-22 09:08:05 浏览: 22
邻接矩阵实现深度优先遍历的基本思路如下:
1. 用邻接矩阵存储图的结构;
2. 从任意一个顶点开始,将该顶点标记为已访问;
3. 递归地访问该顶点的所有未访问过的邻居节点;
4. 重复2和3直到图中所有节点都被访问。
Java代码如下:
```java
public class Graph {
private int vertexCount; // 图中顶点的数量
private int[][] adjacencyMatrix; // 存储图的邻接矩阵
private boolean[] visited; // 标记每个顶点是否被访问过
public Graph(int vertexCount) {
this.vertexCount = vertexCount;
adjacencyMatrix = new int[vertexCount][vertexCount];
visited = new boolean[vertexCount];
}
// 添加边
public void addEdge(int i, int j) {
adjacencyMatrix[i][j] = 1;
adjacencyMatrix[j][i] = 1;
}
// 深度优先遍历
public void depthFirstTraversal(int startVertex) {
visited[startVertex] = true;
System.out.print(startVertex + " ");
for (int i = 0; i < vertexCount; i++) {
if (adjacencyMatrix[startVertex][i] == 1 && !visited[i]) {
depthFirstTraversal(i);
}
}
}
}
```