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

问题描述

问 题

最近这个问题困扰我半天,我有以下json数据

[
    {"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": null,"next_node": "0000000000000005"},
    {"prev_node": "0000000000000021","next_node": null}
]

其中,prev_node代表上一个节点,next_node为下一节点.如果prev_node为Null,则代表当前为第一个节点.next_node为null为最后一个节点.根据数据得到以下流程图

求当前深度最深的流程有哪些节点，和流程的有几个分支

注:节点只能向下走

这个问题已被关闭，原因：问题已解决 - 问题已解决，且对他人无借鉴意义

解决方案

#!/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

这篇关于javascript - 流程图获取深度，求各位算法高手帮帮忙的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！