我要招人

去企业版

首页 > 试题广场 >

图的遍历

[编程题]图的遍历

热度指数：8586 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $1 \le n \le 10^5 \$

输入描述:

第一行包含一个整数N。

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

输出描述:

输出总路程的最小值。

示例1

输入

输出

示例2

输入

2
1 2

输出

算法知识视频讲解

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蒹葭

为甚么超时？？

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

递归实现深度优先搜索最终只能通过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

您的代码已保存
请检查是否存在数组越界等非法访问情况
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条回答 193收藏 17721浏览

通过挑战的用户

查看代码

GeekExp...

2023-02-20 20:51:18
One Peach

2023-01-09 20:35:50
FionaBYQNL

2022-12-06 17:28:49
brbrbr

2022-11-27 21:33:07
Spectre_

2022-10-16 19:24:48

图的遍历

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题