怎么用leetcode找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊

這篇文章主要介紹“怎么用leetcode找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊”，在日常操作中，相信很多人在怎么用leetcode找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么用leetcode找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

一、題目內(nèi)容

給你一個(gè) n 個(gè)點(diǎn)的帶權(quán)無向連通圖，節(jié)點(diǎn)編號為 0 到 n-1 ，同時(shí)還有一個(gè)數(shù)組 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 節(jié)點(diǎn)之間有一條帶權(quán)無向邊。最小生成樹 (MST) 是給定圖中邊的一個(gè)子集，它連接了所有節(jié)點(diǎn)且沒有環(huán)，而且這些邊的權(quán)值和最小。

請你找到給定圖中最小生成樹的所有關(guān)鍵邊和偽關(guān)鍵邊。如果從圖中刪去某條邊，會(huì)導(dǎo)致最小生成樹的權(quán)值和增加，那么我們就說它是一條關(guān)鍵邊。偽關(guān)鍵邊則是可能會(huì)出現(xiàn)在某些最小生成樹中但不會(huì)出現(xiàn)在所有最小生成樹中的邊。

請注意，你可以分別以任意順序返回關(guān)鍵邊的下標(biāo)和偽關(guān)鍵邊的下標(biāo)。

示例 1：

輸入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
輸出：[[0,1],[2,3,4,5]]
解釋：上圖描述了給定圖。
下圖是所有的最小生成樹。

注意到第 0 條邊和第 1 條邊出現(xiàn)在了所有最小生成樹中，所以它們是關(guān)鍵邊，我們將這兩個(gè)下標(biāo)作為輸出的第一個(gè)列表。
邊 2，3，4 和 5 是所有 MST 的剩余邊，所以它們是偽關(guān)鍵邊。我們將它們作為輸出的第二個(gè)列表。

示例 2 ：

輸入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
輸出：[[],[0,1,2,3]]
解釋：可以觀察到 4 條邊都有相同的權(quán)值，任選它們中的 3 條可以形成一棵 MST 。所以 4 條邊都是偽關(guān)鍵邊。

提示：

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti <= 1000
所有 (fromi, toi) 數(shù)對都是互不相同的。

二、解題思路

難到爆炸??！并查集， DFS，最小生成樹算法，注意遍歷邊時(shí)權(quán)重要排序，具體的算法流程看代碼注釋。

三、代碼

from collections import defaultdict


class Solution:
    flag = True

    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list) -> list:
        f = list(range(n))

        def find(x):
            if x != f[x]:
                f[x] = find(f[x])
            return f[x]

        # weight存儲(chǔ) 權(quán)重和邊下標(biāo)
        weight = []
        for index, item in enumerate(edges):
            u, v, w = item
            weight.append((w, index))

        # 構(gòu)建u到v和v到u的關(guān)系（u是起始點(diǎn)，v是終止點(diǎn)）
        keyedges = defaultdict(list)

        # 關(guān)鍵邊集合
        keyedge = set()
        # 非關(guān)鍵邊集合
        non_keyedge = set()

        def dfs(u, v, fw, visited):
            # 起始點(diǎn)和終結(jié)點(diǎn)一樣，返回True
            if u == v:
                return True
            # 遍歷集合加入起始點(diǎn)u
            visited.add(u)
            # 查看u節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)tmp和后一個(gè)節(jié)點(diǎn)tmp
            for tmp, index in keyedges[u]:
                w = edges[index][2]  # 與前一個(gè)節(jié)點(diǎn)或后一個(gè)節(jié)點(diǎn)構(gòu)成的邊的權(quán)值
                if tmp not in visited and dfs(tmp, v, fw, visited):
                    if w == fw:  # 當(dāng)前邊的權(quán)重和上一次得到權(quán)重一樣，說明兩條邊都可以分別刪除掉
                        keyedge.discard(index)  # 不是關(guān)鍵邊，從關(guān)鍵邊集合中去除
                        non_keyedge.add(index)  # 非關(guān)鍵邊加入
                        self.flag = True
                    return True

        for w, index in sorted(weight):
            u, v, _ = edges[index]
            fu = find(u)
            fv = find(v)
            if fu != fv:
                f[fu] = find(fv)  # 將當(dāng)前fu節(jié)點(diǎn)的終止點(diǎn)變得和fv查找的節(jié)點(diǎn)一致
                keyedges[u].append((v, index))
                keyedges[v].append((u, index))
                keyedge.add(index)
            else:  # 終止節(jié)點(diǎn)一致， 例如[2, 3, 2], [0, 3, 2]， 3和3都是查到的節(jié)點(diǎn)
                visited = set()
                self.flag = False
                dfs(u, v, w, visited)
                if self.flag:
                    non_keyedge.add(index)

        return [list(keyedge), list(non_keyedge)]


if __name__ == '__main__':
    s = Solution()
    n = 5
    edges = [[0, 1, 1], [1, 2, 1], [2, 3, 2], [0, 3, 2], [0, 4, 3], [3, 4, 3], [1, 4, 6]]
    ans = s.findCriticalAndPseudoCriticalEdges(n, edges)
    print(ans)

到此，關(guān)于“怎么用leetcode找到最小生成樹里的關(guān)鍵邊和偽關(guān)鍵邊”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！