TA貢獻1883條經驗 獲得超3個贊
#!/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
舉報