做游戏模型素材 网站,做网站存在的问题,稳定的常州网站推广,潍坊市城市建设官网站今日收获#xff1a;图论理论基础#xff0c;深搜理论基础#xff0c;所有可达路径#xff0c;广搜理论基础#xff08;理论来自代码随想录#xff09;
1. 图论理论基础
#xff08;1#xff09;邻接矩阵
邻接矩阵存储图#xff0c;x和y轴的坐标表示节点的个数 优点…今日收获图论理论基础深搜理论基础所有可达路径广搜理论基础理论来自代码随想录
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 ListListInteger resultnew ArrayList();static ListInteger pathnew ArrayList();public static void main(String[] args){Scanner scnew Scanner(System.in);int Nsc.nextInt();int Msc.nextInt();// 存储图的邻接矩阵int[][] graphnew int[N1][N1];for (int i0;iM;i){int ssc.nextInt();int tsc.nextInt();graph[s][t]1;}path.add(1); // 出发点dfs(graph,1,N); // 开始深度搜索// 输出结果if (result.size()0){System.out.println(-1);}else {for (ListInteger pa:result){for (int i0;ipa.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 (currentN){ // 走到终点result.add(new ArrayList(path));return;}for (int i1;iN1;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 ListListInteger resultnew ArrayList();static ListInteger pathnew ArrayList();public static void main(String[] args){Scanner scnew Scanner(System.in);int Nsc.nextInt();int Msc.nextInt();// 存储图的邻接表ListLinkedListInteger graphnew ArrayList(N1);for (int i0;iN1;i){graph.add(new LinkedListInteger());}for (int i0;iM;i){int ssc.nextInt();int tsc.nextInt();graph.get(s).add(t);}path.add(1); // 出发点dfs(graph,1,N); // 开始深度搜索// 输出结果if (result.size()0){System.out.println(-1);}else {for (ListInteger pa:result){for (int i0;ipa.size()-1;i){System.out.print(pa.get(i) );}System.out.println(pa.get(pa.size()-1));}}}public static void dfs(ListLinkedListInteger graph,int current,int N){if (currentN){ // 走到终点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 {ListListInteger resultnew ArrayList();ListInteger pathnew ArrayList();public ListListInteger allPathsSourceTarget(int[][] graph) {int ngraph.length-1;path.add(0);dfs(graph,0,n);return result;}public void dfs(int[][] graph,int current,int n){if (currentn){result.add(new ArrayList(path));return;}for (int i:graph[current]){path.add(i);dfs(graph,i,n);path.remove(path.size()-1);}}
}
4. 广搜理论基础
思想一圈一圈的搜索每次遍历当前节点连接的所有节点
使用场景解决两点之间的最短路径问题
解决方式用队列/栈/数组只要能保存遍历过的元素。用队列时先加入起始节点并标记为访问然后遍历队列计算当前节点的连接节点如果连接节点没有被访问过则加入队列。
