chapter10-graph-algorithm

[TOC]

图算法

二分图

1. 判断是否为二分图

Leetcode / 力扣

def isBipartite(graph) -> bool:

    #  you题意可知
    # 要成为二分图，就只能有一个环，如果有两个环就不能成为二分图了
    # 因此，只需要判断，在遍历图的过程中，一个数是否被遍历的两次
    # 如果被遍历了两次，说明有两个环，就不能够成二分图了
    # 考虑到如果图本来就不连续，意思为两个独立的图构成一个大图
    # 所以需要遍历每一个节点
    # 因此代码逻辑如下：
    def dfs():
        def isBipartite(curNode, curColor, colors, graph):
            # 判断当前节点颜色
            if colors[curNode] != -1:
                return colors[curNode] == curColor
            # 没有颜色，则开始染色
            colors[curNode] = curColor
            # 给当前点的邻接点着色
            for nextNode in graph[curNode]:
                if not isBipartite(nextNode, 1-curColor, colors, graph):
                    return False
            return True

        colors = [-1]*len(graph)
        for i in range(len(graph)): # 处理图不连续的情况
            if colors[i] == -1 and not isBipartite(i, 0, colors, graph):
                return False
        return True

    # 由上诉理解可知
    # 对于一个结点染为红色后，他的邻接点一定为蓝色，
    # 且他的邻接点的邻接点的染色为红色，一直贪婪下去
    # 符合这样规则的图才能够为二分图
    # 因此，可以使用栈去模拟深度搜索
    # 代码逻辑如下：

    def dy():
        color = {}
        # 遍历每一个节点，防止不连续图
        for node in range(len(graph)):
            if node not in color:
                stack = [node]
                color[node] = 0
                # 开始深度搜索
                while stack:
                    # 表示下一个邻接点
                    node = stack.pop()
                    print(graph[node])
                    # 遍历当前节点的下一个邻接点
                    for n in graph[node]:
                        if n not in color:
                            stack.append(n)
                            color[n] = color[node]^1
                        elif color[n] == color[node]:
                            return False
        return True
    return  dy()

graph = [[1,3], [0,2], [1,3], [0,2]]
# print(isBipartite(graph))

拓扑排序

1.课程安排的合法性

Leetcode / 力扣

def canFinish(numCourses, prerequisites):

    # 由题意得
    # 要先完成一门课程，那么一定要先完成前一门课程
    # 如果这两门构成一个环，也就是谁也完成不了谁，就一门也完成不了了
    # 所以本题就是判断所给课程中，构成一个图，里面是否有环
    # 如果没有环就能够完成，反之，亦然
    # 代码逻辑如下：

    def hasCycle(globalMarked, localMarked, graphic, curNode):
        if localMarked[curNode]:
            return True
        if globalMarked[curNode]:
            return False

        globalMarked[curNode] = True
        localMarked[curNode] = True
        # 遍历邻接点
        for nextNode in graphic[curNode]:
            if hasCycle(globalMarked, localMarked, graphic, nextNode):
                return True
        # 返回时候需要回溯，因为应访问过了
        localMarked[curNode] = False
        return False

    graphic = [[] for i in range(numCourses)]
    for pre in prerequisites:
        graphic[pre[0]].append(pre[1])
    print(graphic)

    globalMarked = [False]*numCourses
    localMarked = [False]*numCourses
    for i in range(numCourses):
        if hasCycle(globalMarked, localMarked, graphic, i):
            return False
    return True

# numCourses, prerequisites = 2, [[0, 1]]
# print(canFinish(numCourses, prerequisites ))

2. 课程安排的顺序

Leetcode / 力扣

def findOrder(  numCourses: int, prerequisites):

    # you题意可知
    # 在选修某些课程之前需要一些先修课程
    # 1. 课程之间构成一个图的形式
    # 2. 如果图中有环，那永远也完成不了全部课程
    # 3. 遍历图，需要采用拓扑排序，也就是没有出度只有入度的结点先输出
    # 4. 后续遍历能够满足当前输出要求
    #  因此逻辑代码如下：

    # 判断图中是否有环
    # 并且保存后续遍历后的返回值，存入栈中(先返回的一定是叶节点)
    def hasCycle(globalMarked, localMarked, graphic, curNode,stack):
        if localMarked[curNode]:
            return True
        if globalMarked[curNode]:
            return False

        globalMarked[curNode] = True
        localMarked[curNode] = True
        # 遍历邻接点
        for nextNode in graphic[curNode]:
            if hasCycle(globalMarked, localMarked, graphic, nextNode,stack):
                return True
        # 返回时候需要回溯，因为应访问过了
        localMarked[curNode] = False
        stack.append(curNode)
        return False

    # 把课程转为邻接表形式
    graphic = [ [ ] for i in range(numCourses) ]
    for node in prerequisites:
        graphic[ node[ 0 ] ].append(node[ 1 ])
    print(graphic)

    stack = []
    globalMarked = [False]*numCourses
    localMarked = [False]*numCourses
    for i in range(numCourses):
        if hasCycle(globalMarked, localMarked, graphic, i,stack):
            return []
    print(stack)
    return stack


numCourses, prerequisites = 4, [ [ 1, 0 ], [ 2, 0 ], [ 3, 1 ], [ 3, 2 ] ]
findOrder(numCourses, prerequisites)

并查集

1. 冗余连接

Leetcode / 力扣

# 建立并查集结构
# 就过两点之间有联系，那么这个两点一定指向连接的最大值，也就是有关联的祖祖
# 比如prerequisites = [[1,2], [1,3], [2,3]]: 1(3)->2(3)->3(3)
# 也就是说当前点，指向最终的祖祖，即：
# 1. 不同点有同一个祖祖，说明它们在一棵树上，反之
# 并查集优点：
# 1.树不管有多大，判断两个点是否在树上只需要小于三次，反正很小哈哈
# 本体为什么使用并查集：
# 1. 在插入另一个点prerequisites[2]过程中,
# 前面的结点已经构成了树，且已经满足了这两个点
# 说明如果在插入这两个点，已经构成了环，就是需要我们删除的冗余连接
# 因此代码逻辑如下：
class UF:
    def __init__(self, N):
        self.id = [i for i in range(N+1)]


    def union(self, u, v):
        uid = self.find(u)
        vid = self.find(v)

        if uid == vid:
            return
        for i in range(len(self.id)):
            if self.id[i] == uid:
                self.id[i] = vid

    def find(self, p):
        return self.id[p]



    def collect(self, u, v):
        return self.find(u) == self.find(v)

def findRedundantConnection( edges ) :
    uf = UF(len(edges))
    for  e in edges:
        u, v = e[0], e[1]
        if uf.collect(u, v):
            return e
        uf.union(u, v)
    return [-1, -1]



# 缩略版本
def findRedundantConnection1( edges ) :
    p = [ [ i ] for i in range(len(edges) + 1) ]  # 并查集初始化
    for x, y in edges:
        if p[ x ] is not p[ y ]:  # 如果两个集合地址不一样
            if len(p[ x ]) < len(p[ y ]):
                x, y = y, x
            p[ x ].extend(p[ y ])  # 合并集合
            for z in p[ y ]:
                p[ z ] = p[ x ]  # 修改元素集合标记的指针地址
        else:
            return [ x, y ]

edges = [[1,2], [1,3], [2,3]]
print(findRedundantConnection(edges = edges))
print(findRedundantConnection1(edges = edges))