图论基础

图本质上就是个高级点的多叉树而已，适用于树的 DFS/BFS 遍历算法，全部适用于图。

1. 图的存储常常通过邻接表和邻接矩阵来实现

2. 我们再明确一个图论中特有的度（degree）的概念：

        在无向图中，「度」就是每个节点相连的边的条数

        由于有向图的边有方向，所以有向图中每个节点「度」被细分为入度（indegree）和出度（outdegree）=> 入度：指向该节点边的数量

遍历算法框架

DFS

图和多叉树最大的区别是，图是可能包含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点，而树不会出现这种情况，从某个节点出发必然走到叶子节点，绝不可能回到它自身。

所以，如果图包含环，遍历框架就要一个 visited 数组进行辅助

 这里你看到的onPath是用来解决路径问题的 => 标记正在走的路线

类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。在图的遍历过程中，onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景，这下你可以理解它们二者的区别了吧。

如果让你处理路径相关的问题， onPath 变量是肯定会被用到的，拓扑排序 中就有运用。

这个 onPath 数组的操作很像回溯算法中的「做选择」和「撤销选择」，区别在于位置：

回溯算法的「做选择」和「撤销选择」在 for 循环里面，

而对 onPath 数组的操作在 for 循环外面。

回溯算法和 DFS 算法的区别所在：回溯算法关注的不是节点，而是树枝。

// DFS 算法，关注点在节点
void traverse(TreeNode* root) {if (root == nullptr) return;printf("进入节点 %s", root);for (TreeNode* child : root->children) {traverse(child);}printf("离开节点 %s", root);
}// 回溯算法，关注点在树枝
void backtrack(TreeNode *root) {if (root == nullptr) return;for (TreeNode* child : root->children) {// 做选择printf("从 %s 到 %s", root, child);backtrack(child);// 撤销选择printf("从 %s 到 %s", child, root);}
}

vector<bool> visited;
vector<bool> onPath;
void DFS(Graph graph, int s){if(visited[s]) return;visited[s] = true;onPath[s] = true;for(auto neighbour:graph.neighbour(s)){DFS(graph,neighbour);}onPath[s] = false;
} 

BFS

所谓「出度」和「入度」是「有向图」中的概念，很直观：如果一个节点 x 有 a 条边指向别的节点，同时被 b 条边所指，则称节点 x 的出度为 a，入度为 b。

按道理， 图的遍历 都需要 visited 数组防止走回头路，

这里的 BFS 算法其实是通过 indegree 数组实现的 visited 数组的作用，只有入度为 0 的节点才能入队，从而保证不会出现死循环。

void BFS(int num, vector<vector<int>>& pre){queue<int> q;for(int i=0;i<num;i++){if(!indegree[i]) q.push(i);}int cnt = 0;while(!q.empty()){int cur = q.front();q.pop();cout << cur.val;for(auto next:graph[cur]){indegree[next]--;if(!indegree[next]) q.push(next);}}}

环检测算法

207. 课程表 - 力扣（LeetCode）

成环 => 结点之间有依赖关系

先修课程修完才能学习下面的课程 => 这就是依赖关系

如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。

DFS

class Solution {
public:bool hasCycle = false;vector<bool> onPath;vector<bool> visited;vector<vector<int>> graph;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {onPath.resize(numCourses);visited.resize(numCourses);buildGraph(numCourses, prerequisites);for(int i = 0; i < numCourses; i++) {DFS(i); // 防止有些孤立的结点遍历不到}return !hasCycle; // 没有循环依赖 就是可以完成学习}void buildGraph(int n, vector<vector<int>>& pre) {graph.resize(n);for(auto p: pre) {graph[p[1]].emplace_back(p[0]);}}void DFS(int node) {if(onPath[node]) hasCycle = true;if(visited[node] || hasCycle) return;visited[node] = true;onPath[node] = true;for(auto next: graph[node]) DFS(next);onPath[node] = false;}
};

BFS

我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的

判断环的依据 => 存在环时，始终会有结点入度降不到0，就加不到队列里去

class Solution {
public:vector<vector<int>> graph;vector<int> indegree;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {indegree.resize(numCourses, 0);buildGraph(numCourses, prerequisites);return BFS(numCourses);}void buildGraph(int n, vector<vector<int>>& pre) {graph.resize(n);for(auto p: pre) {graph[p[1]].emplace_back(p[0]);indegree[p[0]]++;}}bool BFS(int num) {queue<int> q;for(int i = 0; i < num; i++) {if(!indegree[i]) q.push(i);}int count = 0;while(!q.empty()) {int cur = q.front();q.pop();count++;for(auto next: graph[cur]) {indegree[next]--;if(!indegree[next]) q.push(next);}}return count == num;}
};

拓扑排序

210. 课程表 II - 力扣（LeetCode）

什么叫做拓扑排序：

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的

 抽象出题目中需要的逻辑：

如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；

反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

但是我们这道题和拓扑排序有什么关系呢？

其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序

怎么用算法实现拓扑排序：

对于DFS而言：后序遍历的结果就是拓扑排序

对于BFS而言：按照入度下降梯度相对排序

DFS

关于后序结果是否逆序 => 在于建图函数的写法问题

class Solution {
public:vector<vector<int>> graph;vector<bool> onPath;vector<bool> visited;bool hasCycle = false;vector<int> ans;vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {onPath.resize(numCourses);visited.resize(numCourses);buildGraph(numCourses, prerequisites);for(int i = 0; i < numCourses; i++) {DFS(i);}reverse(ans.begin(), ans.end());if(hasCycle) return {};else return ans;}void buildGraph(int n, vector<vector<int>>& pre) {graph.resize(n);for(auto p: pre) {graph[p[1]].emplace_back(p[0]);}}void DFS(int now) {if(onPath[now]) hasCycle = true;if(hasCycle || visited[now]) return;visited[now] = true;onPath[now] = true;for(auto next: graph[now]) DFS(next);ans.emplace_back(now);onPath[now] = false;}
};

BFS

vector<int> indegree => 索引是结点，存放的值是该结点的入度数

class Solution {
public:vector<vector<int>> graph;vector<int> indegree;vector<int> ans;vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {buildGraph(numCourses, prerequisites);if(BFS(numCourses)) return ans;else return {};}void buildGraph(int n, vector<vector<int>>& pre) {indegree.resize(n);graph.resize(n);for(auto p: pre) {graph[p[1]].emplace_back(p[0]);indegree[p[0]]++;}}bool BFS(int num) {queue<int> q;for(int i = 0; i < num; i++) {if(!indegree[i]) q.push(i);}while(!q.empty()) {int cur = q.front();q.pop();ans.emplace_back(cur);for(auto next: graph[cur]){indegree[next]--;if(!indegree[next]) q.push(next);}}return ans.size() == num;}
};