給定一個圖，其根節點由一個Node物件定義：
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def __eq__(self, other) -> bool:
if isinstance(other, self.__class__):
return self.__repr__() == other.__repr__()
def __repr__(self):
return f"Node(val: {self.val}, neighbors: {self.neighbors})"
def __str__(self):
return self.__repr__()
Graph 類定義如下，它使用Node上面的類從鄰接表中構造自己
class Graph:
def __init__(self, adj_list=[]):
self.root = adj_list or self.make_graph(adj_list)
def __repr__(self):
return str(self.root)
def __str__(self):
return self.__repr__()
def __eq__(self, other):
if isinstance(other, self.__class__):
return other.root == self.root
return False
def make_graph(self, adj_list) -> Node:
# Ref: https://stackoverflow.com/a/72499884/16378872
nodes = [Node(i 1) for i in range(len(adj_list))]
for i, neighbors in enumerate(adj_list):
nodes[i].neighbors = [nodes[j-1] for j in neighbors]
return nodes[0]
例如鄰接表[[2,4],[1,3],[2,4],[1,3]]被轉換Graph為如下
graph = Graph([[2,4],[1,3],[2,4],[1,3]])
print(graph)
Node(val: 1, neighbors: [Node(val: 2, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [Node(val: 2, neighbors: [...]), Node(val: 4, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [...])])])]), Node(val: 4, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [Node(val: 2, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [...])]), Node(val: 4, neighbors: [...])])])])
現在，如果我有 2 個圖表：
graph1 = Graph([[2,4],[1,3],[2,4],[1,3]])
graph2 = Graph([[2,4],[1,3],[2,4],[1,3]])
print(graph1 == graph2)
True
Node.__repr__()我可以通過比較這兩個圖物件的回傳值來檢查它們的相等性graph1，graph2這基本上是通過比較兩個圖的根節點的相等性的__eq__()特殊方法來完成的，因此使用如上所述的特殊方法。Graph__repr__()Node
該__repr__方法將輸出中深度嵌套的鄰居截斷為[...]，但是內部深處可能存在一些不具有相等值的節點Node.val，因此使該方法的比較結果不可靠。
我擔心的是，是否有更好、更可靠的方法來進行此相等性測驗，而不僅僅是比較__repr__()圖的兩個根節點？
uj5u.com熱心網友回復：
您可以實作深度優先遍歷并按值和度數比較節點。將節點標記為已訪問以避免它們被第二次遍歷：
def __eq__(self, other) -> bool:
visited = set()
def dfs(a, b):
if a.val != b.val or len(a.neighbors) != len(b.neighbors):
return False
if a.val in visited:
return True
visited.add(a.val)
return all(dfs(*pair) for pair in zip(a.neighbors, b.neighbors))
return isinstance(other, self.__class__) and dfs(self, other)
此代碼假定節點的值唯一標識同一圖中的節點。
這也假設圖是連通的，否則與根斷開的組件將不會被比較。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/486739.html