《刷题健身两不误》龙傲天转世

21、8.29 图的拓扑结

　　前段时间讲计算机网络，操作系统和c++的八股整理好了
　　快开学了，就多多休息了一段时间，现在回归学习啦啦啦啦

　　图的题目感觉就是dfs，可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，在换方向（换方向的过程就涉及到了回溯）。

　　void dfs(参数) {
　　if (终止条件) {
　　存放结果;
　　return;
　　}
　　for (选择：本节点所连接的其他节点) {
　　处理节点;
　　dfs(图，选择的节点); // 递归
　　回溯，撤销处理结果
　　}
　　}

　　图论基础及遍历算法：
　　797. 所有可能的路径记得回溯需要撤回处理结果，才可以返回上一个节点

　　环检测及拓扑排序算法：我大概知道需要用到拓扑结构，然后需要进行dfs，但我不会建立一个拓扑结构，从而进行遍历和判断。晚上等修勾给我讲一下
　　207. 课程表
　　210. 课程表 II

　　二分图判定算法：
　　二分图的特点：
　　1.所有的点将被分成独立的集合
　　2.每条边两端的点一定属于不同的集合
　　3.可能存在孤点
　　比如六边形就不是一个二分图，因为每条边的两端总是属于相同的集合。
　　785. 判断二分图
　　bfs是广度搜索法，用来判断一个节点邻边的点。
　　染色法（BFS），判断图是否为二分图。
　　核心是有一个color列表，存放节点的染色结果，未染色为0，代表染成一种颜色，2代表染成另一种颜色。
　　如果父节点为染色结果为1，那么如果子节点未染色，将子节点的染色结果设置为2.
　　如果子节点染色了，判断染色和父节点是否一致，如果一致，则不是二分图

　　具体步骤:
　　1.遍历所有定点
　　2.如果节点未染色加入到队列中，并且将节点染色为1.
　　3.节点出队列，并且遍历节点的子节点，判断子节点是否染色。
　　4.如果子节点未染色，将子节点的染色结果设置为2.如果子节点染色了，判断染色和父节点是否一致，如果一致，则不是二分图

　　886. 可能的二分法
　　这道题感觉就是bfs的二分图的判定。可能需要将数组变成二分图，但是具体的操作并不太会，就是知道大概的思路，晚上等待修勾给我说说

　　并查集（UNION-FIND）算法：看不懂，绝望了
　　130. 被围绕的区域