美团2018.9.6笔试图的遍历

刺骨的言语ヽ痛彻心扉 2022-05-14 11:43 118阅读 0赞

# 题目描述 #

给定N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1节点出发并打算遍历所有节点，那么总路程至少是多少？  
**输入：**  
第一行包含一个整数N，1≤N≤ 1 0 5 10^5 105  
接下来N-1行，每行包含两个整数X和Y，表示X号节点和Y号节点之间有一条边，1≤X,Y≤N  
**输出：**  
输出总路程的最小值  
**样例输入：**  
4  
1 2  
1 3  
3 4  
**样例输出：**  
4  
**提示：**  
按1->2->1->3->4的路线遍历所有节点，总路程为4

# 思路 #

首先看到程序总是从1开始遍历，可以想到这个1其实就是树的根节点，本题本质上一棵**树的深度遍历**问题。  
看到N个节点，N-1边，而且还是连通图，所以可以确定这个图，实际上是一颗**生成树**。同时，因为是树，所以肯定没有环。  
以具体例子分析：  
样例输入的图是这样的：  
![这里写图片描述][70]  
从1出发遍历，找到深度最深的那条路线，那么这条路线上的边只会走一次，而其他边则都会走两遍。**之所以要找到深度最深的那条路线，因为这样就可以让走两遍的边的数量最小。**  
所以，红线就是代表深度最深的那条路线，这条路线只会走一次；而黑线的路线，就会走两遍。

对于更复杂的图也是如此（本文代码用的是这个图）：  
![这里写图片描述][70 1]

**重新整理思路**：  
1.输入的数据是图的数据，而我们需要将其改成树的数据。所以，从根节点1开始深度遍历，用数据结构记录下来树的结构和树各节点的深度。  
2.找出深度最深的那条路线，那么这条路线上的边乘1，加上其余边乘2，就是结果。（deep数组记录各节点深度，deep数组中的最大值就是最大深度）  
3.假设这条路线的长度为m（最大深度），那么其他边的数量为N-1-m

# 代码 #

from collections import defaultdict
    #提交代码时，取消以下注释
    ##n = eval(input())
    ##edge = []
    ##for i in range(n-1):
    ## a,b = map(int,input().split())
    ## edge.append([a,b])
    
    #提交代码时，删除以下代码
    n =7
    edge = [[1,2],[2,3],[2,4],[3,6],[6,7],[3,5]]
    
    d =defaultdict(list)#邻接表
    for i in edge:
        #无向图添加两条边
        d[i[0]].append(i[1])
        d[i[1]].append(i[0])
    #建立好了邻接表
    #深度遍历
    
    visited = [False]*(n+1)#使用索引从1开始
    
    deep = [0]*(n+1)#记录每个节点的深度
    parent = [-1]*(n+1)#记录每个节点的父节点
    
    def recursion(d,n,tempdeep):
        tempdeep += 1
        visited[n] = True
        if d[n] == []:#已经为空了，就回溯
            return 
        for i in d[n]:
            if (visited[i] == False):
                deep[i] = tempdeep
                parent[i] = n
                recursion(d,i,tempdeep)
    recursion(d,1,0)
    
    #找到最大深度的路线的长度，即路线上有多少条边
    maxdeep = max(deep)
    print( maxdeep + (n-1-maxdeep)*2 )

运行结果为8  
解析：  
parent记录下来了树的结构，但此代码中没有用处。

有一种更笨的方法来获得最深路线长度（大家可以无视，只是想看下这个递归怎么写）：

#找出深度最大那个节点的索引
    maxdeepindex = deep.index(max(deep))
    #得到最深节点到根节点的路线的长度
    def findroot(parent,temp):
        if(temp == 1):
            return 0
        return 1+findroot(parent,parent[temp])
    print(findroot(parent,maxdeepindex))

运行结果为4，即为最深深度。

2019.8.24代码调整（修改递归代码，使之更简洁易懂）：

from collections import defaultdict
    #提交代码时，取消以下注释
    n = eval(input())
    edge = []
    for i in range(n-1):
        a,b = map(int,input().split())
        edge.append([a,b])
    
    d =defaultdict(list)#邻接表
    for i in edge:
        #无向图添加两条边
        d[i[0]].append(i[1])
        d[i[1]].append(i[0])
    #建立好了邻接表
    #深度遍历
    
    visited = [False]*(n+1)#使用索引从1开始
    
    deep = [0]*(n+1)#记录每个节点的深度
    
    def recursion(d,n,tempdeep):
        deep[n] = tempdeep
        visited[n] = True
        if d[n] == []:#已经为空了，就回溯
            return 
        for i in d[n]:
            if (visited[i] == False):
                recursion(d,i,tempdeep+1)
    recursion(d,1,0)
    
    #找到最大深度的路线的长度，即路线上有多少条边
    maxdeep = max(deep)
    print( maxdeep + (n-1-maxdeep)*2 )

但牛客还是报错（66.7%，具体看评论），很恶心的是牛客网不提供出错的输入，和期望的输出。思路是对的，希望有明白的盆友能指点一二。

[70]: /images/20220514/716fa46bbecc4e3ea2b0e66a1a54559c.png
[70 1]: /images/20220514/cb4c0e774d3a46238c20cb8bb550281b.png