首页 > 试题广场 >

图的遍历

[编程题]图的遍历
  • 热度指数：8275 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给定一张包含 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
算法知识视频讲解
添加回答
Java
谁在找工作头像 谁在找工作
提交结果：答案错误 运行时间：1047ms 占用内存：60980KB 使用语言：Java 用例通过率：93.33% 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static int max = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i=0; i<n-1; i++) {
            int key = in.nextInt();
            int val = in.nextInt();
            if (map.containsKey(key)) {
                List<Integer> list = map.get(key);
                list.add(val);
                map.put(key, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(val);
                map.put(key, list);
            }
        }
        dfs(map, 1, 0);

        System.out.print(2*(n-1) - max);  
    }

    private static void dfs(HashMap<Integer, List<Integer>> map, int key, int num) {
        if (!map.containsKey(key)) {
            max = Math.max(max, num);
            return;
        }
        num++;
        for (Integer i : map.get(key)) {
            dfs(map, i, num);
        }        
    }
}

发表于 2023-04-20 21:13:55 回复(0)
Java
w蒹葭头像 w蒹葭
为甚么超时？？ 
public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<LinkedList<Integer>> list = new LinkedList();
        for(int i = 0; i < n; i++){
            list.add(new LinkedList<Integer>());
        }
        int[] visited = new int[n];
        for(int i = 0; i < n-1; i++){
            int f = sc.nextInt()-1;
            int e = sc.nextInt()-1;
            list.get(f).add(e);
            list.get(e).add(f);
        }
        int max_path = -1;
        //BFS
        Deque<Integer> queue = new LinkedList();
        queue.offerLast(0);
        visited[0] = 1;
        while(queue.size() > 0){
            int nums = queue.size();
            while(nums>0){
                int node = queue.pollFirst();    
                for(int i = 0; i < list.get(node).size(); i++){
                    int j = list.get(node).get(i);
                    if(visited[j]==0){
                        visited[j] = 1;
                        queue.offerLast(j);
                    }
                }
                nums--;
            }
            max_path++;
        }
        System.out.println(2*(n-1)-max_path);
    }

发表于 2021-03-16 23:39:27 回复(0)
Java
何止hz头像 何止hz
递归实现深度优先搜索最终只能通过66.7%。
最后只能用广度优先搜索了，借助两个栈（不用栈也行，比如用队列，或者其他集合也可以）保存当前层节点和下一层节点，类似于求树的层数，其实一开始就想这么做，但还是习惯用dfs，没想到栈溢出。 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 20:05
 * @Description: 图的遍历--本题本质是求树的高度或者理解为从1出发的最长路径
 * @version: 1.0
 */
public class Main {
    static int len = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= N; i++)
            graph.put(i, new ArrayList<>());
        String[] s;
        int num[] = new int[2];
        for (int i = 0; i < N - 1; i++){
            s = br.readLine().split(" ");
            num[0] = Integer.parseInt(s[0]);
            num[1] = Integer.parseInt(s[1]);
            graph.get(num[0]).add(num[1]);
            graph.get(num[1]).add(num[0]);
        }
        boolean flag[] = new boolean[N+1];
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> temp;
        stack.push(1);
        flag[1] = true;
        while (!stack.isEmpty()){
            temp = new Stack<>();
            while (!stack.isEmpty()){
                Integer pop = stack.pop();
                for (int son: graph.get(pop))
                    if (!flag[son]){
                        temp.push(son);
                        flag[son]=true;
                    }
            }
            if (!temp.isEmpty())
                len++;
            stack = temp;
        }
        System.out.println(2*(N-1) - len);
    }
}


编辑于 2020-05-10 22:21:23 回复(1)
Java
mignnan头像 mignnan
您的代码已保存
请检查是否存在数组越界等非法访问情况
case通过率为60.00%
import java.util.*;
public class Main {
    private static int m = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<List<Integer>> children = new ArrayList<>(N);
        for(int i = 0; i < N; i++) {
            children.add(new LinkedList<>());
        }
        while(sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            children.get(a-1).add(b-1);
            children.get(b-1).add(a-1);
        }
        boolean[] v = new boolean[N];
        v[0] = true;
        int count = 0;
        dfs(count, 0, v, children);
        System.out.println(2*(N-1) - m);
    }
 
    private static void dfs(int count, int index, boolean[] v, List<List<Integer>> children) {
        if(index<0 || index>=children.size())
            return;
        List<Integer> list = children.get(index);
        for(int i=0; i<list.size(); i++) {
            if(v[list.get(i)]){
                m = Math.max(m, count);
            } else {
                v[list.get(i)] = true;
                count++;
                dfs(count, list.get(i),v,children);
                
                v[list.get(i)] = false;
                count--;
            }
            
        }
    }
}

发表于 2019-09-11 15:45:01 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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