算法打卡：第十一章 图论part01

今日收获：图论理论基础，深搜理论基础，所有可达路径，广搜理论基础（理论来自代码随想录）

1. 图论理论基础

（1）邻接矩阵

邻接矩阵存储图，x和y轴的坐标表示节点的个数

优点：

• 表达方式简单，易于理解
• 易于检查两个顶点间是否存在边
• 适合稠密图，此时邻接矩阵是一种空间效率较高的表示方法，矩阵中的格子利用率高。

缺点：

• 遇到稀疏图，会导致申请过大的二维数组造成空间浪费。
• 遍历边的时候需要遍历整个n * n矩阵，造成时间浪费。

（2）邻接表

邻接表使用 数组 + 链表 的方式来表示。数组的长度是节点个数，节点的边用链表连接。

 优点：

• 对于稀疏图的存储，只需要存储边，空间利用率高
• 遍历节点连接情况相对容易

缺点：

• 检查任意两个节点间是否存在边，效率相对低，需要遍历数组中某个节点连接的整个链表
• 实现相对复杂，不易理解

（3）图的遍历方式

• 深度优先搜索（dfs）
• 广度优先搜索（bfs）

2. 深搜理论基础

（1）思想

        一条道走到黑，不到黄河不死心，不撞南墙不回头（走投无路或者找到了就回到上一个节点再重复，即回溯）

（2）代码框架

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

3. 所有可达路径

题目链接：98. 所有可达路径

思路：回溯算法

（1）邻接矩阵

a. 首先根据节点的个数创建二维数组，然后遍历节点之间的边，如果存在边则二维数组对应位置设为1。

b. 在回溯函数中，遍历所有的节点，如果当前所处的节点位置和遍历节点之间存在边，则将当前遍历节点添加到路径中，递归调用回溯函数，函数结束后取消路径中的当前遍历节点

c. 如果当前所处的节点位置是终点，则收获结果

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

public class Main{
    static List<List<Integer>> result=new ArrayList<>();
    static List<Integer> path=new ArrayList<>();
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int M=sc.nextInt();
        
        // 存储图的邻接矩阵
        int[][] graph=new int[N+1][N+1];
        
        for (int i=0;i<M;i++){
            int s=sc.nextInt();
            int t=sc.nextInt();
            
            graph[s][t]=1;
        }
        
        path.add(1);  // 出发点
        dfs(graph,1,N);  // 开始深度搜索
        
        // 输出结果
        if (result.size()==0){
            System.out.println("-1");
        }else {
            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 current,int N){
        if (current==N){  // 走到终点
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i=1;i<N+1;i++){  // 从小到大遍历节点
            if (graph[current][i]==1){  // 存在边
                path.add(i);  // 走到下一个节点
                dfs(graph,i,N);
                path.remove(path.size()-1);  // 回溯
            }
        }
    }
    
}

（2）邻接表

a. 首先创建存储整型链表的列表作为图，将列表中的每个节点都添加一个链表。遍历边时，将结尾节点添加到列表中起点的链表中。

b. 回溯函数中，遍历当前所处位置节点的连接节点时，获取其链表，然后再遍历链表中的元素

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

public class Main{
    static List<List<Integer>> result=new ArrayList<>();
    static List<Integer> path=new ArrayList<>();
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int M=sc.nextInt();
        
        // 存储图的邻接表
        List<LinkedList<Integer>> graph=new ArrayList<>(N+1);
        for (int i=0;i<N+1;i++){
            graph.add(new LinkedList<Integer>());
        }
        
        for (int i=0;i<M;i++){
            int s=sc.nextInt();
            int t=sc.nextInt();
            
            graph.get(s).add(t);
        }
        
        path.add(1);  // 出发点
        dfs(graph,1,N);  // 开始深度搜索
        
        // 输出结果
        if (result.size()==0){
            System.out.println("-1");
        }else {
            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(List<LinkedList<Integer>> graph,int current,int N){
        if (current==N){  // 走到终点
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i:graph.get(current)){  // 从小到大遍历节点
            path.add(i);  // 走到下一个节点
            dfs(graph,i,N);
            path.remove(path.size()-1);  // 回溯
        }
    }
    
}

总结：打印二维数组最好使用增强for循环遍历

（3）相似题目

题目链接：797. - 力扣（LeetCode）

思路：回溯算法。首先添加起点0，当前位置也为0，然后遍历当前位置连接的节点，将连接节点加入路径列表中再调用函数深度搜索；当前连接节点上的路径深度搜索之后，去掉路径列表中的当前节点。

方法：

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new ArrayList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n=graph.length-1;

        path.add(0);
        dfs(graph,0,n);
        return result;
    }

    public void dfs(int[][] graph,int current,int n){
        if (current==n){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i:graph[current]){
            path.add(i);
            dfs(graph,i,n);
            path.remove(path.size()-1);
        }
    }
}

4. 广搜理论基础

思想：一圈一圈的搜索，每次遍历当前节点连接的所有节点

使用场景：解决两点之间的最短路径问题

解决方式：用队列/栈/数组，只要能保存遍历过的元素。用队列时，先加入起始节点并标记为访问；然后遍历队列，计算当前节点的连接节点，如果连接节点没有被访问过则加入队列。