无向和无权树中的最长路径-在python中 [英] Longest path in a undirected and unweighted tree - in python
问题描述
我正在解决一个问题，我需要计算树的直径，我知道如何先使用2 bfs来计算最远的节点，然后使用从第一个bfs中找到的节点来进行第二bfs的计算。 / p>
但是我很难执行一个非常简单的步骤-从输入中创建邻接表（在python中为dict），我已经为此编写了代码，但没有整洁而不是最好的，有人可以说出如何有效地做到这一点
输入
输入文件的第一行包含一个整数N ---树中
个节点的数目（0---每行包含一对（u，v）表示在节点u和节点v之间存在
边（1 <= u，v< = N）。
示例：
8
1 2
1 3
2 4
2 5
3 7
4 6
7 8
我的代码是：
def makedic（m）：
d = {}
for i in range（m）：
o，p = map（int，raw_input（）。split（））
，如果o不在d中，p不在d中：
d [p] = []
d [o] = [p]
elif o不在d和p中d：
d [o] = []
d [p] .append（o）
elif p不在d和o中d：
d [p] = []
d [o] .append（p）
在d中的elif o：
d [o] .append（p）
＃d [p ] .ap pend（o）
d的d：
d [p] .append（o）
return d
这是我实施bfs的方式：
def bfs（g，s）：
父级= {s：无}
级别= {s：0}
前沿= [s]
ctr = 1
而前沿：
next = [] i在边境的
：j在g [i]中的
：如果j不在父母中，则
：
父母[j] = i
等级[j ] = ctr
next.append（j）
frontier = next
ctr + = 1
返回水平，父级
您的代码中有不必要的检查。对于每个 A-B 边缘，只需将 B 放入 A 的邻接列表中，将 A 放入 B 的邻接表：
d = {}
对于范围i ）：
u，v = map（int，raw_input（）。split（））
如果d中的u：
d [u] .append（v）
否则：
d [u] = [v]
如果v在d：
d [v] .append（u）
否则：
d [v] = [u]
根据这个问题，每个节点的索引在 1 和 N ，因此您可以使用此事实并在 dict 中预先填充一个空列表。这样，您不必检查键是否在 dict 中。还要使代码短一些：
N = input（）
d = {i：[] for i范围（1，N + 1）}
对于范围（N）中的i：
u，v = map（int，raw_input（）。split（））
d [u] .append （v）
d [v] .append（u）
I am solving a problem in which I need to calculate the diameter of the tree.I know how to calculate that using 2 bfs first to find the farthest node then do second bfs using the node we found from the first one.
But I am having difficulty to implement a very simple step - making a adjacency list (dict in case of python) from the input I have written a code to this but its not tidy and not the best can someone tell how to do this efficently
Input
The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).
Example:
8
1 2
1 3
2 4
2 5
3 7
4 6
7 8
My code is :
def makedic(m):
d = {}
for i in range(m):
o, p = map(int, raw_input().split())
if o not in d and p not in d:
d[p] = []
d[o] = [p]
elif o not in d and p in d:
d[o] = []
d[p].append(o)
elif p not in d and o in d:
d[p] = []
d[o].append(p)
elif o in d:
d[o].append(p)
# d[p].append(o)
elif p in d:
d[p].append(o)
return d
Here is how I implemented bfs:
def bfs(g,s):
parent={s:None}
level={s:0}
frontier=[s]
ctr=1
while frontier:
next=[]
for i in frontier:
for j in g[i]:
if j not in parent:
parent[j]=i
level[j]=ctr
next.append(j)
frontier=next
ctr+=1
return level,parent
There are unnecessary checks in your code. For each A - B edge you just have to put B in A's adjacency list and A in B's adjacency list:
d = {}
for i in range(m):
u,v = map(int, raw_input().split())
if u in d:
d[u].append(v)
else:
d[u] = [v]
if v in d:
d[v].append(u)
else:
d[v] = [u]
According to the question every node has an index between 1 and N so you can use this fact and pre-populate the dict with empty lists. This way you don't have to check whether a key is in the dict or not. Also make the code a little bit shorter:
N = input()
d = { i:[] for i in range(1, N+1) }
for i in range(N):
u,v = map(int, raw_input().split())
d[u].append(v)
d[v].append(u)
这篇关于无向和无权树中的最长路径-在python中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
