图的度
无向图:
连接某节点的边数,即为该节点的【度】。
(无向图中,有5条边连接节点4,则节点4的度为5。)
有向图:
出度:从该节点出发的边的个数。
入度:指向该节点边的个数。
(有向图中,
从节点3出发的边的个数是2,则节点3的入度为2;
指向节点3的边的个数是5,则出度为5)
连通性
(无向图)
连通图:在无向图中,任何两个节点都是可以到达的图。
非连通图:在无向图中,存在有节点不能到达其他节点的图。
(有向图)
强连通图:在有向图中,任何两个节点是可以相互到达的图。
图的存储
邻接表
邻接矩阵
一、深搜 与 广搜
数据结构与算法 | 深搜(DFS)与广搜(BFS)_深搜广搜算法-CSDN博客
深度优先搜索理论基础
深搜和广搜的区别:
(通俗版)
广搜(bfs)是一圈一圈的搜索过程,
深搜(dfs)是一条路跑到黑然后再回溯。
- dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,再换方向(换方向的过程就涉及到了回溯)。
- bfs是先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。
二叉树的递归法,就是dfs。
二叉树的迭代法,就是bfs(广度优先搜索)。
所以dfs,bfs其实是基础搜索算法,也广泛应用与其他数据结构与算法中。
深度优先搜索(Depth First Search)
深搜dfs关键就两点:
- 搜索方向,是认准一个方向搜,直到碰壁之后再换方向
- 换方向是撤销原路径,改为节点链接的下一个路径,回溯的过程。
因为dfs搜索可一个方向,并需要回溯,所以用递归的方式来实现是最方便的。
回溯链接:C++学习/复习补充记录 --- 递归、回溯_c++中回溯是啥-CSDN博客
深搜三部曲
1、确认递归函数,参数
2、确认终止条件
3、处理目前搜索节点出发的路径
深搜代码模板:
//1、确认递归函数,参数 vector<vector<int>> result; // 保存符合条件的所有路径(存放结果组合的vector) vector<int> path; // 起点到终点的路径(单个组合结果)void dfs (图,目前搜索的节点) {if (剪枝条件) return;//剪枝//2、确认终止条件if (终止条件) {result.push_back(path);//存放结果;return;}//3、处理目前搜索节点出发的路径for (选择:本层节点所连接的其他节点) {处理节点;(做选择)dfs(图,选择的节点); // 递归回溯,撤销处理结果(撤销选择)} }
(回溯撤销处理结果其实就是:撤回一步,回到上一步重新走另一个方向。)
广度优先搜索(Breadth First Search)
1、应用场景:
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路
2、实现方式:
用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针。
因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。
如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历。
因为栈是先进后出,加入元素和弹出元素的顺序改变了。
广搜不需要注意 转圈搜索的顺序 !
广搜代码模板:
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; // 只要加入队列立刻标记,避免重复访问}}} }
(该模板针对的是如下图的四方格地图)
实际应用
输入数据的含义:
例一:
输入:graph = [[1,2],[3],[3],[]]
节点0可链接到的节点有:节点1,节点2;
节点1可链接到的节点有:节点3;
节点2可链接到的节点有:节点3;
节点3可链接到的节点有:无。
例二:
输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]
节点0可链接到的节点有:节点4,节点3,节点1;
节点1可链接到的节点有:节点3,节点2,节点4;
节点2可链接到的节点有:节点3;
节点3可链接到的节点有:节点4;
节点4可链接到的节点有:无。
1.1 所有可能的路径 (深搜)
给你一个有
n
个节点的 有向无环图(DAG),请你找出所有从节点0
到节点n-1
的路径并输出(不要求按特定顺序)
graph[i]
是一个从节点i
可以访问的所有节点的列表(即从节点i
到节点graph[i][j]
存在一条有向边)。
class Solution {vector<vector<int>> result;//符合条件的路径集合vector<int> path;//0节点到终点的路径void dfs(vector<vector<int>>& graph, int cur) {//cur为当前遍历到的节点if (cur == graph.size() - 1) {//要求从节点0到节点n-1的路径并输出,所以是 graph.size() - 1result.push_back(path);return;//已找到一条符合条件的路径}for (int i = 0; i < graph[cur].size(); i++) {//遍历当前节点可链接到的所有节点path.push_back(graph[cur][i]);//当前选择的链接节点尝试加入dfs(graph, graph[cur][i]);//加入下一层递归path.pop_back();//当前选择的链接节点走不通,不带上玩,腾出位置尝试另一个}}
public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);//所有路径皆是从节点0出发dfs(graph, 0);//开始遍历return result;}
};