Day56_20250204_图论part1_图论理论基础|深搜理论基础|98.所有可达路径|广搜理论基础

深搜理论基础

基础知识
- 深搜与广搜
- 并查集
- 最小生成树
- 拓扑排序
- 最短路算法
图论理论基础
- 图的基本概念
  - 多个点连线
- 连通性
  - 表示节点的连通情况
  - 无向图
    - 连通图
    - 非连通图
    - 连通分量：极大连通子图。
  - 有向图
    - 强连通图
      - 任何两个节点是可以相互到达的。
    - 强连通分量：在有向图中极大强连通子图
- 图的构造
  - 组成：邻接表、临接矩阵、类。主要是朴素存储、邻接表和临接矩阵
  - 邻接矩阵：
    - 二维数组来表示图结构。
    - 从节点的角度来表示图，有多少节点就申请多大的二维数组。
  - 邻接表
    - 数组+链表
    - 从边的数量来表示图，有多少边申请对应大小的链表。
- 图的遍历方式
  - 深度优先搜索(dfs) ex:二叉树的递归遍历
  - 广度优先搜索(bfs) ex:二叉树的层序遍历

深度优先搜索理论基础(dfs)

dfs和bfs的区别
- dfs深度优先搜索：
  - 可一个方向去搜，不到黄河不回头。直到无法继续搜下去，再换方向(回溯)
- bfs广度优先搜索：
  - 先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
dfs搜索过程
- dfs搜索可一个方向，并需要回溯，所以用递归的方式来实现是最方便的。

代码模板

dfs，回溯

void dfs(参数){
	if(终止条件){
		存放结果；
		return;
	}
	for(选择：本节点所连接的其他节点){
		处理节点；
		dfs(图，选择的节点)；
		回溯，撤销处理结果
	}

}

深搜三部曲

void dfs(参数)//1.确认递归函数、参数
//2.确认终止条件,收获结果
if(终止条件){
	存放结果；
	return;
}
//3.处理目前搜索节点出发的路径
for(选择：本节点所连接的其他节点){
	处理节点；
	dfs(图，选择的节点)；//递归
	回溯，撤销处理结果
}

二维数组结构保存所有路径，一维数组保存单一路径。定义全局变量

vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)

98.所有可达路径

题目

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入：

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出：

输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5 ， 5后面没有空格！

例子：

输入：

输出：

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5 ， 5后面没有空格！

思路

思路

代码

邻接矩阵

import java.util.ArrayList;//动态数组，存储任意类型的元素，
import java.util.List;//有序的元素集合
import java.util.Scanner;//从标准输入中读取数据
public class Main{
    //2个路径
    static List<List<Integer>> result=new ArrayList<>();//所有路径
    static List<Integer> path=new ArrayList<>();//1节点到终点的路径
    public static void main(String[] args){
	//输入 n个节点，m条边
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();

        //邻接矩阵构建
        int[][] graph=new int[n+1][n+1];

        for(int i=0;i<m;i++){
            int s=scanner.nextInt();
            int t=scanner.nextInt();
            //使用邻接矩阵表示无向图，1表示s与t是相连的
            graph[s][t]=1;
        }
	//路径搜索部分
        path.add(1);//无论什么路径已经是从1节点出发
        dfs(graph,1,n);//开始遍历
        //打印输出结果
        if(result.isEmpty()) System.out.println(-1);
        for(List<Integer> pa:result){
            for(int i=0;i<pa.size()-1;i++){
                System.out.print(pa.get(i)+" ");
            }
            System.out.println(pa.get(pa.size()-1));
        }

    }
    //递归
    public static void dfs(int[][] graph,int x,int n){
        //终止条件，当前遍历的节点x到达节点n
        if(x==n){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=1;i<=n;i++){
            if(graph[x][i]==1){//找到x链接的节点
                path.add(i);//遍历到的节点加入到路径中来。
                dfs(graph,i,n);//下一层递归
                path.remove(path.size()-1);//回溯，撤销本节点

            }
        }

    }

}

邻接表

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;


public class Main{
    //2个路径
    static List<List<Integer>> result=new ArrayList<>();//收集符合条件的路径
    static List<Integer> path=new ArrayList<>();//1节点到终点的路径
  
    public static void main(String[] args){
        //输入
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
    
        //邻接表，表的数量=边的数量
        List<LinkedList<Integer>> graph=new ArrayList<>(n+1);
        for(int i=0;i<=n;i++){
            graph.add(new LinkedList<>());
        }
    
        //？
        while(m-->0){
            int s=scanner.nextInt();
            int t=scanner.nextInt();
            //s和t是相连的
            graph.get(s).add(t);
        }
        path.add(1);//无论什么路径已经是从1节点出发
        dfs(graph,1,n);//开始遍历
    
        //打印输出结果
        if(result.isEmpty()) System.out.println(-1);
        //遍历并打印所有路径
        //遍历所有路径，pa每一条路径
        for(List<Integer> pa:result){
            //打印路径中的每个节点,从起点1到终点n的一条路径。最后输出一个多余的空格
            for(int i=0;i<pa.size()-1;i++){
                System.out.print(pa.get(i)+" ");
            }
            //打印路径最后一个节点
            System.out.println(pa.get(pa.size()-1));//
        }
    
    
    
    }
    public static void dfs(List<LinkedList<Integer>> graph,int x,int n){
        //终止条件
        if(x==n){
            result.add(new ArrayList<>(path));
            return;
        }
        //递归
        for(int i:graph.get(x)){
            path.add(i);
            dfs(graph,i,n);//进入下一层递归
            path.remove(path.size()-1);//回溯，撤销本节点
        }
    
    }
}

总结

掌握邻接表和邻接图的代码写法
挺复杂的，需要多练习几遍

广搜理论基础广搜(bfs)是一圈一圈的搜索过程，和深搜(dfs)是一条路跑到黑然后再回溯。

使用场景：
- 解决两个点之间的最短路径问题。
- 广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
- 岛屿问题广搜深搜都可以，特征是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。
- - 一旦遇到终止点，一定是一条最短路径。地图中可以有障碍。

怎么进行一圈一圈的搜索，放在什么容器里，才能这样去遍历。

需要一个容器，保存遍历过的元素就可以。队列，栈，数组
- 队列，每一圈都是一个方向去转，统一顺时针或逆时针
- 栈，第一圈顺时针遍历，第二圈逆时针遍历，第三圈顺时针遍历
- 数组，

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

}