Yyc

用户名：EvoYyc

访问量：1692

签　名：

等　　级
排　　名	14647
经　　验	871
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	西京学院
专　　业

　　自我简介：

TA的其他文章

城市建设-通过kruskal算法生成最小生成树 [Java][超详细注解]
浏览：542

网络寻路-通过DFS(深搜)+邻接表实现 [Java][超详细注解]
浏览：816

文化之旅-采用Dijkstra寻找最短路径 [Java][详细注解]
浏览：255

你可能喜欢

网络寻路-通过DFS(深搜)+邻接表实现 [Java][超详细注解]

　　作者: Yyc　　　　发表时间：2022-01-16 16:54:26 浏览：816　|　评论：0　

原题链接：蓝桥杯历届试题-网络寻路

# 基本思路

首先找路径数，很明显能想到用DFS（深度优先搜索）
但是有没有明确的终点，同时还给了一共需要转发2次（即需要走四个地点）
那么我们就可以想到用邻接表或邻接矩阵的数据结构来储存地点之间的线路关系。

## 邻接表的介绍

邻接表就是用一个集合储存多个集合。其中最外部的集合为地点编号、内部的集合表示该地点所能到达的地点。按照样例输入后，邻接表形式如下
此时我们有一个Vector<Vector<Integer>>
V1 -> 2 、3、4
V2 -> 1、3
V3 -> 1、2
V4 -> 1

## 深搜的思路

**深搜的结束条件：**
走到了最后一个点。此时就算是一条成功的转发路线。

**深搜的继续条件：**
转发次数还没满两次（或者可以理解为走的点还没有满四个）
那么就继续对当前点可以走到的所有点进行一次遍历，并且判断是否可以走后
再对下一个点，进行一次DFS搜索。知道满足结束条件后，退出DFS。

## 为什么不用邻接矩阵

邻接矩阵通常适用于稠密图，如果是非稠密图会造成很大的内存浪费，同时会让DFS次数增多，可能会有爆栈的风险，此处不用它，所以不详细讲，如果有兴趣可以自己了解邻接矩阵的数据结构。

# 实现代码

```java
package 蓝桥;

import java.util.*;

public class 网络寻路_1452 {

public static Vector<Vector<Integer>> vertexes = new Vector<>();

public static int[] visited = new int[100001];

public static int sum = 0;

public static int start = 0;

// 题目地址：https://www.dotcpp.com/oj/problem1452.html
    // 思路：深搜（DFS）、邻接表
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();

// 初始化邻接表
        for (int i = 0; i < n; i++) {
            vertexes.add(new Vector<>());
        }

// 邻接表的输入
        for (int i = 0; i < m; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            // 此处我们将输入的第一个点作为出发的点
            // 那么to就是from这个的目标点
            vertexes.get(from - 1).add(to - 1);
            // 此处我们将输入的第二个点作为出发的点
            // 那么from就是to这个的目标点
            vertexes.get(to - 1).add(from - 1);
            // 为什么要这样？！因为这些线路是双向的，可以往回走的！
        }

int i = 0;
        for (Vector<Integer> node : vertexes) {
            // 先把起点标记上
            visited[i] = 1;
            // 记录开始的点，这里start是全局变量，所以在DFS里面也可以访问
            // 主要用来做到最后到终点的判断
            start = i;
            DFS(1, node);
            // 记得还原
            visited[i] = 0;
            // 因为for用了快速遍历，所以需要有一个i记录起点
            // 当然我们用传统for语句也可以
            i++;
        }

System.out.println(sum);
    }

// forwarnNum 用来记录走的地点数量、node用来记录下一个可以走的点的集合
    public static void DFS(int forwardNum, Vector<Integer> node) {
        // 如果 forwardNum == 那就说明此时走的就是最后到终点的那一步
        // 此时我么做一个特殊判断即可，不需要在做一次DFS了。
        if (forwardNum == 3) {
            for (int vertex : node) {
                // 此处有两种可能，走过的下一个点，从来没有被走过，自然可以走
                // 第二种：和起点一样，则也可以走。
                // 满足上述两种的话，就 sum++ 并退出
                if (visited[vertex] == 0 || vertex == start) {
                    sum++;
                }
            }
            return;
        }

// 能到这里，就说嘛不是最后的异步
        // 就把这点能走的其他点走一遍
        for (int vertex : node) {
            // 如果这个点之前已经被记录走过了，那就不走他
            if (visited[vertex] == 1) continue;
            // 能到这里就是可以走
            // 那就接着获取走了之后，能走的点
            Vector<Integer> next = vertexes.get(vertex);
            // 标记为已走过
            visited[vertex] = 1;
            DFS(forwardNum + 1, next);
            // 记得还原！
            visited[vertex] = 0;
        }
    }
}

```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Yyc

TA的其他文章

你可能喜欢

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

C二级辅导-计负均正（C语言代码）

网络寻路-通过DFS(深搜)+邻接表实现 [Java][超详细注解]

评论区

精彩推荐

C语言训练-求PI* （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

拆分位数（C语言代码）

用筛法求之N内的素数。（C语言代码）

简单的a+b （C语言代码）

众数问题（C语言代码）

IP判断（C语言描述，蓝桥杯）

Cylinder （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Yyc

TA的其他文章

你可能喜欢

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

C二级辅导-计负均正 （C语言代码）

网络寻路-通过DFS(深搜)+邻接表实现 [Java][超详细注解]

评论区

精彩推荐

C语言训练-求PI* （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

拆分位数 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

简单的a+b （C语言代码）

众数问题 （C语言代码）

IP判断 （C语言描述，蓝桥杯）

Cylinder （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蛇行矩阵（C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

拆分位数（C语言代码）

用筛法求之N内的素数。（C语言代码）

众数问题（C语言代码）

IP判断（C语言描述，蓝桥杯）