Блог

Я учусь решать проблему топологической сортировки в leetcode

Всего вам нужно пройти n курсов, помеченных как от 0 до n-1 .

Некоторые курсы могут иметь предварительные требования, например, чтобы пройти курс 0, вы должны сначала пройти курс 1, который выражается в виде пары: [0,1]

Учитывая общее количество курсов и список пар предварительных условий, возможно ли для вас закончить все курсы?

Пример 1:

 Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
  

Пример 2:

 Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.
  

Примечание:

1. Входными предпосылками является граф, представленный списком ребер, а не матрицами смежности. Узнайте больше о том, как представляется граф.
2. Вы можете предположить, что во входных предпосылках нет повторяющихся ребер.

Я прочитал следующее решение toposort в области обсуждения

 class Solution5:
    def canFinish(self,numCourses, prerequirements):
    """
    :type numCourse: int
    :type prerequirements: List[List[int]]
    :rtype:bool
    """
    if not prerequirements: return True 
    count = []

    in_degrees = defaultdict(int)
    graph = defaultdict(list)

    for u, v in prerequirements:
        graph[v].append(u)
        in_degrees[u]  = 1 #Confused here

    queue = [u for u in graph if in_degrees[u]==0]

    while queue:
        s = queue.pop()
        count.append(s)
        for v in graph(s):
            in_degrees[v] -= 1
            if in_degrees[v] ==0:
                queue.append(v)
    #check there exist a circle
    for u in in_degrees:
        if in_degrees[u]:
            return False 
    return True 
  

Я в замешательстве по поводу in_degrees[u] = 1

 for u, v in prerequirements:
    graph[v].append(u)
    in_degrees[u]  = 1 #Confused here
  

для направленного ребра (u, v) , u ——> v , узел u имеет одну превосходящую степень, в то время как узел v имеет одну независимую степень.

Поэтому я думаю, in_degrees[u] = 1 следует изменить на in_degrees[v] = 1 , потому что если существует (u, v), то v имеет по крайней мере один входящий инцидент и один indegree

В степени: это применимо только для ориентированного графа. Это представляет количество ребер, входящих в вершину.

Тем не менее, первоначальное решение работает.

В чем проблема с моим пониманием?

Посмотрите на строку выше; graph[v].append(u) . Ребра фактически идут в обратном направлении к вашему предположению и формату ввода. Это связано с тем, что для топологической сортировки мы хотим, чтобы объекты без зависимостей / входящих ребер оказывались в начале результирующего порядка, поэтому мы направляем ребра в соответствии с интерпретацией «является требованием для», а не «требуется». Например. входная пара (0,1) означает, что 0 требует 1, поэтому на графике мы рисуем направленное ребро (1,0), так что 1 может предшествовать 0 в нашей сортировке. Таким образом, 0 получает степень от рассмотрения этой пары.