首页 > 试题广场 >

图的遍历

[编程题]图的遍历
  • 热度指数:8258 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给定一张包含 个点、 N-1 条边的无向连通图,节点从 到 编号,每条边的长度均为 。假设你从 号节点出发并打算遍历所有节点,那么总路程至少是多少?

数据范围:

输入描述:
第一行包含一个整数N。

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


输出描述:
输出总路程的最小值。
示例1

输入

4
1 2
1 3
3 4

输出

4
示例2

输入

2
1 2

输出

1
头像 laglangyue
发表于 2020-06-21 21:42:03
开始写深度优先遍历一步步走,走一步+1,只能过40%,因为可能不是最长的最后走完看了大佬说 2*(n-1)-最长,然后开始写了一个广搜。 import java.util.*; public class Main { public static void main(String[] arg 展开全文
头像 小Cen
发表于 2023-04-12 08:43:18
这是一到技巧题, 核心思想就是 从1出发,只有最长路径才不会被重复走两次, 大家可以在纸上模拟几个场景就知道。那么就是 2(总边数)- 最长路径的边数。 边数为 n-1, n为顶点数, 最后公式演变为 2(n-1)-最长路径边数。所以现在的首要问题是找最长路径, 采用递归方式找,可以用 visite 展开全文
头像 牛客728825809号
发表于 2023-05-23 12:23:55
#include <iostream> #include <cstring> using namespace std; const int N = 1e5 + 10; int h[N], e[2 * N], ne[2 * N], idx, n; int d[N]; int 展开全文
头像 17c89
发表于 2024-01-19 10:45:41
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { private static HashS 展开全文
头像 秦时明月2022
发表于 2022-08-19 11:23:41
解题思路 1.除了最长的路径,所有的路径均需要走两遍,使用转化思想,将问题转化为两遍路径(2 * (n - 1))-最长路径(step)即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n 展开全文