图论算法（六）
分享丨【题单】图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
刷题交流｜【模拟退火算法】求解经典的地图填色问题 先码上，后面需要仔细的看一遍。
不得不说，灵神还是灵神呀，我现在只能用牛来形容。
图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
一、基础遍历
1.1、DFS基础
104. 二叉树的最大深度（20250326更新）
我们需要知道什么是二叉树的最大深度，就是从跟节点到最下方叶子节点经过的节点个数为二叉树的最大深度。
所以我们只需要遍历一次，记录最大深度就可以了。DFS和BFS都可以。
class Solution {
int depth = 0;
int res = 0;
public int maxDepth(TreeNode root) {
dfs(root);
return res;
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
// 进来+1，并更新最大高度
depth++;
res = Math.max(res, depth);
dfs(root.left);
dfs(root.right);
// 出去-1， 维护树的高度
depth--;
}
}1.2、BFS基础
104. 二叉树的最大深度（20250326更新）
这个也可以写成BFS的形式。
BFS有三种写法，一种就是最简单的，把节点存进去然后取出来遍历，但是这一种没有办法记录层数；第二种就是通过一个for循环来记录每一层，相当于每层的权重是1；还有第三种就是节点维护自己的层级（权重）。
class Solution {
int depth = 0;
public int maxDepth(TreeNode root) {
bfs(root);
return depth;
}
void bfs(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode node = q.poll();
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
depth++;
}
}
}二、其他
1791. 找出星型图的中心节点
有一个无向的星型图，由 n 个编号从 1 到 n 的节点组成，星型图有一个中心节点，并且恰有 n-1 条边将中心节点与其他节点连接起来。
给你一个二维整数数组 edges，其中 edges[i]=[ui, vi]表示在节点之间存在一条边，请你找出返回 edges 所有表示星型图的中心节点。
根据题意，中心节点必然出现在所有的 edges[i]中，根据第一条边，判断里面的两个数据是否在后面边里面，如果在的话，就是中心节点，否则就不是中心节点。
因为题目给出 n 是大于等于 3 的，必定是大于两个节点的。
class Solution {
public int findCenter(int[][] edges) {
int a = edges[0][0], b =edges[0][1];
if(a == edges[1][0] || a == edges[1][1]){
return a;
}
else{
return b;
}
}
}1557. 可以到达所有点的最少点数目
给你一个 有向无环图， n 个节点编码为 0 到 n-1， 以及一个变数组 edges，其中 edges[i] = [from, to], 表示一条从 from 到 to 的有向边。
找到最小的点集使得从这些点出发能到达图中所有的点，题目保证解存在且唯一。
你可以以任何顺序返回这些节点的编号。
最小的点集使得能够到达图的所有点，这里我们只需要找到入度为 0 的节点就是题目的解。
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
// 只有出度没有入度的节点?
int[] ans = new int[n];
for(List<Integer> dt: edges){
ans[dt.get(1)] += 1;
}
List<Integer> res = new ArrayList<>();
for(int i=0;i<ans.length;i++){
if(ans[i] == 0){
res.add(i);
}
}
return res;
}
}构建 java 列表并初始化的方式
1、List<Integer> list = Arrays.asList(1,2,3);
2、List<Integer> lit = new ArrayList<>(Arrays.asList(1,1,3));
3、List<String> lit = new ArrayList<>(Collections.singletonList("a", "b"));
图论基础及遍历算法
学习 labuladong 关于图相关的理论和知识点。
图的话和多叉树遍历类似，需要防止遍历的时候形成环，使用数据 visit 来表示每个节点是否被访问过。
图的存储的话有两种方式，一个是领接表，一个是领接矩阵，分别定义如下：
// 邻接表
List<Integer>[] graph;
// 邻接矩阵
boolean[][] graph;如果是带权图的话，邻接表存储的时候顺便把权重也存起来，邻接矩阵的话，每个坐标存的就是权重，不是 true 或者 false。
度（degree），入度（indegree）， 出度（outdegree）
矩阵（martix），顶点（vertex）
图的遍历模版：
// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;
void traverse(Graph graph, int s){
if(visited[s]){
return;
}
// 经过节点s，标记为已遍历
visited[s] = true;
// 做选择：标记节点s在路径上
onPath[s] = true;
for(int neighbor: graph.neighors(s)){
traverse(graph, neighbor);
}
// 撤销选择，节点s离开路径
onPath[s] = false;
}LCR 110. 所有可能的路径
给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出。
graph 的第 i 个数组中的单元都表示有向图 i 号节点所能够到达的下一个节点。
从 0 节点开始遍历图，将到达 n-1 的路径保存下来。
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
// 无环图
// 从 0 到 n-1的所有路径
// graph 邻接表
List<Integer> onPath = new ArrayList<>();
traverse(graph, 0, onPath);
return res;
}
// s 表示节点
public void traverse(int[][] graph, int s, List<Integer> onPath){
onPath.addLast(s);
int n = graph.length;
if(s == n-1){
res.add(new ArrayList<>(onPath));
}
for(int v: graph[s]){ // graph[s] 表示s能到达的所有节点
traverse(graph, v, onPath);
}
onPath.removeLast();
}
}547. 省份数量
这个题就是求无向图中的连通域的个数，直接 dfs/bfs。
题目给出的 isConnected 是邻接矩阵的存储方式。