以下内容均来自“代码随想录”
图的种类:整体上一般分为 有向图 和 无向图。
度:无向图中有几条边连接该节点,该节点就有几度。
在有向图中,每个节点有出度和入度。
出度:从该节点出发的边的个数。
入度:指向该节点边的个数。
连通图:在无向图中,任何两个节点都是可以到达的,我们称之为连通图。
强连通图:在有向图中,任何两个节点是可以相互到达的,我们称之为 强连通图。
连通分量:在无向图中的极大连通子图称之为该图的一个连通分量。
强连通分量:在有向图中极大强连通子图称之为该图的强连通分量。
图一般使用邻接表、邻接矩阵来表示。
深度优先搜索
搜索方向,是认准一个方向搜,直到碰壁之后再换方向,换方向是撤销原路径,改为节点链接的下一个路径,回溯的过程。代码框架:
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择:本节点所连接的其他节点) {处理节点;dfs(图,选择的节点); // 递归回溯,撤销处理结果}
}
深度搜索练习题目链接:卡码网题目链接(ACM模式)
广度优先搜索
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。
那么用队列,还是用栈都是可以的。
用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针。因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。
如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历。因为栈是先进后出,加入元素和弹出元素的顺序改变了。
import java.util.*;public class Main {// 表示四个方向static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // grid 是地图,也就是一个二维数组// visited 标记访问过的节点,不要重复访问// x, y 表示开始搜索节点的下标public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {Queue<int[]> queue = new LinkedList<>(); // 定义队列queue.offer(new int[]{x, y}); // 起始节点加入队列visited[x][y] = true; // 加入队列后立即标记为已访问while (!queue.isEmpty()) { // 遍历队列中的元素int[] cur = queue.poll(); // 从队列取出元素int curx = cur[0];int cury = cur[1]; // 当前节点坐标for (int i = 0; i < 4; i++) { // 遍历当前节点的四个方向int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标// 检查边界条件if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {continue; // 坐标越界,跳过}// 如果节点未被访问过if (!visited[nextx][nexty]) {queue.offer(new int[]{nextx, nexty}); // 将节点加入队列visited[nextx][nexty] = true; // 加入队列后立即标记为已访问}}}}public static void main(String[] args) {// 示例使用char[][] grid = {{'1', '1', '0', '0'},{'1', '0', '0', '1'},{'0', '0', '1', '1'}};boolean[][] visited = new boolean[grid.length][grid[0].length];// 从(0, 0)开始搜索bfs(grid, visited, 0, 0);}
}