题解 | #反复横跳#

题意整理

给定一张带权无向图，图中任意两点间有且仅有一条路径。
求从任意点出发，访问完所有节点后，所经过边的权值和的最小值。

方法一（dfs）

1.解题思路

要想边权值最小，所走的路径中必定包含了最长（边权值最大）无重复节点的路径，只要求出这个路径权值和，用所有路径权值和的两倍减去最大路径权值和，即得到所经过边的权值和的最小值。

首先初始化邻接表，遍历点对集合Edge，计算所有边长度的两倍。
先从1号节点进入递归，通过递归找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权值和。
然后再从最远节点处继续进入递归体，寻找最大路径权值和。
找到之后，用所有边长度的两倍减去这个权值和。

由于测试数据较大，栈深度会溢出，通过自定义栈深度的方式可以避免。

动图展示：
图片说明

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 最短距离
     * @param n int整型 
     * @param Edge Point类一维数组 
     * @param val int整型一维数组 
     * @return long长整型
     */
    //邻接表
    List<List<int[]>> graph;
    //结果变量
    long res=0;
    //记录最远节点
    long far=0;
    //记录无重复最长路径
    long max=0;

    public long solve (int n, Point[] Edge, int[] val) {
        //初始化邻接表
        graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        //计算所有路径和的两倍，即res的值
        for(int i=0;i<Edge.length;i++){
            res+=2*val[i];
            graph.get(Edge[i].x-1).add(new int[]{Edge[i].y-1,val[i]});
            graph.get(Edge[i].y-1).add(new int[]{Edge[i].x-1,val[i]});
        }


        //从1号点开始递归
        try{
            Thread t=new Thread(null,()->{
                dfs(0,-1,0);
            },"自定义栈深度",1<<30);
            t.start();
            t.join();
        }
        catch(Exception e){}
        max=0;
        //找到最远点后，从当前点递归
        try{
            Thread t=new Thread(null,()->{
                dfs(far,-1,0);
            },"自定义栈深度",1<<30);
            t.start();
            t.join();
        }
        catch(Exception e){}
        return res-max;
    }

    //深度优先搜索
    private void dfs(long cur,long pre,long dist){
        //跟新当前最长路径以及最远点
        if(dist>max){
            max=dist;
            far=cur;
        }
        for(int[] sub:graph.get((int)cur)){
            //如果没有走回头路，则将子节点放入队列
            if(sub[0]!=(int)pre){
                dfs(sub[0],cur,dist+sub[1]);
            }
        }
    }

}

3.复杂度分析

时间复杂度：最坏情况下，递归栈的深度为n，所以时间复杂度是 $O(n)$ 。
空间复杂度：最坏情况下邻接表的大小为 $n^2$ ，所以空间复杂度为 $O(n^2)$ 。

方法二（bfs）

1.解题思路

首先初始化邻接表，遍历点对集合Edge，计算所有边长度的两倍。
将1号节点入队，找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权值和。如果没有走回头路，将所有可能的子节点入队。
找到最远节点后，继续将最远节点入队，找出最大权值和。
找到之后，用所有边长度的两倍减去这个权值和。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 最短距离
     * @param n int整型 
     * @param Edge Point类一维数组 
     * @param val int整型一维数组 
     * @return long长整型
     */
    //邻接表
    List<List<int[]>> graph;
    //结果变量
    long res=0;
    //记录最远节点
    long far=0;
    //记录无重复最长路径
    long max=0;

    public long solve (int n, Point[] Edge, int[] val) {
        //初始化邻接表
        graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0;i<Edge.length;i++){
            res+=2*val[i];
            graph.get(Edge[i].x-1).add(new int[]{Edge[i].y-1,val[i]});
            graph.get(Edge[i].y-1).add(new int[]{Edge[i].x-1,val[i]});
        }

        //初始化队列
        Queue<long[] > queue=new LinkedList<>();
        //从1号点开始找
        bfs(queue,0,-1,0);
        max=0;
        //找到最远点后，从当前点继续找
        bfs(queue,far,-1,0);
        return res-max;
    }

    //广度优先搜索
    private void bfs(Queue<long[] > queue,long cur,long pre,long dist){
        //加入起始节点到队列
        queue.offer(new long[]{cur,pre,dist});

        while(!queue.isEmpty()){
            //取出当前节点信息
            long[] node=queue.poll();
            cur=node[0];
            pre=node[1];
            dist=node[2];
            //如果大于max，则跟新最远距离以及最远节点
            if(dist>max){
                max=dist;
                far=cur;
            }
            for(int[] sub:graph.get((int)cur)){
                //如果没有走回头路，则将子节点放入队列
                if(sub[0]!=(int)pre){
                    queue.offer(new long[]{sub[0],cur,dist+sub[1]});
                }
            }
        }
    }

}

3.复杂度分析

时间复杂度：最坏情况下，需要将n个节点入队，所以时间复杂度是 $O(n)$ 。
空间复杂度：最坏情况下邻接表的大小为 $n^2$ ，所以空间复杂度为 $O(n^2)$ 。