图.md

图

1. dfs

def dfs(cur,graph,visited):
    '''
    cur:当前结点
    graph:图的邻接表(如果是邻接矩阵需要简单修改下代码)
    visited:用来记录已经访问过的结点
    '''
    if visited[cur]==1:
        return 访问过就不需要再访问了
    visited[cur]=1
    for i in graph[cur]: #访问这个结点连接的下一个结点，不停递归
        dfs(i,graph,visited)
    return 从cur开始的dfs遍历结束

2. bfs

from queue import Queue
def bfs(cur,graph,visited):
    '''
    cur:当前结点
    graph:图的邻接表(如果是邻接矩阵需要简单修改下代码)
    visited:用来记录已经访问过的结点
    '''
    if visited[cur]==1:
      return 访问过了
    que=Queue()
    que.put(cur)
    while not que.empty():
        tmp=que.get()
        visited[tmp]=1
        for i in graph[tmp]:
            if visited[i]!=1:
                que.put(i)
    return 从cur开始的bfs遍历结束

785.判断二分图
思路：通过染色并判断染色是否有冲突的方法来判断是否为二分图。

#dfs方法
class Solution:
 def dfs(self,cur,prev_color,graph,visited,union_find):
     if cur in visited: #如果遇到了遍历过的结点，要判断遍历过的结点的颜色是否和当前应该有的颜色冲突
         if union_find[cur]==prev_color:
             return False
         else:
             return True
     union_find[cur]=not prev_color
     visited.add(cur)
     return all([self.dfs(i,union_find[cur],graph,visited,union_find) for i in graph[cur]])
 def isBipartite(self, graph: List[List[int]]) -> bool:
     for i in range(len(graph)):
         visited=set()
         union_find=[None]*len(graph)
         if not self.dfs(i,True,graph,visited,union_find):
             return False
     return True
#bfs方法
from queue import Queue
class Solution:
 def bfs(self,cur,graph):
     que=Queue()
     que.put([cur,True]) #队列存储的是二元组列表[当前结点，该结点的父节点的染色]
     visited=set()
     visited.add(cur)
     union_find=[None]*len(graph)
     while not que.empty():
         tmp,prev_color=que.get()
         for i in graph[tmp]:
             if i in visited:
                 if union_find[i]==prev_color:
                     return False
             else:
                 visited.add(i)
                 union_find[i]=not prev_color
                 que.put([i,not prev_color])

     return True
 def isBipartite(self, graph: List[List[int]]) -> bool:
     for i in range(len(graph)):
         if not self.bfs(i,graph):
             return False
     return True

207.课程表
思路：由于只需要判断这个课程表是否能学完，不需要有具体的路径，相当于问题转化为判断所给课程表的图是否为有向无环图。dfs里判断一个dfs结点出发是否会出现这次dfs遍历中再次访问到该结点的情况。bfs则利用一个入度表，每次将入度为0的结点加入队列来实现拓扑排序。

# dfs
class Solution:
    def dfs(self,cur,graph,union_find):
        if union_find[cur]==1: return False
        if union_find[cur]==-1: return True
        union_find[cur]=1
        for i in graph[cur]:
            if not self.dfs(i,graph,union_find):
                return False
        union_find[cur]=-1
        return True
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph=[[] for _ in range(numCourses)]
        for cur,pre in prerequisites:
            graph[pre].append(cur)
        union_find=[0]*numCourses
        for i in range(numCourses):
            if not self.dfs(i,graph,union_find):
                return False
        return True
# bfs
from queue import Queue
class Solution:
    def bfs(self,degree,graph,num):
        que=Queue()
        for i in range(len(degree)):
            if degree[i]==0:
                que.put(i)
        while not que.empty():
            cur = que.get()
            num-=1
            for i in graph[cur]:
                degree[i]-=1
                if degree[i]==0:
                    que.put(i)
        return False if num>0 else True
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph=[[] for _ in range(numCourses)]
        degree=[0]*numCourses
        for cur,pre in prerequisites:
            graph[pre].append(cur)
            degree[cur]+=1
        return self.bfs(degree,graph,numCourses)

210.课程表II
思路：和207.课程表类似，只不过要找到学习路径。dfs寻找到的答案刚好是反过来的，所以将答案反转即可，而拓扑排序是正序寻找的，寻找结点的顺序就是学习的顺序。

# dfs
class Solution:
    def dfs(self,cur,graph,union_find,stack):
        if union_find[cur]==-1: return True
        if union_find[cur]==1: return False
        union_find[cur]=1
        for i in graph[cur]:
            if not self.dfs(i,graph,union_find,stack):
                return False
        union_find[cur]=-1
        stack.append(cur)
        return True
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph=[[] for _ in range(numCourses)]
        for cur,pre in prerequisites:
            graph[pre].append(cur)
        stack=[]
        union_find=[0]*numCourses
        for i in range(numCourses):
            if not self.dfs(i,graph,union_find,stack):
                return []
        return stack[::-1]
# bfs
from queue import Queue
class Solution:
    def bfs(self,degree,graph,num):
        result=[]
        que=Queue()
        for i in range(len(degree)):
            if degree[i]==0:
                que.put(i)
        while not que.empty():
            cur = que.get()
            result.append(cur)
            for i in graph[cur]:
                degree[i]-=1
                if degree[i]==0:
                    que.put(i)
        return result if len(result)==num else []
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph=[[] for _ in range(numCourses)]
        degree=[0]*numCourses
        for cur,pre in prerequisites:
            graph[pre].append(cur)
            degree[cur]+=1
        return self.bfs(degree,graph,numCourses)