流程图获取深度，求各位算法高手帮帮忙

Question

最近这个问题困扰我半天,我有以下json数据其中,prev_node代表上一个节点,next_node为下一节点.如果prev_node为Null,则代表当前为第一个节点.next_node为null为最后一个节点.根据数据得到以下流程图求当前深度最深的流程有哪些节点，和流程的有几个分支注:节点只能向下走

Answer 1

#!/usr/bin/python

# coding: utf-8

def build_graph(nodes=[]):

    graph = {}

    for node in nodes:

        if not node['prev_node']:      # root node

            if 'root' not in graph:

                graph['root'] = []

            graph['root'].append(node['next_node'])

        else:

            if node['prev_node'] not in graph:

                graph[node['prev_node']] = []

            if node['next_node']:

                graph[node['prev_node']].append(node['next_node'])

    return graph

def travel(node, graph={}):

    # print(node)

    if not graph[node]:

        return 1, [node]   # branch, node

    max_nodes = []

    max_branches = 0

    for i in graph[node]:

        branches, nodes = travel(i, graph)

        if len(nodes) > len(max_nodes):

            max_nodes = nodes

        max_branches += branches

    max_nodes.append(node)

    return max_branches, max_nodes

if __name__ == '__main__':

    nodes = [

        {"prev_node": "0000000000000005","next_node": "0000000000000006"},

        {"prev_node": "0000000000000006","next_node": "0000000000000007"},

        {"prev_node": "0000000000000006","next_node": "0000000000000008"},

        {"prev_node": "0000000000000008","next_node": "0000000000000012"},

        {"prev_node": "0000000000000009","next_node": "0000000000000010"},

        {"prev_node": "0000000000000010","next_node": "0000000000000011"},

        {"prev_node": "0000000000000014","next_node": "0000000000000015"},

        {"prev_node": "0000000000000015","next_node": "0000000000000016"},

        {"prev_node": "0000000000000016","next_node": "0000000000000017"},

        {"prev_node": "0000000000000018","next_node": "0000000000000019"},

        {"prev_node": "0000000000000020","next_node": "0000000000000021"},

        {"prev_node": "0000000000000019","next_node": "0000000000000020"},

        {"prev_node": "0000000000000012","next_node": "0000000000000022"},

        {"prev_node": "0000000000000022","next_node": "0000000000000023"},

        {"prev_node": "0000000000000023","next_node": "0000000000000009"},

        {"prev_node": "0000000000000011","next_node": "0000000000000024"},

        {"prev_node": "0000000000000024","next_node": "0000000000000014"},

        {"prev_node": "0000000000000017","next_node": "0000000000000025"},

        {"prev_node": "0000000000000025","next_node": "0000000000000018"},

        {"prev_node": "0000000000000007","next_node": "0000000000000021"},

        {"prev_node": None, "next_node": "0000000000000005"},

        {"prev_node": "0000000000000021", "next_node": None}

    ]

    graph = build_graph(nodes)

    branches, nodes = travel('root', graph)

    print("branch num: %d" % branches)

    print("max depth branch:")

    for i in nodes[::-1]:

        print(i)

branch num: 2

max depth branch:

root

0000000000000005

0000000000000006

0000000000000008

0000000000000012

0000000000000022

0000000000000023

0000000000000009

0000000000000010

0000000000000011

0000000000000024

0000000000000014

0000000000000015

0000000000000016

0000000000000017

0000000000000025

0000000000000018

0000000000000019

0000000000000020

0000000000000021