python - 算法:类(class)顺序

Question

鉴于类(class)数量和先决条件，我必须返回学生可以参加类(class)的正确顺序，即如果学生没有完成先决条件，则不能参加类(class)。请参阅下面的示例输入和输出以进行解释

类(class)顺序

示例输入:
- 类(class)数量:4
- 先决条件列表:[[1,2],[3,2],[2,4]]//[i,j] 表示 i 是 j 的先决条件
输出:[1,3,2,4] 或 [3,1,2,4]

示例输入:
- 类(class)数量:2
- 先决条件列表:[[1,2],[2,1]]
输出:[]//由于循环依赖，没有可能的解决方案

这是我天真的解决方案:

class Solution:
    def __init__(self):
        self.order = []
        self.mapping = {}

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        for pre_req in prerequisites:
            if pre_req[1] not in self.mapping:
                self.mapping[pre_req[1]] = [pre_req[0]]
            else:
                self.mapping[pre_req[1]].append(pre_req[0])

        # for i in range(1, numCourses+1):
        #     if i not in self.mapping:
        #         self.order.append(i)

        j = 0
        # for key in self.mapping:
        #     i += 1
        #     if key not in self.order:
        #         self.helper(key, i)
        #     break
        for i in range(1, numCourses+1):
            if i in self.mapping:
                self.helper(i, j)



        return self.order

    def helper(self, key, i):
        if len(self.mapping[key]) == 0:
            if key not in self.order:
                self.order.append(key)

                for ki in self.mapping:
                    if key in self.mapping[ki]:
                        self.mapping[k].remove(value)
                self.mapping.pop(key, None)   
            return


        for k in self.mapping:
            for value in self.mapping[k]:    
                if value not in self.mapping:
                    if value not in self.order:
                        self.order.append(value)
                        for ki in self.mapping:
                            if value in self.mapping[ki]:
                                self.mapping[k].remove(value)
                    else:
                        self.mapping[k].remove(value)
                else:
                    self.helper(k, i+1)
                if len(self.mapping[key]) == 0:
                    if key not in self.order:
                        self.order.append(key)

                        for ki in self.mapping:
                            if key in self.mapping[ki]:
                                self.mapping[k].remove(value)



s = Solution()
prereq = [[1,2],[3,2],[2,4]]
courses = 4
res = s.canFinish(courses, prereq)
print(res)

• 我的代码适用于以下输入:
• 类(class)数量:4
• 先决条件列表:[[1,2],[3,2],[2,4]]
• 我的代码没有处理循环依赖
• 我的解决方案不是最优的
• 我想知道这个问题的正确最优解
• 在投反对票之前，请评论您需要我添加哪些额外信息

=============================更新============== ==================

• 它不处理循环依赖，因为在辅助函数中我只检查先决条件，即 mapping 字典中 key 的值，并且是先决条件，即值作为 mapping 字典中的不同键，然后我将其添加到 self.order 中，我递归地执行此操作
• 所以我不检查键和值以及相同的值是否是它自己的键的键。
  • 显然这不是最优的，因为我没有检查循环依赖
  • 我认为可以有更好的数据结构来解决这个问题
  • 字典的概念:mapping = {course1 : [prereq1, prereq2], course2: [prereq1, prereq3]}
  • 辅助函数检查 mapping 是否有 prereq1 作为键，然后它将 prereq1 的值添加到 self.order

Answer 1

这是 topological sorting 的经典用例.如果您将先决条件视为有向图，其中从先决条件到另一门类(class)有一条边，您可以简单地找到该图的拓扑排序，您将得到答案。当图表有循环时，拓扑排序没有定义，同样，你的类(class)不应该有循环，因为你永远无法参加这些类(class)。在 python 中，您可以通过简单的深度优先搜索跟踪您何时进入和退出节点来进行拓扑排序。当您退出节点时(在查看所有子节点之后)，您将该节点添加到列表的起始位置。例如:

from collections import defaultdict
graph = defaultdict(set)

def getCourses(prereq):
    for p in prereq:
        # build a simple graph structure: keys are node value is a set of children
        graph[p[1]]
        graph[p[0]].add(p[1])

    visited = set()  
    seen = set()
    courses = []

    def dfs(node): # depth-first search
        if node in visited: return
        if node in seen:
            raise ValueError("Error cycle in prerequisites")
        seen.add(node)
        for e in graph[node]:
            dfs(e) #recurse on children
        seen.remove(node)
        visited.add(node)
        courses.insert(0, node)


    for k in graph.keys():
        if k in visited:
            continue        
        try: dfs(k)
        except ValueError: # in case of cycle
            return []

    return courses

print(getCourses([[1,2],[3,2],[2,4]]))