首页 > 试题广场 > 图的遍历
[编程题]图的遍历
  • 热度指数:2471 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

给定一张包含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个点,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)
发表于 2019-08-23 16:29:01 回复(0)
#include <bits/stdc++.h>
using namespace std;

int sum = 0;
const int N = 100003;
vector<int> v[N];

void DFS(int x, int pre, int w){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=pre)
            DFS(v[x][i], x, w+1);
    }
    sum = max(sum, w);
}

int main(){
    int n,x,y;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, -1, 0);
    cout<<2*(n-1)-sum<<endl;
    return 0;
}

发表于 2019-09-28 10:05:56 回复(0)
/*借用一下别人的代码,讲下思路: 其实就是每条边都会走两遍,一共有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)
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<List<Integer>> map = new ArrayList<>(n + 1);

        for (int i = 0; i <= n; i++) {
            map.add(new ArrayList<>());
        }

        for (int i = 1; i <= n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            List<Integer> lst = map.get(x);
            lst.add(y);
            lst = map.get(y);
            lst.add(x);
        }

        boolean[] vis = new boolean[n + 1];

        class Element {
            private int point;
            private int deep;
            private Element(int point, int deep) {
                this.point = point;
                this.deep = deep;
            }
        }

        Queue<Element> queue = new LinkedList<>();
        queue.add(new Element(1, 0));
        vis[1] = true;
        int max = 0;
        while (!queue.isEmpty()) {
            Element p = queue.poll();

            if(p.deep > max) {
                max = p.deep;
            }

            List<Integer> lst = map.get(p.point);
            if(lst.isEmpty()) {
                continue;
            }

            for (int t : lst) {
                if(!vis[t]) {
                    vis[t] = true;
                    queue.add(new Element(t, p.deep + 1));
                }
            }
        }

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

}

发表于 2019-09-15 16:48:18 回复(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 回复(4)
我的理解是,首先这不是一个环,然后从1出发有好几条路径,所以要遍历所有的节点的话,假设有n条路径,n-1条路径都需要走来回两遍,所以最短路径就是最长的那条路径只走一边,其余的都走两遍。
发表于 2019-08-09 10:29:34 回复(0)
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 10;

vector <int> G[N];
int mark[N];

int dfs1(int u) {
	mark[u] = 1;
	int D = 1;
	for (int v: G[u]) {
		if (!mark[v]) {
			D += (dfs1(v) + 1);
		}
	}
	return D;
}

int dfs2(int u) {
	mark[u] = 1;
	int Max = 0;
	for (int v: G[u]) {
		if (!mark[v]) {
			Max = max(Max, dfs2(v));
		}
	}
	return Max + 1;
}

int main() {
	int n, sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int x = dfs1(1);
	memset(mark, 0, sizeof(mark));
	int y = dfs2(1);
	x--;y--;
	cout << x - y << "\n";
	return 0;
}

发表于 2019-11-29 09:54:29 回复(0)
#include<bits/stdc++.h>
using namespace std;
#define N 100000
long n;
bool visited[N+1] = {false};
void bfs(vector<vector<int>>& v,long& ans)
{
    queue<int>q;
    // 从1号节点开始遍历
    q.push(1);
    visited[1]=true;
    while(!q.empty())
    {
        ans++;
        int len = q.size();
        // 前len个元素出队
        for(int i=0;i<len;++i)
        {
            int node = q.front();
            q.pop();
            for(int j=0;j<v[node].size();++j)
             {
                if(!visited[v[node][j]])
                {
                 q.push(v[node][j]);
                 visited[node]=true;
                
                }
             }
        }
        
    }
}
void dfs(vector<vector<int>>& v,long& ans,int entrance,long depth)
{
    for(int index_=0;index_<v[entrance].size();++index_)
    {
        if(!visited[v[entrance][index_]])
        {
            visited[v[entrance][index_]]=true;
            ans = max(ans,depth);
            dfs(v,ans,v[entrance][index_],depth+1);
            visited[v[entrance][index_]]=false;
        }
    }
}
int main()
{
    // 题意最小路程等于所有边走上两遍再减去从节点1出发能达到的最长路径
   
    cin>>n;
    // vector的二维数组来表示图
    vector<vector<int>>v(n+1);
    int x,y;
    for(int i=1;i<=n-1;++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    // DFS或BFS求最长路径
    //long ans = -1;
    //bfs(v,ans);
    long ans = 0;
    visited[1]=true;
    dfs(v,ans,1,1);
    cout<<2*(n-1)-ans<<endl;
    return 0;
}

发表于 2019-09-21 19:29:06 回复(0)
您的代码已保存
请检查是否存在数组越界等非法访问情况
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)
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 回复(1)

#只通过了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 回复(3)