首页 > 试题广场 >

图的遍历

[编程题]图的遍历
  • 热度指数：8481 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一张包含 N 个点、 N-1 条边的无向连通图，节点从 1 到 N 编号，每条边的长度均为 1 。假设你从 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 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 小Cen
发表于 2023-04-12 08:43:18
这是一到技巧题， 核心思想就是 从1出发，只有最长路径才不会被重复走两次， 大家可以在纸上模拟几个场景就知道。那么就是 2（总边数）- 最长路径的边数。 边数为 n-1, n为顶点数， 最后公式演变为 2（n-1）-最长路径边数。所以现在的首要问题是找最长路径， 采用递归方式找，可以用 visite 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Tiamonia
发表于 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 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hejuzs
发表于 2025-04-14 21:46:22
BFS搜索解法： import sys from typing import List, Dict from collections import deque # 添加导入 sys.setrecursionlimit(1 << 25) class State: def __ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 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 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 秦时明月2022
发表于 2022-08-19 11:23:41
解题思路 1.除了最长的路径,所有的路径均需要走两遍,使用转化思想,将问题转化为两遍路径(2 * (n - 1))-最长路径(step)即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 重生之我要当分子
发表于 2024-12-29 16:57:30
解题思路 这是一个无向图遍历问题： 从 号节点出发，需要遍历所有节点 每条边长度为 需要找到最短的遍历路径 关键发现： 对于叶子节点，必须走两次（来回） 对于非叶子节点，只需要走一次就能到达其他节点 最小路程 = * (边数) - (最远叶子节点的深度) 代码 c++ jav 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 树 测试工程师 图 PHP工程师 递归 贪心 美团 2019 Java工程师
来自：美团2019年秋招部分...
上传者：小小
难度：
29条回答 16216浏览

热门推荐

通过挑战的用户

查看代码

相关试题

图的遍历

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号