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

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

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

import networkx as nx

def get_node_height(G, number):
    height = 0
    successors = G.successors(number)
    if len(list(successors)) == 0:
        height = 0
        # print(number, '高度', height)
        return height

    bfs = nx.bfs_tree(G, number)
    node_v = list(bfs).pop()
    # print(number, '最远的点', node_v)
    while True:
        predecessors = G.predecessors(node_v)
        ps = list(predecessors)
        # print(node_v, '前继', ps)
        if len(ps) == 0:
            break
        else:
            p_node_v = ps.pop()
            height = height + 1
            if p_node_v == number:
                break
            else:
                node_v = p_node_v

    # print(number, '高度', height)
    return height

相关文章