拓扑排序方法实现报错排查及修复咨询

问题背景 #

我正在实现拓扑排序方法，但测试时遇到以下错误：

• 预期抛出java.lang.IllegalArgumentException异常但未触发
• 预期结果长度为<5>，实际返回<0>
• 出现异常java.lang.IllegalArgumentException: No path found

相关实现代码如下：

/**
* Helper method for the sort method in the GraphUtility class to generate a sorted ordering of the vertices in the
* graph. Note that a graph may have more than one valid ordering, and any such ordering is accepted.
*
* @param sources      - the source from where we'll be starting our sort
* @param destinations - the destination, or end point, of our sort
* @return a sorted ordering of the vertices in the graph
*/
public List topologicalSort(List sources, List destinations) throws IllegalArgumentException {
createGraph(sources, destinations);

    Queue<Vertex<Type>> doableTasks = new LinkedList<>();
    List<Type> output = new LinkedList<>();

    for (Vertex<Type> task : vertices.values()) {
        if (task.getIndegree() == 0) {
            doableTasks.add(task);
        }
    }

    // counter for things we've visited in the queue
    int counter = 0;

    while (!(doableTasks.isEmpty())) {
        Vertex<Type> task = doableTasks.remove();
        counter++;
        output.add(task.getName());

        for (Iterator<Edge<Type>> it = task.edges(); it.hasNext(); ) {
            Edge<Type> outEdge = it.next();

            Vertex<Type> neighbor = outEdge.getOtherVertex();

            neighbor.setIndegree(neighbor.getIndegree() - 1);

            if (neighbor.getIndegree() == 0) {
                doableTasks.add(neighbor);
            }
        }
    }

    if (counter > output.size()) {
        throw new IllegalArgumentException("The size doesn't match.");
    }
    return output;
}

public static <Type> void createGraph(List<Type> sources, List<Type> destinations)
        throws IllegalArgumentException {
    if (sources.size() != destinations.size()) {
        throw new IllegalArgumentException("Must have the same size");
    }

    Graph<Type> graph = new Graph<>();

    for (int i = 0; i < sources.size(); i++) {
        Type sourceData = sources.get(i);
        Type destData = destinations.get(i);
        graph.addEdge(sourceData, destData);
    }
}

public class Vertex {

// Used to id the Vertex
private final Type name;

// Adjacency list
private final LinkedList<Edge<Type>> adj;
private int indegree;

public int getIndegree() {
    return indegree;
}

public int setIndegree(int newIndegree) {
    return indegree = newIndegree;
}

/**
 * Creates a new Vertex object, using the given name.
 *
 * @param name - string used to identify this Vertex
 */
public Vertex(Type name) {
    this.name = name;
    this.adj = new LinkedList<>();

}

/**
 * @return the string used to identify this Vertex
 */
public Type getName() {
    return name;
}

/**
 * Adds a directed edge from this Vertex to another.
 *
 * @param otherVertex - the Vertex object that is the destination of the edge
 */
public void addEdge(Vertex<Type> otherVertex) {
    adj.add(new Edge<>(otherVertex));
    otherVertex.indegree++;
}

/**
 * @return an iterator for accessing the edges for which this Vertex is the source
 */
public Iterator<Edge<Type>> edges() {
    return adj.iterator();
}

/**
 * Generates and returns a textual representation of this Vertex.
 */
public String toString() {
    StringBuilder s = new StringBuilder("Vertex " + name + " adjacent to vertices ");
    for (Edge<Type> typeEdge : adj) s.append(typeEdge).append("  ");
    return s.toString();
}

}

错误原因分析 #

1. 图实例未共享：createGraph方法内部新建了局部Graph<Type>实例，和topologicalSort方法中遍历的vertices集合无关联，导致拓扑排序时vertices为空，直接返回空列表，对应“预期结果<5>实际为<0>”的问题。
2. 环检测逻辑错误：当前if (counter > output.size())的判断完全无效，拓扑排序中存在环时，处理的节点数counter会小于总节点数，正确判断应为counter != vertices.size()，否则无法触发预期的异常。
3. 泛型与成员变量缺失：topologicalSort方法未声明泛型，且vertices变量的来源未明确，存在类型安全问题；Vertex类的indegree未初始化，可能导致入度统计错误。
4. 异常信息不匹配：当前抛出的异常信息为"The size doesn't match."，与测试中出现的"No path found"不符，不符合预期。

修复方案 #

关键修复点 #

1. 共享图实例：将createGraph改为非静态方法，操作类成员变量的图实例，确保拓扑排序能访问到构建好的节点。
2. 修正环检测逻辑：当counter != vertices.size()时抛出异常，信息改为"No path found"。
3. 完善泛型与初始化：补全topologicalSort的泛型声明，初始化Vertex的indegree为0。
4. 优化方法返回值：将Vertex的setIndegree改为void返回值，符合常规 setter 设计。

修复后的完整代码 #

import java.util.*;

public class GraphUtility<Type> {
    private Graph<Type> graph;

    public GraphUtility() {
        this.graph = new Graph<>();
    }

    /**
     * 生成图中顶点的拓扑排序结果，图可能存在多个有效排序，任意一种均可。
     *
     * @param sources      边的起点列表
     * @param destinations 边的终点列表
     * @return 顶点的拓扑排序列表
     * @throws IllegalArgumentException 当图存在环或输入参数无效时抛出
     */
    public List<Type> topologicalSort(List<Type> sources, List<Type> destinations) throws IllegalArgumentException {
        createGraph(sources, destinations);
        Map<Type, Vertex<Type>> vertices = graph.getVertices();

        Queue<Vertex<Type>> doableTasks = new LinkedList<>();
        List<Type> output = new LinkedList<>();

        // 初始化入度为0的节点
        for (Vertex<Type> task : vertices.values()) {
            if (task.getIndegree() == 0) {
                doableTasks.add(task);
            }
        }

        int counter = 0;

        while (!doableTasks.isEmpty()) {
            Vertex<Type> task = doableTasks.remove();
            counter++;
            output.add(task.getName());

            for (Iterator<Edge<Type>> it = task.edges(); it.hasNext(); ) {
                Edge<Type> outEdge = it.next();
                Vertex<Type> neighbor = outEdge.getOtherVertex();

                neighbor.setIndegree(neighbor.getIndegree() - 1);
                if (neighbor.getIndegree() == 0) {
                    doableTasks.add(neighbor);
                }
            }
        }

        // 检测环：处理的节点数不等于总节点数，说明存在环
        if (counter != vertices.size()) {
            throw new IllegalArgumentException("No path found");
        }
        return output;
    }

    /**
     * 根据边的起点和终点列表构建图
     *
     * @param sources      边的起点列表
     * @param destinations 边的终点列表
     * @throws IllegalArgumentException 当起点和终点列表长度不一致时抛出
     */
    public void createGraph(List<Type> sources, List<Type> destinations) throws IllegalArgumentException {
        if (sources.size() != destinations.size()) {
            throw new IllegalArgumentException("Must have the same size");
        }

        for (int i = 0; i < sources.size(); i++) {
            Type sourceData = sources.get(i);
            Type destData = destinations.get(i);
            graph.addEdge(sourceData, destData);
        }
    }

    // 补充Graph类的实现
    private static class Graph<Type> {
        private Map<Type, Vertex<Type>> vertices = new HashMap<>();

        public void addEdge(Type sourceData, Type destData) {
            Vertex<Type> source = vertices.computeIfAbsent(sourceData, Vertex::new);
            Vertex<Type> dest = vertices.computeIfAbsent(destData, Vertex::new);
            source.addEdge(dest);
        }

        public Map<Type, Vertex<Type>> getVertices() {
            return vertices;
        }
    }

    private static class Vertex<Type> {
        private final Type name;
        private final LinkedList<Edge<Type>> adj;
        private int indegree;

        public Vertex(Type name) {
            this.name = name;
            this.adj = new LinkedList<>();
            this.indegree = 0; // 初始化入度为0
        }

        public Type getName() {
            return name;
        }

        public int getIndegree() {
            return indegree;
        }

        public void setIndegree(int newIndegree) {
            this.indegree = newIndegree;
        }

        public void addEdge(Vertex<Type> otherVertex) {
            adj.add(new Edge<>(otherVertex));
            otherVertex.indegree++;
        }

        public Iterator<Edge<Type>> edges() {
            return adj.iterator();
        }

        @Override
        public String toString() {
            StringBuilder s = new StringBuilder("Vertex " + name + " adjacent to vertices ");
            for (Edge<Type> edge : adj) {
                s.append(edge.getOtherVertex().getName()).append("  ");
            }
            return s.toString();
        }
    }

    private static class Edge<Type> {
        private final Vertex<Type> target;

        public Edge(Vertex<Type> target) {
            this.target = target;
        }

        public Vertex<Type> getOtherVertex() {
            return target;
        }
    }
}

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