获取给定距离的邻居 BFS 算法
Getting neighbours in given distance BFS algorithm
我必须编写一个函数,它将 return 一个 set
包含给定距离内源顶点的邻居。例如,对于示例图:
{0: [1, 3],
1: [2],
2: [],
3: [4],
4: [1, 5],
5: [],
6: [1]}
通过将此图传递给函数 + 为 0 的源顶点并传递距离 = 2,结果应为:{1,2,3,4}
.
我怎样才能做到这一点?
我对图论不是很精通,但下面的似乎得到了正确的结果。对于 2 的距离,它得到以下结果:
{1, 2, 3, 4}
import networkx as nx
def main():
distance = 2
source_node = 0
dict1 = {0: [1, 3],
1: [2],
2: [],
3: [4],
4: [1, 5],
5: [],
6: [1]}
g = nx.DiGraph()
# fill graph
for node, list1 in dict1.items():
for n in list1:
g.add_edge(node, n)
neighbors = []
M = [source_node]
for _ in range(distance):
M = find_neigbors(g,M)
neighbors.extend(M)
print(neighbors)
def find_neigbors(g, vertices):
p = []
for node in vertices:
p.extend(g.adj[node])
return p
main()
更新:维基百科有一个 Python 函数 here 实现了 BFS 算法。
更新:另见 BFS algorithm in Python
我必须编写一个函数,它将 return 一个 set
包含给定距离内源顶点的邻居。例如,对于示例图:
{0: [1, 3],
1: [2],
2: [],
3: [4],
4: [1, 5],
5: [],
6: [1]}
通过将此图传递给函数 + 为 0 的源顶点并传递距离 = 2,结果应为:{1,2,3,4}
.
我怎样才能做到这一点?
我对图论不是很精通,但下面的似乎得到了正确的结果。对于 2 的距离,它得到以下结果:
{1, 2, 3, 4}
import networkx as nx
def main():
distance = 2
source_node = 0
dict1 = {0: [1, 3],
1: [2],
2: [],
3: [4],
4: [1, 5],
5: [],
6: [1]}
g = nx.DiGraph()
# fill graph
for node, list1 in dict1.items():
for n in list1:
g.add_edge(node, n)
neighbors = []
M = [source_node]
for _ in range(distance):
M = find_neigbors(g,M)
neighbors.extend(M)
print(neighbors)
def find_neigbors(g, vertices):
p = []
for node in vertices:
p.extend(g.adj[node])
return p
main()
更新:维基百科有一个 Python 函数 here 实现了 BFS 算法。
更新:另见 BFS algorithm in Python