給定一個節點串列，例如，
[1,2,3,4,5,6,7,8,9],
以及表示連接兩個節點的無方向邊的元組串列，例如，
[(2,3), (2,7), (3,7), (4,3), (5,1), (5,6)],
我怎樣才能找到不相交的樹的數量？
樹是由至少一條邊連接的一組音符，或者是不與任何其他節點連接的孤立節點。
在我的示例中，有些3樹是：
{2,3,4,7}{1,5,6}{9}
我認為這是一個花園式演算法問題，所以這個問題很可能是重復的。但是我只是在網上找不到解決方案。也許我沒有使用正確的術語進行搜索。
uj5u.com熱心網友回復：
感謝@beaker 和@derpirscher。我在下面發布了一些鏈接并關閉了這個問題。
https://en.wikipedia.org/wiki/Component_(graph_theory)
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/discuss/516491/Java-Union-Find-DFS-BFS-Solutions-Complexity-Explain-Clean-code
uj5u.com熱心網友回復：
根據您的描述，不相交的樹不一定是樹。他們可以有周期。它們通常被稱為組件。
解決這個問題的方法之一是使用Disjoint Set的概念。
您的語言環境可能具有本機或作為庫的不相交集的實作，但這里是 Python 中的不相交集的實作：
# Implementation of Union-Find (Disjoint Set)
class Node:
def __init__(self):
self.parent = self
self.rank = 0
def find(self):
if self.parent.parent != self.parent:
self.parent = self.parent.find()
return self.parent
def union(self, other):
node = self.find()
other = other.find()
if node == other:
return True # was already in same set
if node.rank > other.rank:
node, other = other, node
node.parent = other
other.rank = max(other.rank, node.rank 1)
return False # was not in same set, but now is
所以以上是通用的，與您的圖形問題沒有特別的關系。現在要將它用于您的圖形，我們Node為每個圖形節點創建一個實體，并呼叫union以指示連接的節點屬于同一個圖形組件：
def count_components(nodeids, edges):
# Create dictionary of nodes, keyed by their IDs
nodes = {
nodeid: Node() for nodeid in nodeids
}
# All connected nodes belong to the same disjoined set:
for a, b in edges:
nodes[a].union(nodes[b])
# Count distinct roots to which each node links
return len(set(node.find() for node in nodes.values()))
我們可以為您的示例圖運行它，如下所示：
vertices = [1,2,3,4,5,6,7,8,9]
edges = [(2,3), (2,7), (3,7), (4,3), (5,1), (5,6)]
print(count_components(vertices, edges)) # 4
由于這些已識別的不相交集，這將列印 4：
{2,3,4,7}
{1,5,6}
{8}
{9}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/318657.html
上一篇：如何處理不同權限的端點呼叫測驗