python中无向无权树的最长路径

Question

我正在解决一个需要计算树的直径的问题。我知道如何计算，首先使用2个bfs找到最远的节点，然后使用我们从第一个节点找到的节点进行第二个bfs。

但是我很难实现一个非常简单的步骤-从输入中创建邻接表(python的字典)，我已经写了一个代码，但它不整洁，也不是最好的，有人能告诉如何有效地做到这一点吗

输入

输入文件的第一行包含一个整数N——number of树中的节点(0 <= 10000)。接下来N-1条线包含N-1条边每一行包含一对(u, v)表示有一个节点u和节点v之间的边(1 <= u, v <= N)

:

8

1 23

1

2

5

7

6

7 8

我的代码是:

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

我是这样实现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

Answer 1

代码中有不必要的检查。对于每个A - B边，只需将B放在A的邻接表中，并将A放在B的邻接表中:

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]   

根据问题，每个节点在1和N之间有一个索引，因此您可以使用这一事实并用空列表预填充dict。这样，您就不必检查密钥是否在dict中。同时让代码更短一点:

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)

Answer 2

在makedic in first elif条件中使用0而不是o。对无向图也做了修正

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] = [o]
             d[o] = [p]
        elif o not in d and p in d:
             d[o] = [p]
             d[p].append(o)
        elif p not in d and o in d:
            d[p] = [o]
            d[o].append(p)
        elif o in d:
            d[o].append(p)
            d[p].append(o)
    return d