首页 > 试题广场 > 图的遍历
[编程题]图的遍历
  • 热度指数:5679 时间限制: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)
我的理解是,首先这不是一个环,然后从1出发有好几条路径,所以要遍历所有的节点的话,假设有n条路径,n-1条路径都需要走来回两遍,所以最短路径就是最长的那条路径只走一边,其余的都走两遍。
发表于 2019-08-09 10:29:34 回复(2)
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 回复(1)
/*借用一下别人的代码,讲下思路: 其实就是每条边都会走两遍,一共有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个节点,由该节点出发bfs遍历所得最大深度d,最短路程就是2*(N-1)-d
    原因:最短的路径,为沿最小生成树行走。每次到叶节点返回,在每个分支节点处都要经过两次。
          但注意到,如果某节点之前所有的子树都已经遍历过了,那么其与最后一个子树连接走一次即可。
          如此递归下去即有一条从根到叶子结点的路径只走了一次,那么只要使这条路径最长即可完成总路程最短的目标。
          显然在本题中,最长的路径就是图bfs得到的深度。而最小生成树总共有N-1条边,若树的深度为d,那么最短路程就是2*(N-1)-d。
    推广:对于一般的图,要想找到由某点出发遍历全图节点的最短路程。只需要首先找出该结点为根的最小生成树,
          再进一步寻找最寻找最小生成树中根到叶子结点的最长路径即可。
#include<iostream>
(720)#include<vector>
#include<queue>
(789)#include<algorithm>
#define N 100001
using namespace std;
int n,deg=0;
bool visit[N]={false};
vector<int> map[N];
int main()
{
    int x,y;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y;
        map[x].push_back(y);
        map[y].push_back(x);
    } 
    queue<int> Q;
	Q.push(1);
	int p,end=1,nend,adj;
	while(!Q.empty())
	{
		p=Q.front();
		visit[p]=true;
		//cout<<p<<' '<<data[p].degree<<endl;
		Q.pop();
		for(int i=0;i<map[p].size();i++)
		{
			adj=map[p][i];
			if(!visit[adj])
			{
				Q.push(adj);
				nend=adj;
			}
		}
		if(p==end) 
		{
			end=nend;
			deg++;	
		}
	}
	deg--;   
    
	cout<<2*(n-1)-deg;
		
    return 0;
}


发表于 2020-03-27 20:13:30 回复(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 回复(6)
n = int(input())
path = {i: [] for i in range(n)}

for i in range(n-1):
    s, e = [int(i) - 1 for i in input().split()]
    
    path[s].append(e)
    path[e].append(s)

visited = [False] * n
stack = [0]
visited[0] = True
depth = 0

while stack:
    t = []
    while stack:
        node = stack.pop()
        for child in path[node]:
            if visited[child]:
                continue
            else:
                visited[child] = True
                t.append(child)
                
    stack = t
    if stack:
        depth += 1

print(2*(n-1) - depth)

发表于 2020-08-04 22:23:13 回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;
int main(){
    int N;
    cin>>N;
    vector<pair<int, int>> P(N-1);
    vector<vector<int>> matrix(N+1);
    for (int i = 0; i < N-1; ++i) {
        cin>>P[i].first>>P[i].second;
    }
    for (int i = 0; i < N-1; ++i) {
        matrix[P[i].first].push_back(P[i].second);
        matrix[P[i].second].push_back(P[i].first);
    }
    vector<bool> isVisted(N, false);
    queue<int> Q;
    isVisted[1] = true;
    Q.push(1);
    int num = 1;
    int level = 0;
    int count = 0;
    while(!Q.empty()){
        int val = Q.front();
        Q.pop();
        for (int i = 0; i < matrix[val].size(); ++i) {
            if(!isVisted[matrix[val][i]]) {
                Q.push(matrix[val][i]);
                isVisted[matrix[val][i]] = true;
                ++count;
            }
        }
        --num;
        if(num == 0){
            ++level;
            num = count;
            count = 0;
        }
    }
    cout<<2*(N-1)-level+1<<endl;
    return 0;
}


非递归的BFS
发表于 2020-06-08 10:53:23 回复(0)
递归实现深度优先搜索最终只能通过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)
#处理stack有两种方式,一是记录原来长度,切片
(3755)#二是直接把新元素添加给临时数组,直接赋值或者深拷贝
N = int(input())
edge = [[] for i in range(N)]
stack = []
for i in range(N-1):
    x, y = map(int,input().split())
    edge[x-1].append(y - 1)
    edge[y-1].append(x - 1)

visit = [False for i in range(N)]
visit[0] = True
stack.append(0)
depth = 1
while len(stack) > 0:
    temp = []
    flag = False
    while len(stack) > 0:
         i = stack.pop()
         for j in edge[i]:
            if visit[j]:
                    continue
            else:
                temp.append(j)
                visit[j] = True
                flag = True
        
    if flag:
        depth += 1
    stack = temp[:]
                
print(2 * N - 1 - depth)

发表于 2020-03-26 16:58:47 回复(0)
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] visit = new boolean[n+1];
		for(int i=0;i<n+1;i++)
			visit[i] = false;
		
		List<List<Integer>> map = new ArrayList<> ();
		for(int i=0;i<=n;i++) {
			List<Integer> lst = new ArrayList<Integer>();
			lst.add(i);
			map.add(lst);
		}
		for(int i=1;i<n;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);
		}//graph
		
		
		class Element{
			int point;
			int deep;
			Element(int point, int deep){
				this.point = point;
				this.deep = deep;
			}
		}
		Queue<Element> queue = new LinkedList<>();
		Element e = new Element(1,0);
		visit[1] = true;
		int max = 0;
		queue.offer(e);
		while(!queue.isEmpty()) {
			Element temp = queue.poll();
			max=Math.max(max, temp.deep);
			List<Integer> lst = map.get(temp.point);
			for(int i=1;i<lst.size();i++) {
				if(!visit[lst.get(i)]) {
					visit[lst.get(i)]=true;
					queue.offer(new Element(lst.get(i),temp.deep+1));
				}
			}
		}
		int distance = 2*((n-1)-max)+max;
		System.out.println(distance);
	}
}

发表于 2020-03-19 15:45:01 回复(0)
package main

import (
	"fmt"
	"math"
)

var (
	sum    = 0
	v      = make(map[int][]int, N)
	visted = make(map[int]int, N)
	N      = 1000
)

func dfs(x int, w int) {
	for i := 0; i < len(v[x]); i++ {
		if visted[v[x][i]] == 0 {
			visted[v[x][i]] = 1
			dfs(v[x][i], w+1)
		}
	}
	sum = int(math.Max(float64(sum), float64(w)))
}

func main() {
	var a, b int
	fmt.Scanf("%d", &N)
	for i := 1; i <= N; i++ {
		visted[i] = 0
	}
	for i := 1; i <= N-1; i++ {
		fmt.Scanf("%d %d", &a, &b)
		v[a] = append(v[a], b)
		v[b] = append(v[b], a)
	}
	visted[1]=1
	dfs(1, 0)
	fmt.Println(2*(N-1) - sum)
}

编辑于 2020-03-13 00:16:10 回复(0)
93.3%,发生段错误,原因是输入的时候,当成i=0, i < n了!
发表于 2020-03-07 20:35:44 回复(1)
#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 回复(3)
不知道为什么,通过率只有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)