需要帮助找到最少的学期

Question

我的作业问题呈现了一些课程，有多少相互依赖。例如，第一个测试 (courses,depedent on)：(1,3) (2,3) (4,1) (4,2) 我们确定有 5 门课程和 4 门课程相互依赖（那是为什么 5 不在列表中，它只是 0)

我通过拓扑搜索得知，以下是一个有效的解决方案： 1 3 2 4 0

然后我需要打印学习这些课程所需的学期数，由于它们之间的关系，我知道这是 3 个学期。我们先要上课程1和2才能上3，因为我们已经有1 2，我们可以上课程4。

所以我需要帮助找出一些执行此操作的代码。这就是我需要你们帮助的地方

我试图简单地计算连接的课程数，但失败了。我试图想出一些我可以做的事情，但实际上没有任何解决方案出现。

图表class:

public class Graph {

    int V;
    LinkedList<Integer> adjList[];

    public Graph(int vertex) {
        this.V = vertex;

        //We then define the num of vertexes in the adjlist
        adjList = new LinkedList[vertex];

        //Then create a new list for each vertex so we can create a link between the vertexes
        for (int i = 0; i < vertex; i++) {
            adjList[i] = new LinkedList<>();
        }
    }
    //Directed graph
    public void addEdge(int source, int destination) {
        //Add the edge from the source node to the destination node

        adjList[source].add(destination);
        adjList[destination].add(source);
    }

    //Method to print the graph if necessary
    public void printGraph(Graph graph) {
        for (int i = 0; i < graph.V; i++) {
            System.out.println("Adjacency list over vertex: " + i);
            System.out.print("head");

            for (Integer treeCrawler : graph.adjList[i]) {

                System.out.print("-> " + treeCrawler);
            }
            System.out.println("\n");
        }
    }

    public LinkedList<Integer>[] getAdjList() {
        return adjList;
    }
}

和拓扑排序class，我们用于问题的算法

public class TopologicalSort {

    int vertex;

    //This function helps the topological function recursively by marking the vertices and pushing them onto the stack
    public void topologicalHelper(int vertex, boolean marked[], Stack nodes, Graph graph) {

        List<Integer>[] list = graph.getAdjList();

        marked[vertex] = true;

        Iterator<Integer> iterator = list[vertex].iterator();
        while (iterator.hasNext()) {
            int temp = iterator.next();
            if (!marked[temp] && list[temp].size() != 0) {
                topologicalHelper(temp, marked, nodes, graph);
            }

        }
        nodes.add(vertex);
    }


    public TopologicalSort(Graph graph, int vertecies) {
        vertex = vertecies;
        Stack nodes = new Stack();
        boolean[] marked = new boolean[vertex];

        for (int i = 0; i < vertex; i++) {
            if (marked[i] == false) {
                topologicalHelper(i, marked, nodes, graph);
            }
        }
        while(!nodes.empty()) {
            System.out.print(nodes.pop() + " ");
        }
    }
}

结果应该是 3，但我在所有的解决方案想法中都没有产生这个数字，我需要一些帮助或提示。

哦，下面是控制台输出

Adjacency list over vertex: 0
head

Adjacency list over vertex: 1
head-> 3-> 4

Adjacency list over vertex: 2
head-> 3-> 4

Adjacency list over vertex: 3
head-> 1-> 2

Adjacency list over vertex: 4
head-> 1-> 2

1 3 2 4 0

Answer 1

依赖是有向的属性所以你应该使用有向图。填充图形后，您将得到一个断开连接的图形，其中包含一棵或多棵树。找出哪些节点是每棵树的根，并使用 DFS 获得每棵树的最大深度。假设每学期的课程数量没有限制，所有树的最大深度就是解决方案。

public class Graph {
int V;
ArrayList<Integer> adjList[];
boolean[] notRoot;
public Graph(int vertex) {
    this.V = vertex;
    adjList = new ArrayList[vertex];
    notRoot = new boolean[vertex];
    for (int i = 0; i < vertex; i++) {
        adjList[i] = new ArrayList<Integer>();
    }
}
public void addEdge(int a, int b) {
    //asuming b is dependent on a
    adjList[b].add(a);
    notRoot[a]=true;
}
int maxDepthDfs(int root){
    int depth=1;
    for(int i=0;i<adjList[root].size();i++){
        int child=adjList[root].get(i);
        depth=Math.max(maxDepthDfs(child)+1,depth);
    }
    return depth;
}
public int getSolution(){
    int ans=0;
    for(int i=0;i<V;i++){
        if(!notRoot[i])
            ans=Math.max(ans,maxDepthDfs(i));
    }
    return ans;
}
}

拓扑排序就是简单的DFS，将节点添加到堆栈中（先添加节点的所有子节点，然后添加根节点）。在 Kahn 的算法中，首先找到根元素（没有父节点的节点）并且仅调用该方法或那些节点。

int maxDepthDfs(int root){
//since we are only calling this function for root nodes we need not check if nodes were previously visited
int depth=1;
for(int i=0;i<adjList[root].size();i++){
    int child=adjList[root].get(i);
    depth=Math.max(maxDepthDfs(child)+1,depth);
}
s.push(root);
return depth;
}
public int getSolution(){
    s=new Stack<Integer>();
    int ans=0;
    for(int i=0;i<V;i++){
        if(!notRoot[i])
            ans=Math.max(ans,maxDepthDfs(i));
    }
    //stack s contains result of topological sort;
    return ans;
}

需要帮助找到最少的学期

Need help to find the least amount of semesters

java

topological-sort