在有向树的广度优先搜索中跟踪深度
Tracking depth in a breadth first search of a directed tree
我试图找到根和正在遍历的节点的深度之间的距离,例如,如果我有以下表示树的邻接列表 { 1: [2, 3], 2: [4], 3: [5]}
关联列表,如将创建以下 [0, 1, 1, 2, 2]
表示每个节点的级别。
我有以下代码,但看不到我要在何处添加计数功能等,理想情况下,这也可以处理交叉和背面边缘
def bfs(graph, root):
seen, queue = set([root]), collections.deque([root])
visit_order = []
while queue:
vertex = queue.popleft()
visit_order.append(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
print(visit_order)
您可以将节点及其级别作为元组进行排队,而不是仅对节点进行排队,并且当您对节点进行排队时,它总是与当前级别加一相结合,因此当您将节点出列并追加该节点时到 visit_order
您还可以从元组中获得节点的级别:
import collections
def bfs(graph, root):
seen, queue = {root}, collections.deque([(root, 0)])
visit_order = []
levels = []
while queue:
vertex, level = queue.popleft()
visit_order.append(vertex)
levels.append(level)
for node in graph.get(vertex, []):
if node not in seen:
seen.add(node)
queue.append((node, level + 1))
print(visit_order)
print(levels)
这样:
bfs({ 1: [2, 3], 2: [4], 3: [5]}, 1)
会输出:
[1, 2, 3, 4, 5]
[0, 1, 1, 2, 2]
您可以使用字典来跟踪当前深度:
from collections import deque
d = {1: [2, 3], 2: [4], 3: [5]}
def bfs(graph, root = 1):
queue, seen, depths = deque([root]), [], {root:0}
while queue:
val = queue.popleft()
depths.update({i:depths[val] +1 for i in graph.get(val, [])})
seen.append(val)
queue.extend([i for i in graph.get(val, []) if i not in seen])
yield seen, depths
[(_all, _depths)] = bfs(d)
print([_depths[i] for i in _all])
输出:
[0, 1, 1, 2, 2]
但是,当使用 class
时,逻辑更简单,因为可以应用深度优先遍历:
class Tree:
def __init__(self, _start):
self.__dict__ = {'head':_start, 'data':[Tree(i) for i in d.get(_start, [])]}
def __contains__(self, _val):
if self.head != _val and not self.data:
return False
return True if self.head == _val else any(_val in i for i in self.data)
def get_depth(self, _val):
if self.head == _val:
return 0
return 1+[i for i in self.data if _val in i][0].get_depth(_val)
t = Tree(1)
print([t.get_depth(i) for i in set([i for a, b in d.items() for i in [a, *b]])])
输出:
[0, 1, 1, 2, 2]
我试图找到根和正在遍历的节点的深度之间的距离,例如,如果我有以下表示树的邻接列表 { 1: [2, 3], 2: [4], 3: [5]}
关联列表,如将创建以下 [0, 1, 1, 2, 2]
表示每个节点的级别。
我有以下代码,但看不到我要在何处添加计数功能等,理想情况下,这也可以处理交叉和背面边缘
def bfs(graph, root):
seen, queue = set([root]), collections.deque([root])
visit_order = []
while queue:
vertex = queue.popleft()
visit_order.append(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
print(visit_order)
您可以将节点及其级别作为元组进行排队,而不是仅对节点进行排队,并且当您对节点进行排队时,它总是与当前级别加一相结合,因此当您将节点出列并追加该节点时到 visit_order
您还可以从元组中获得节点的级别:
import collections
def bfs(graph, root):
seen, queue = {root}, collections.deque([(root, 0)])
visit_order = []
levels = []
while queue:
vertex, level = queue.popleft()
visit_order.append(vertex)
levels.append(level)
for node in graph.get(vertex, []):
if node not in seen:
seen.add(node)
queue.append((node, level + 1))
print(visit_order)
print(levels)
这样:
bfs({ 1: [2, 3], 2: [4], 3: [5]}, 1)
会输出:
[1, 2, 3, 4, 5]
[0, 1, 1, 2, 2]
您可以使用字典来跟踪当前深度:
from collections import deque
d = {1: [2, 3], 2: [4], 3: [5]}
def bfs(graph, root = 1):
queue, seen, depths = deque([root]), [], {root:0}
while queue:
val = queue.popleft()
depths.update({i:depths[val] +1 for i in graph.get(val, [])})
seen.append(val)
queue.extend([i for i in graph.get(val, []) if i not in seen])
yield seen, depths
[(_all, _depths)] = bfs(d)
print([_depths[i] for i in _all])
输出:
[0, 1, 1, 2, 2]
但是,当使用 class
时,逻辑更简单,因为可以应用深度优先遍历:
class Tree:
def __init__(self, _start):
self.__dict__ = {'head':_start, 'data':[Tree(i) for i in d.get(_start, [])]}
def __contains__(self, _val):
if self.head != _val and not self.data:
return False
return True if self.head == _val else any(_val in i for i in self.data)
def get_depth(self, _val):
if self.head == _val:
return 0
return 1+[i for i in self.data if _val in i][0].get_depth(_val)
t = Tree(1)
print([t.get_depth(i) for i in set([i for a, b in d.items() for i in [a, *b]])])
输出:
[0, 1, 1, 2, 2]