Java中如何将拓扑排序的数据结构从<Integer>改为<String>

不用完全重写整个实现！你只需要借助Java的泛型（Generic）特性，把原来绑定Integer的代码改成通用类型，这样不仅能支持String，还能兼容其他任意实现了equals和hashCode的类型，扩展性拉满。我给你一步步拆解修改步骤：

首先，在你的拓扑排序类定义上添加泛型占位符<T>，然后把所有原来用Integer存储节点的地方，替换成泛型参数T——比如邻接表、入度表这些核心数据结构：

public class TopologicalSort<T> {
    // 邻接表：键是节点，值是该节点的所有邻接节点
    private Map<T, List<T>> adjacencyList;
    // 入度表：键是节点，值是该节点的入度数值
    private Map<T, Integer> inDegreeMap;

    // 构造方法初始化数据结构
    public TopologicalSort() {
        adjacencyList = new HashMap<>();
        inDegreeMap = new HashMap<>();
    }
}

原来的addEdge(Integer u, Integer v)要改成接受泛型参数，同时要确保所有节点都被正确加入入度表（避免后续排序时漏掉节点）：

public void addEdge(T source, T destination) {
    // 确保源节点存在于邻接表，不存在则创建空列表
    adjacencyList.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
    
    // 维护入度表：源节点入度默认0（如果之前没记录）
    inDegreeMap.putIfAbsent(source, 0);
    // 目标节点入度+1，没有则从0开始加
    inDegreeMap.put(destination, inDegreeMap.getOrDefault(destination, 0) + 1);
}

原来的排序逻辑（比如Kahn算法或者DFS递归）不需要大改，只需要把涉及节点类型的地方换成T就行。这里以常用的Kahn算法为例：

public List<T> sort() {
    Queue<T> queue = new LinkedList<>();
    List<T> sortedResult = new ArrayList<>();

    // 把所有入度为0的节点加入队列
    for (Map.Entry<T, Integer> entry : inDegreeMap.entrySet()) {
        if (entry.getValue() == 0) {
            queue.add(entry.getKey());
        }
    }

    while (!queue.isEmpty()) {
        T currentNode = queue.poll();
        sortedResult.add(currentNode);

        // 遍历当前节点的邻接节点，入度减1
        if (adjacencyList.containsKey(currentNode)) {
            for (T neighbor : adjacencyList.get(currentNode)) {
                inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
                if (inDegreeMap.get(neighbor) == 0) {
                    queue.add(neighbor);
                }
            }
        }
    }

    // 检查是否存在环：如果结果长度不等于节点总数，说明有环
    if (sortedResult.size() != inDegreeMap.size()) {
        throw new IllegalArgumentException("图中存在环，无法完成拓扑排序");
    }

    return sortedResult;
}

现在你就可以直接用String节点调用了，完全符合你的需求：

public static void main(String[] args) {
    TopologicalSort<String> ts = new TopologicalSort<>();
    ts.addEdge("a", "b");
    ts.addEdge("a", "c");
    ts.addEdge("b", "d");
    ts.addEdge("c", "d");

    List<String> sortedNodes = ts.sort();
    System.out.println(sortedNodes); // 输出类似 [a, b, c, d] 或 [a, c, b, d]，取决于队列顺序
}

• 确保你的节点类型（比如String）已经正确实现了equals和hashCode——String本身已经满足，所以不用额外处理；如果是自定义类型，一定要重写这两个方法，否则Map无法正确识别节点。
• 不要保留任何依赖Integer特性的逻辑（比如用节点值做数值运算），拓扑排序只关心节点的关联性，不需要节点的数值属性。

内容的提问来源于stack exchange，提问作者Marky_rick