首页 > 试题广场 > 图的遍历
[编程题]图的遍历

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


输入描述:
第一行包含一个整数N,1≤N≤10^5。

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


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

输入

4
1 2
1 3
3 4

输出

4
/*借用一下别人的代码,讲下思路: 其实就是每条边都会走两遍,一共有n-1条边,所以2*(n-1), 最后一条路径只需要走一次,
所以减去最后一条路径的长度。本质来说,就是求一个图的最长路径*/
#include <bits/stdc++.h>
usingnamespacestd;
constintN = 1e5+10;
vector<int> vec[N];
intans;
voiddfs(intx, intold, intw) {
    for(inti=0;i<vec[x].size();i++){
        if(vec[x][i]==old){
            continue;
        }
        dfs(vec[x][i],x,w+1);
    }
    ans = max(ans, w);
}
intmain() {
    intn;
    scanf("%d", &n);
    for(inti = 1; i < n; ++ i) {
        intx, y;
        scanf("%d%d", &x, &y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    ans = 0;
    dfs(1, -1, 0);
    printf("%d\n", (n-1)*2-ans);
    return0;
}

发表于 2019-05-09 12:06:28 回复(1)

由题意得:n个点,n-1条边组成得图是无环图,所以要遍历所有点,最少得走法是所有边走俩两边再减去图中得最长路径,所以本题可以理解为,用bfs求图得最长路径

from collections import defaultdict
d = defaultdict(list)
n = int(input())
for i in range(n-1):
    a,b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

visited = defaultdict(bool)
visited[1] = True
res = 0
stack = [1]
while len(stack) > 0:
    tmp = []
    while len(stack) > 0:
        t = stack.pop()
        for e in d[t]:
            if not visited[e]:
                visited[e] = True
                tmp.append(e)
    stack = tmp
    res += 1
print(2 * (n-1) - res + 1)
发表于 今天 16:29:01 回复(0)
我的理解是,首先这不是一个环,然后从1出发有好几条路径,所以要遍历所有的节点的话,假设有n条路径,n-1条路径都需要走来回两遍,所以最短路径就是最长的那条路径只走一边,其余的都走两遍。
发表于 2019-08-09 10:29:34 回复(0)
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    x, y = map(int, input().split(" "))
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
visited = [0 for _ in range(n)]
visited[0] = 1
# 从当前根节点开始到返回当前根节点的路程为2*(n-1),n为节点个数,即根节点的子节点个数的2倍
# 求树的深度
queue = [0]
depth = 0
while len(queue)>0:
    depth += 1
    size = len(queue)
    for _ in range(size):
        now = queue.pop(0)
        for j in edge[now]:
            if visited[j]==0:
                visited[j]=1
                queue.append(j)
print((n-1)*2-depth+1)

过了93.33%后超时了,还能怎么优化啊
发表于 2019-08-22 21:55:08 回复(2)
n=int(input())
graph={}
for i in range(1,n+1):
    graph[i]=[]
for _  in range(n-1):
    f=[int(x) for x in input().split()]
    graph[f[0]].append(f[1])
    graph[f[1]].append(f[0])
def dfs(x,old,w):
    global ans
    for i in range(len(graph[x])):
        if (graph[x][i]==old):
            continue
        dfs(graph[x][i],x,w+1)
    ans=max(ans,w)
    return ans
ans=0
m=dfs(1,-1,0)
print((n-1)*2-m)
通过了66.7%报数组越界,有大佬指点下的嘛!
发表于 2019-08-21 20:01:54 回复(2)
不知道为什么,通过率只有20%,报数组越界
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static class Vertex{
		public Integer value;
		public boolean visited;
		public Vertex(int i){
			this.value = i;
		}
		public int getValue(){
			return this.value;
		}
	}

	static int N ;// 数字个数
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		 N = sc.nextInt();
		 int[][] adjMat = new int[N][N];// 关系矩阵
		
		// 保存节点
		 Vertex[] arr = new Vertex[N];
		for(int i= 0 ; i< N; i++){arr[i]= new Vertex(i);}
		// 添加连线关系
		// 注意:只执行n-1次 ;   i<N-1  从0开始计数,共n-1次
		for(int i= 0 ; i< N-1; i++){
				int n1 = sc.nextInt();
				int n2 = sc.nextInt();
				addLine(adjMat,arr,n1,n2);
		}
		//for(int[] i:adjMat){System.out.println(Arrays.toString(i));}
		// 深度搜索(统计次数)
		int result = dpSerch(adjMat,arr);
		System.out.println(result);
	}
	
	
	private static int dpSerch(int[][] adjMat, Vertex[] arr) {
		int currentIndex=0;//当前元素指针
		Stack<Integer> stack = new Stack<Integer>();// 栈,存放元素
		stack.push(0);// 存入第一个元素下标
		arr[0].visited = true;//把第一个元素标记为已访问
		int sign = 0;// 标记,用来标记所有元素均找到的状态,(注意:都找到了但还需要把先入栈的元素弹出)
		int times = 0; // 标记-查找所有元素所需的最短路程
		
		out:while(!stack.isEmpty()){
			for(int i=currentIndex+1 ; i< N ; i++){
				// 有连续的点
				if(adjMat[currentIndex][i] == 1 && arr[i].visited == false){
					// 连续点,下标进栈
					stack.push(i);
					arr[i].visited = true;//标记为已访问
					//System.out.println("存入:"+arr[i].getValue()+" 下标: "+i);
					times++;
					//System.out.println("路程+1,现在为:"+times);
					currentIndex = i;
					continue out;
				}
			}
			// 查找完与当前点所有连续的点,弹出当前点
			int pop = stack.pop();
			//System.out.println("弹出:"+" "+arr[pop].getValue()+"  下标: "+pop);
			// 弹出点 == N,即表明点已经找完,但是后续会继续弹出先入栈的点,所以需要用标记
			// 注意:弹出的点是指针,与数组长度比较需要+1
			if(pop == N-1){
				//System.out.println("数组长度: "+N);
				sign = 1;}
			if(sign != 1){
				times++;
				//System.out.println("路程+1,现在为:"+times);
				}
			// 最后一次弹栈后,栈为空,直接peek()会报错,所以加上if语句
			if(!stack.isEmpty()){currentIndex = stack.peek();}
			
		}
		
		return times;
	}


	private static void addLine(int[][] adjMat,Vertex[] arr, int n1, int n2) {
		// TODO Auto-generated method stub
		int rowIndex =0;// 行下标
		int colIndex =0;// 列下标
		int i = 0;
		int j=0;
		for(;  i<N; i++ ){
			if(arr[i].getValue()== n1){break;}
			rowIndex = i;
		}
		
		
		for(;  j<N; j++ ){
			if(arr[j].getValue() == n2){break;}
			colIndex = j;
		}
		
		// 行列互相联通
		adjMat[rowIndex][colIndex]=1;
		adjMat[colIndex][rowIndex]=1;
		// 自己联通自己
		adjMat[rowIndex][rowIndex]=1;
		adjMat[colIndex][colIndex]=1;
	}

}


编辑于 2019-08-13 17:48:39 回复(0)
import java.util.*;
public class Main {
    private static int m;
    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);
        }
        dfs(-1, 0, 0, children);
        System.out.println(2*(N-1) - m);
    }

    private static void dfs(int parent, int son, int cur, List<List<Integer>> children) {
        List<Integer> nextSon = children.get(son);
        if(nextSon.size() == 1) {
            m = Math.max(m, cur);
        }
        for(Integer tmp : nextSon) {
            if(tmp != parent) {
                dfs(son, tmp, 1 + cur, children);
            }
        }
    }
}
发表于 2019-07-09 23:30:41 回复(1)
const int N=1e5+10;//不加10通过率为40%,这块很疑问
发表于 2019-06-27 22:47:42 回复(1)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner; 
public class Main {
    static int m = 0;
    static Map<Integer, List<Integer>> map;
    public static void main(String[] args) { 
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        map = new HashMap<>();
        while (in.hasNextInt()) {//注意while处理多个case 
            int a = in.nextInt();
            int b = in.nextInt();
            if (map.containsKey(a)){
                List<Integer> list = map.get(a);
                list.add(b);
                map.put(a, list);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(b);
                map.put(a, list);
            }
        }
        //System.out.println(4);
        end(-1, 1, 0);
        System.out.println(2*(len-1) - m);
        return;
    } 
    private static void end(int father, int son, int now) {
        if (map.containsKey(son)) {
            for (int j : map.get(son)) {
                if (j==father) continue;
                end(son, j, now+1);
            }
        } else {
            m = Math.max(m, now);
        }
        
        return;
    }
}
不懂为啥只过了60%,数组越界的情况可以把jvm的错误输出打出来吧,要不然java的方便体现在哪?

发表于 2019-06-24 20:33:55 回复(0)

#只通过了60%case 不知道问题在哪

N = int(input())
l1 = [[] for _ in range(2*N)] 
for _ in range(N-1):
    i,x = map(int, input().split())
    l1[i].append(x) print(l1) 
def dfs(x,depth):
    temp = depth 
    for i in l1[x]:
        temp = max(temp,dfs(i,depth+1)) 
    return temp
depth = dfs(1,0) 
print(2*N-2-depth)
编辑于 2019-05-13 16:51:32 回复(2)