能解释一下每一行代码的意思
时间: 2024-03-05 17:48:59 浏览: 152
当然可以,以下是每行代码的意思:
```java
import java.util.*;
```
这行代码导入了 `java.util` 包,其中包括了我们在这个程序中使用的集合类。
```java
public class TopologicalSort<T> {
```
这行代码定义了一个泛型类 `TopologicalSort`,它可以接受任意类型的参数。
```java
private Map<T, List<T>> graph = new HashMap<>();
private Set<T> visited = new HashSet<>();
private Stack<T> stack = new Stack<>();
```
这三行代码定义了三个私有变量,分别是一个 `Map`、一个 `Set` 和一个 `Stack`。这三个变量用于表示有向图、已访问的节点和排序结果。
```java
public void addEdge(T node, T neighbor) {
graph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);
}
```
这个方法用于添加节点和边。它将节点和相邻节点存储在一个 `Map` 中,如果节点还没有对应的列表,则创建一个新的列表。
```java
public List<T> sort() {
for (T node : graph.keySet()) {
if (!visited.contains(node)) {
dfs(node);
}
}
List<T> result = new ArrayList<>();
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
```
这个方法用于进行拓扑排序。它首先遍历所有的节点,如果节点没有被访问过,则调用 `dfs` 方法进行深度优先搜索。搜索完成后,将排序结果保存在一个 `List` 中,并返回该列表。
```java
private void dfs(T node) {
visited.add(node);
for (T neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor);
}
}
stack.push(node);
}
```
这个方法用于对一个节点进行深度优先搜索。它首先将该节点标记为已访问,然后搜索该节点的相邻节点,如果相邻节点还没有被访问,则递归调用 `dfs` 方法。搜索完成后,将该节点压入一个 `Stack` 中。
```java
public static void main(String[] args) {
TopologicalSort<String> topoSort = new TopologicalSort<>();
// 添加节点和边
topoSort.addEdge("A", "C");
topoSort.addEdge("B", "C");
topoSort.addEdge("C", "D");
topoSort.addEdge("D", "E");
topoSort.addEdge("F", "E");
topoSort.addEdge("F", "G");
// 拓扑排序
List<String> result = topoSort.sort();
System.out.println(result);
}
```
这个 `main` 方法用于测试 `TopologicalSort` 类。它首先创建了一个 `TopologicalSort<String>` 对象,然后添加了一些节点和边。最后调用 `sort` 方法,得到了拓扑排序的结果,并将结果输出到控制台。
阅读全文