BFS(Topological Sort) Python solution with comments


  • 1
    R
    class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        # prerequisites graph, course as v, prers as e
        # use dict for prers as convenience
        prer_graph = {course:{} for course in xrange(numCourses)}
        counts = 0
        finished_course_list = []
        
        # construct graph
        for course, prer in prerequisites:
            prer_graph[course][prer] = True
        
        # get no incoming edge v
        for course in xrange(numCourses):
            if not prer_graph[course]:
                finished_course_list.append(course)
        
        # remove edge from graph, and find other no incoming edge v
        while finished_course_list:
            counts += 1
            finished_course = finished_course_list.pop()
            for course, prers in prer_graph.iteritems():
                if finished_course in prers:
                    del prers[finished_course]
                    if len(prers) == 0:
                        finished_course_list.append(course)
                        
        return counts == numCourses
    

    Implementation of http://en.wikipedia.org/wiki/Topological_sorting


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.