Обнаружение цикла в ориентированном графе с использованием очередей - PullRequest
0 голосов
/ 15 октября 2019

Проблема может быть найдена по адресу: https://leetcode.com/problems/course-schedule/

Необходимо вернуть значение true, если в графе существует цикл, в противном случае - false.

Я пытаюсь реализовать обнаружение цикла в ориентированном графе. но это не дает правильный вывод. Логика здесь заключается в том, что всякий раз, когда я вижу вершину с неопределенностью == 0, я добавляю ее в очередь и уменьшаю степень ее соседей на 1, пока очередь не станет пустой, и поддерживаю счет вершин с неопределенностью == 0. Вконец, если число == numCourses (см. проблему по leetcode), что означает отсутствие цикла.

Один из входов, для которых я получаю неправильный вывод: numCourses = 2, prerequisites = [[0, 1]]. Может кто-нибудь сказать, пожалуйста, что я делаю не так?


        if(prerequisites.length== 0) return true;

        int[] indegree= new int[numCourses];
        Map<Integer, List<Integer>> map= new HashMap();

        for(int[] pre: prerequisites){
            List<Integer> list= map.getOrDefault(pre[1], new ArrayList());           
            list.add(pre[0]);
            indegree[pre[0]]++;
            map.put(pre[1], list);
        }

        Queue<Integer> q= new LinkedList();
        int count= 0;

        for(int i= 0; i< indegree.length; i++){
            if(indegree[i]== 0){
                q.add(indegree[i]);
            }
        }

        while(!q.isEmpty()){
            int front= q.poll();
            if(indegree[front]== 0){
                count++;
            }                

            if(!map.containsKey(front))
                continue;

            for(int neighbor: map.get(front)){
                indegree[neighbor]--;

                if(indegree[neighbor]== 0)
                    q.add(neighbor);
            }
        }

        return count== numCourses;
    }
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...