networkx有向图或二叉树的节点高度,Python

x33g5p2x  于2021-12-30 转载在 Python  
字(0.5k)|赞(0)|评价(0)|浏览(389)

原理:BFS广度搜索遍历后,从最后一个节点逆行向上,直到出发源点,没往上爬一层,高度加1。

  1. import networkx as nx
  2. def get_node_height(G, number):
  3. height = 0
  4. successors = G.successors(number)
  5. if len(list(successors)) == 0:
  6. height = 0
  7. # print(number, '高度', height)
  8. return height
  9. bfs = nx.bfs_tree(G, number)
  10. node_v = list(bfs).pop()
  11. # print(number, '最远的点', node_v)
  12. while True:
  13. predecessors = G.predecessors(node_v)
  14. ps = list(predecessors)
  15. # print(node_v, '前继', ps)
  16. if len(ps) == 0:
  17. break
  18. else:
  19. p_node_v = ps.pop()
  20. height = height + 1
  21. if p_node_v == number:
  22. break
  23. else:
  24. node_v = p_node_v
  25. # print(number, '高度', height)
  26. return height

相关文章