Блог

В моей задаче с домашним заданием представлены некоторые курсы и сколько из них зависят друг от друга. Например, первый тест (курсы, зависящие от): (1,3) (2,3) (4,1) (4,2) и мы определяем, что существует 5 курсов и 4 зависят друг от друга (вот почему 5 нет в списке, это просто 0)

Я знаю из топологического поиска, что следующее является допустимым решением: 1 3 2 4 0

Затем мне нужно вывести количество семестров, необходимое для прохождения этих курсов, и я знаю, что это 3 семестра, из-за отношений между ними. Сначала нам нужно пройти курсы 1 и 2, чтобы пройти курс 3, и поскольку у нас уже есть 1-2, мы можем пройти курс 4.

Итак, мне нужна помощь в определении некоторого кода, который делает это. Вот где мне нужна ваша помощь, ребята

Я пытался просто посчитать подключенные курсы, но не получилось. Я пытался придумать что-нибудь, что я могу сделать, но буквально ничего не всплывает в качестве решения.

Класс graph:

 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;
    }
}
  

и класс топологической сортировки, алгоритм, который мы используем для решения задачи

 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] amp;amp; 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 
  

Зависимость — это направленное свойство, поэтому вы должны использовать ориентированный граф. После заполнения графика u в конечном итоге получит несвязанный график, в котором есть одно или несколько деревьев. Выясните, какие узлы являются корнями каждого дерева, и используйте 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 с добавлением узлов в стек (сначала добавляются все дочерние узлы узла, а затем добавляется root). В алгоритме Кана сначала найдены корневые элементы (узлы без родительских), и метод вызывается только для этих узлов.

 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;
}