List<Integer>[] graph = new LinkedList[numCourses];
时间: 2024-05-31 08:12:27 浏览: 13
这段代码是用来创建一个有向图的邻接表表示法。其中`numCourses`是课程的数量,`LinkedList`是Java中的链表数据结构,`List<Integer>[]`是一个泛型数组,每个元素都是一个链表,用来存储与当前节点相连的所有节点。
具体来说,我们可以把每个节点看作一个课程,在这个图中,每个节点有向连接到其他的节点,表示先修课程和后续课程之间的关系。通过使用邻接表的方式,我们可以快速地找到每个节点的后继节点。
相关问题
java广度优先搜索
Java广度优先搜索(BFS)是一种图遍历算法,用于在一个图中从给定的起始节点开始,按照广度优先的顺序遍历所有可达节点。BFS通常使用队列来实现。
以下是Java实现广度优先搜索的基本步骤:
1. 创建一个队列,并将起始节点入队。
2. 创建一个HashSet或HashMap来记录已访问的节点,防止重复访问。
3. 进入循环,直到队列为空:
- 从队列中取出一个节点作为当前节点。
- 将当前节点标记为已访问。
- 处理当前节点,例如输出节点值或进行其他操作。
- 将当前节点的所有未访问过的邻居节点入队。
4. 循环结束后,遍历完成。
下面是一个简单的Java代码示例,演示了如何使用BFS遍历一个图:
```java
import java.util.*;
public class BFS {
public void bfsTraversal(Graph graph, int startNode) {
Queue<Integer> queue = new LinkedList<>(); Set<Integer> visited = new HashSet<>();
queue.add(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
int currentNode = queue.poll();
System.out.print(currentNode + " ");
List<Integer> neighbors = graph.getNeighbors(currentNode);
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
BFS bfs = new BFS();
bfs.bfsTraversal(graph, 0);
}
}
class Graph {
private int vertices;
private List<List<Integer>> adjacencyList;
public Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination) {
adjacencyList.get(source).add(destination);
adjacencyList.get(destination).add(source);
}
public List<Integer> getNeighbors(int vertex) {
return adjacencyList.get(vertex);
}
}
```
这段代码中,我们创建了一个Graph类来表示图,使用邻接表来存储图的结构。然后,我们使用BFS类中的bfsTraversal方法来执行广度优先搜索,并传入起始节点的索引。
广度优先算法java
以下是广度优先搜索算法的Java代码示例:
```java
import java.util.*;
public class BFS {
public static void main(String[] args) {
// 创建一个邻接表表示的图
int n = 6;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
graph.get(0).add(1);
graph.get(0).add(2);
graph.get(1).add(2);
graph.get(2).add(0);
graph.get(2).add(3);
graph.get(3).add(3);
graph.get(4).add(5);
graph.get(5).add(4);
// 从节点0开始进行广度优先搜索
bfs(graph, 0);
}
public static void bfs(List<List<Integer>> graph, int start) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[graph.size()];
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
}
}
```
该代码实现了从节点0开始进行广度优先搜索的功能,输出结果为0 1 2 3。
相关推荐
![text/x-java](https://img-home.csdnimg.cn/images/20210720083646.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)