用java帮我写一份代码,从键盘输入的数据建立图,并进行深度优先搜索和广度优先搜索
时间: 2024-04-06 18:34:15 浏览: 16
好的,以下是用 Java 实现从键盘输入的数据建立图,并进行深度优先搜索和广度优先搜索的代码:
```java
import java.util.*;
public class Graph {
private int V; // 图中顶点的数量
private LinkedList<Integer>[] adj; // 邻接表表示图
// 构造函数,初始化图
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList<>();
}
}
// 添加边
public void addEdge(int v, int w) {
adj[v].add(w);
}
// 深度优先搜索
public void DFS(int v) {
boolean[] visited = new boolean[V];
DFSUtil(v, visited);
}
private void DFSUtil(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
DFSUtil(n, visited);
}
}
}
// 广度优先搜索
public void BFS(int s) {
boolean[] visited = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
// 测试代码
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入顶点和边的数量
int V = sc.nextInt();
int E = sc.nextInt();
// 创建图
Graph g = new Graph(V);
// 输入边
for (int i = 0; i < E; ++i) {
int v = sc.nextInt();
int w = sc.nextInt();
g.addEdge(v, w);
}
// 深度优先搜索
System.out.print("深度优先搜索顺序:");
g.DFS(0);
System.out.println();
// 广度优先搜索
System.out.print("广度优先搜索顺序:");
g.BFS(0);
System.out.println();
}
}
```
在测试代码中,我们先输入顶点和边的数量,然后输入每一条边的起点和终点。最后调用 `DFS` 和 `BFS` 函数,分别输出深度优先搜索和广度优先搜索的顺序。
注意:这里的顶点编号从 0 开始,如果需要从 1 开始,请将输入的顶点编号减 1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)