preface

在无向图中,如果从顶点vi到顶点vj有路径,则称vivj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,称该图为非连通图,则其中的极大连通子图称为连通分量,这里所谓的极大是指子图中包含的顶点个数极大。在有向图中,如果对于每一对顶点vi和vj,从vivj和从vjvi都有路径,则称该图为强连通图;否则,将其中的极大强连通子图称为强连通分量


算法笔记(并查集):https://zhuanlan.zhihu.com/p/93647900

322.重新安排行程(8.27)

给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。

说明:

  • 如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前
  • 所有的机场都用三个大写字母表示(机场代码)。
  • 假定所有机票至少存在一种合理的行程。
#map硬套不行啊,会在图里死循环。

#什么是欧拉路径?欧拉路径就是一条能够不重不漏地经过图上的**每一条边**的路径,
#即小学奥数中的一笔画问题。而若这条路径的起点和终点相同,则将这条路径称为欧拉回路。

#如何判断一个图是否有欧拉路径呢?显然,与一笔画问题相同,一个图有欧拉路径需要以下几个条件:

# 1. 首先,这是一个连通图
# 2. 若是无向图,则这个图的度数为奇数的点的个数必须是0或2;
#    若是有向图,则要么所有点的入度和出度相等,要么有且只有两个点的入度分别比出度大1和少1

#具有欧拉回路的无向图称为欧拉图。

#具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。


class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        def dfs(curr):
            while vec[curr]:
                #pop出最小值
                tmp= heapq.heappop(vec[curr])
                dfs(tmp)
            stack.append(curr)
        
        #一个{depart:[arrive...]}的字典
        vec=collections.defaultdict(list)

        for depart,arrive in tickets:
            vec[depart].append(arrive)

        #便于排序
        for key in vec:
            heapq.heapify(vec[key])
        #heapq是一个标准库模块,优先队列算法
        #heapify转换列表成为堆结构

        stack=list()
        dfs("JFK")
        return stack[::-1]

#dfs和逆序那块迷糊
  1. 由于题目中说必然存在一条有效路径(至少是半欧拉图),所以算法不需要回溯(既加入到结果集里的元素不需要删除)
  2. 整个图最多存在一个死胡同(出度和入度相差1),且这个死胡同一定是最后一个访问到的,否则无法完成一笔画。
  3. DFS的调用其实是一个拆边的过程(既每次调用删除一条边),一定是递归到这个死胡同(无边可拆)后递归函数开始返回。所以死胡同是第一个加入栈中的元素。
  4. 最后逆序的输出即可。

133.克隆图(8.12)

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

class Solution(object):
    def __init__(self):
        self.visited={} #新node字典
    def cloneGraph(self, node):
        if not node: return node
        if node in self.visited:
            return self.visited[node]

        clone_node=Node(node.val,[])
        self.visited[node]=clone_node

        clone_node.neighbors=[self.cloneGraph(n) for n in node.neighbors]

        return clone_node

# 对于一张图而言,它的深拷贝即构建一张与原图结构,值均一样的图,但是其中的节点不再是原来图节点的引用.
# 或者用copy.deepcopy

207.课程表(8.4)

你这个学期必须选修 numCourse 门课程,记为 0numCourse-1

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        relation=collections.defaultdict(list)
        indegree=[0]*numCourses   #入度值列表

        for info in prerequisites:
            relation[info[1]].append(info[0]) #基础:[进阶]关系字典
            indegree[info[0]]+=1
        
        #先建一个入度为0的队列
        q = collections.deque([c for c in range(numCourses) if indegree[c] ==0])
        visited = 0
        while q:
            visited += 1
            u = q.popleft()
            for i in relation[u]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    q.append(i)

        return visited == numCourses

小结:

  • 核心思想:以入度进行BFS
  • 入度:图中的一个节点,多少个节点指向它

唔,经典拓扑图的算法.


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录