算法题 -- 求最长路径

2,880 阅读2分钟

题干:

给定一张包含N个点、N-1条边的无向连通图,节点从1到N编号,每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点,那么总路程至少是多少?

输入描述:

第一行包含一个整数N,1≤N≤10^5。

接下来N-1行,每行包含两个整数X和Y,表示X号节点和Y号节点之间有一条边,1≤X,Y≤N。

输出描述:

输出总路程的最小值。

输入例子:

4

1 2

1 3

3 4

输出例子:

4

解题思路:

这道题用数学的角度考虑,就是一共有N个点,N-1条路径,其实每一条路径都会被走两遍除了最长的那条路经,这样才能实现最短的路程遍历所有节点。也就是 2*(N-1)-最长路径长度。 所以这道题的思路就变成了求最长路径的长度,用递归的方式,根据父节点找子节点,如果找得到子节点,长度加一,没找到就得到了该路径的最长距离,存入数组。最后在路径长度数组中找到最大值加入计算式输出即可。 JavaScript代码如下:

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let count = 0;
let N;
let paths = [];
let result = 0;
let results = [];
rl.on('line', (line) => {
    if(count === 0) {
        N = Number(line);
        count ++;
    } else if(count < N) {
        paths.push(line.replace(/\s/g, ""));
        // ['12', '13', '14'];
        if(count === N-1) {
            getChildNode('1');
            console.log(2*(N-1) - Math.max.apply(this,results));
        }
        count ++;
    } else {
        rl.close();
    }
})

function getChildNode(parentNode) {
    const child = paths.filter(path => path.charAt(0) === parentNode);
    if(child.length > 0) {
        result ++;
        for(i=0; i<child.length; i++) {
            getChildNode(child[i].charAt(1));
        }
    } else {
        results.push(result);
    }
}

经测试,自测方案全部通过,但代码通过率仅为20%,代码逻辑以及迭代方法有待优化,如果有更好的方法可以留言告诉我谢谢!