用Java写一个邻接矩阵实现图的深度遍历和广度遍历的代码
时间: 2023-06-09 22:03:47 浏览: 127
好的,以下是Java实现邻接矩阵的图的深度遍历和广度遍历的代码:
```
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Graph {
private int vertexCount;
private boolean[][] adjMatrix;
public Graph(int vertexCount) {
this.vertexCount = vertexCount;
adjMatrix = new boolean[vertexCount][vertexCount];
}
public void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
public void depthFirstTraversal() {
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[vertexCount];
stack.push(0); // start from vertex 0
visited[0] = true;
while (!stack.isEmpty()) {
int currentVertex = stack.pop();
System.out.print(currentVertex + " ");
for (int i = 0; i < vertexCount; i++) {
if (adjMatrix[currentVertex][i] && !visited[i]) {
stack.push(i);
visited[i] = true;
}
}
}
}
public void breadthFirstTraversal() {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[vertexCount];
queue.add(0); // start from vertex 0
visited[0] = true;
while (!queue.isEmpty()) {
int currentVertex = queue.remove();
System.out.print(currentVertex + " ");
for (int i = 0; i < vertexCount; i++) {
if (adjMatrix[currentVertex][i] && !visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
System.out.print("Depth First Traversal: ");
graph.depthFirstTraversal();
System.out.println();
System.out.print("Breadth First Traversal: ");
graph.breadthFirstTraversal();
}
}
```
这个代码实现了一个Graph类,可以通过`addEdge`方法添加边,然后调用`depthFirstTraversal`方法和`breadthFirstTraversal`方法就可以实现深度遍历和广度遍历。在`main`方法中,我们创建了一个有5个顶点的图,并添加了4条边,然后运行代码就可以看到深度遍历和广度遍历的结果了。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)