1. 拓扑排序

leetcode207

这道题对应拓扑排序，有向图是否有环的问题

1.1 BFS（广度优先搜索）

第一次做法

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 0.初始化准备unordered_set<int> temp;vector<unordered_set<int>> adj_list(numCourses, temp); //先修课程->所有后续课程vector<unordered_set<int>> inv_adj_list(numCourses, temp); //后续课程->所有先修课程unordered_set<int> learned; //已学习课程// 1.建图for (auto &m : prerequisites) {inv_adj_list[m[0]].insert(m[1]);adj_list[m[1]].insert(m[0]);}// 2.模拟学习过程queue<int> q;while (1) {// 2.1 找出未学习且可学习的课程，入队for (int i=0; i<inv_adj_list.size(); ++i) {if (0 == learned.count(i) && inv_adj_list[i].empty()) {q.push(i);learned.insert(i);}}// 2.2 若没有可学习的课程则退出if (q.empty()) break;// 2.3 更新inv_adj_listwhile (!q.empty()) {int curr = q.front();q.pop();for (auto &m : adj_list[curr]) {if (0 == learned.count(m)) {inv_adj_list[m].erase(curr);}}}}// 3.判断是否能够完成return learned.size() == numCourses;}
};

空间复杂度： O(E)，E为边的数量

直接使用prerequisites， 可以不使用inv_adj_list，节省空间，第二次做法如下：

class Solution {
private:public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 1.初始化图vector<vector<int>> adj_list(numCourses); //先修课程->后续课程vector<int> indeg(numCourses, 0); //入度数组queue<int> q;unordered_set<int> learned;for (auto &m : prerequisites) {++indeg[m[0]];adj_list[m[1]].push_back(m[0]);}// 2.模拟学习while (1) {// 2.1 入度为0入队for (int i=0; i<indeg.size(); ++i) {if (0 == learned.count(i) && 0 == indeg[i]) {q.push(i);learned.insert(i);}}// 2.2 队为空，退出循环，否则将队的尺寸加入结果if (q.empty()) {break;}// 2.3 出队，同时将该课程的后续课程的入度减1while (!q.empty()) {int curr = q.front();q.pop();for (auto &m : adj_list[curr]) {--indeg[m];}}}// 3.判断结果return learned.size() == numCourses;}
};

更好的解法，拓扑排序

无向图

有向图（可以分为有向无环图和有向有环图）

 新的存储方法：

出度，入度

可以使用入度数组，记录每个结点的入度（BFS）

也可以使用出度数组，记录每个结点的

答案中的方法是在出队的时候更改入度时，顺便判断入度是否为0，若是压入队列，可以省略上面搜索入度为0的步骤，提升速度

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 1.初始化图vector<vector<int>> adj_list(numCourses); //先修课程->后续课程vector<int> indeg(numCourses); //入度数组for (const auto &m : prerequisites) {++indeg[m[0]];adj_list[m[1]].push_back(m[0]);}// 2.首次生成队列queue<int> q;for (int i=0; i<indeg.size(); ++i) {if (0 == indeg[i]) q.push(i);}// 3.主循环int learned = 0;while (!q.empty()) {// 3.1 出队，记录结果int curr = q.front();q.pop();++learned;// 3.2 更改后续课程的入度，若入度为0，压入队列for (const auto &m : adj_list[curr]) {--indeg[m];if (0 == indeg[m]) q.push(m);}}// 4.返回结果return learned == numCourses;}
};

 时间复杂度O(V+E)，V为课程数量，对应结点数，E对应先修要求，对应边，因为无边的结点和所有的边都会被处理一次，所以时间复杂度为O(V+E)

空间复杂度，主要是adj_list和indeg，前一个对应边的数量，后一个对应结点数量，所以空间复杂度是O(V+E)

这种解法可以说是BFS，也可以说是Kahn算法，这是一种贪心算法的引申

这道题当然也可以采用DFS的思路，不过BFS更加直观自然

1.2 DFS（深度优先搜索）

思路：dfs的思想或者说Kahn算法，就是先一条路走到黑，它更像是判断有向图是否有环，从这个逻辑出发，每个dfs完成的是判断从该节点出发是否存在环，对于一个节点有3种状态，使用visited存储：

• visited = 0，未搜索
• visited = 1, 搜索中
• visited = 2, 已搜索

若搜索到该节点时已搜索则不处理直接返回，若是搜索中说明出现了环，设置结果后返回，若是未搜索，首先将当前结点的状态设置为搜索中，然后对该结点的所有下一个结点继续运行dfs，每次运行时都要判断valid是否为true，若为false，则说明有环，直接返回

而在主函数中做初始化的工作，还有就是对所有的结点都使用dfs进行处理

class Solution {
private:// 需要的变量vector<vector<int>> adj_list; //先修课程->所有后续课程vector<int> visited; //记录结点状态，0为未搜索，1为搜索中，2为已搜索，如果搜索时发现一个结点是搜索中的说明有环bool valid = true; //记录结果,初始为能够完成课程，若存在环说明不能完成，设置为false// 判断从一个结点出发是否有环void dfs (int i) {if (2 == visited[i]) return; //1.该结点为已搜索，直接返回if (1 == visited[i]) { //2.该结点为搜索中，存在环，设置后返回valid = false;return;}//3.该结点为未搜索，继续搜索它的后续结点visited[i] = 1; //设置为搜索中for (auto &m : adj_list[i]) { dfs(m);if (!valid) return;}visited[i] = 2; //4.设置为已搜索}
public:// 使用dfs解决判断有向图是否有环的问题bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 1.初始化准备visited.resize(numCourses);adj_list.resize(numCourses);for (auto &m : prerequisites) {adj_list[m[1]].push_back(m[0]);}// 2.正式处理for (int i=0; i<numCourses; ++i) {if (!valid) break;dfs(i);}// 3.返回结果return valid;}
};

时间复杂度：首先会遍历边，复杂度为O(E)，而对于dfs处理，最多对于每一个结点都会处理一次，复杂度是O(V)，合起来就是O(E+V)

空间复杂度方面adj_list和visited合起来就是O(E+V)，递归栈的深度最多不会超过边的个数，所以合起来是O(E+V)

2. 岛屿的数量

思路：无向图，邻接矩阵，BFS/DFS，图的遍历，辅助队列

遍历二维网格，发现一块陆地，则沉没一座岛屿（使用队列实现），计数，返回结果

class Solution {
public:int numIslands(vector<vector<char>>& grid) {// 0.异常处理if (grid.size() == 0) return 0;// 1.初始化准备// 1.1 运动数组vector<pair<int, int>> moves;moves.push_back(make_pair(0,-1));moves.push_back(make_pair(0,1));moves.push_back(make_pair(-1,0));moves.push_back(make_pair(1,0));queue<pair<int, int>> q;int ans = 0;int rows = grid.size();int cols = grid[0].size();// 2.遍历网格for (int i=0; i<rows; ++i) {for (int j=0; j<cols; ++j) {if ('0' == grid[i][j]) continue;q.push(make_pair(i, j));grid[i][j] = '1';++ans;// 2.1 每次使用队列，处理（沉没）一座岛屿，计数while (!q.empty()) {auto temp = q.front();q.pop();// 判断四周是否是岛屿for (auto &m : moves) {// 判断边界与水域int new_i = m.first + temp.first;int new_j = m.second + temp.second;if (new_i >= rows || new_i < 0 || new_j >= cols || new_j < 0 || grid[new_i][new_j] == '0') continue;q.push(make_pair(new_i, new_j));grid[new_i][new_j] = '0';}}}}// 3.返回结果return ans;}
};

 时间复杂度O(E)，E是边的数量，每条边会被处理一次，所以时间复杂度时O(E)

空间复杂度O(min(M,N))，M是行数，N是列数

3. 有效的数独

4. 省份数量

leetcode547

思路：使用BFS，使用邻接表，队列，标记数组等数据结构

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {if (0 == isConnected.size()) return 0;// 1.初始化准备vector<vector<int>> adj_list(isConnected.size()); //邻接表vector<bool> visited(isConnected.size(), false); //标记结点是否被访问过int ans = 0; //最终答案for (int i=0; i<isConnected.size(); ++i) {for (int j=0; j<isConnected[0].size(); ++j) {if (j == i) continue; //去掉本身if (1 == isConnected[i][j]) adj_list[i].push_back(j);}}// 2.遍历邻接表queue<int> q;for (int i=0; i<adj_list.size(); ++i) {if (visited[i]) continue;else {q.push(i);++ans;visited[i] = true;// 将连通的结点遍历完while (!q.empty()) {int temp = q.front();q.pop();for (auto &m : adj_list[temp]) {if (!visited[m]) {q.push(m);visited[m] = true;}}}}}return ans;   }
};

 时间复杂度O(E^2)+O(E)，总的是O(E^2)

空间复杂度O(V+E)

可以进一步优化，直接使用邻接矩阵，不使用邻接表，节省空间

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {if (0 == isConnected.size()) return 0;// 1.初始化准备vector<bool> visited(isConnected.size(), false); //标记结点是否被访问过int ans = 0; //最终答案// 2.遍历邻接表queue<int> q;for (int i=0; i<isConnected.size(); ++i) {if (visited[i]) continue;else {q.push(i);++ans;visited[i] = true;// 将连通的结点遍历完while (!q.empty()) {int temp = q.front();q.pop();for (int j=0; j<isConnected[temp].size(); ++j) {if (!visited[j] && isConnected[temp][j] == 1) {q.push(j);visited[j] = true;}}}}}return ans;   }
};

 时间复杂度O(E)，总的是O(E)

空间复杂度O(V)，V为节点数量，E是边的数量

5. 最小路径搜索

实现参考geeksforgeeks实现

所需数据结构：

使用邻接表存放图vector<vector<pair<int, int>>> adj

需要实时更新未标记结点中到达起点的距离最小的结点，可以用set<pair<int, int>> setds，pair指的是weight, vertex，set底层是红黑树，红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。setds存放的信息是根据目前已经知道的信息，未标记的结点距离起始点的最短距离。

需要最短路径中当前结点的上一个结点, 可以用vector<int> last

还需要一个vector<int> 来存放跟踪目前信息，当前结点到起点的最短距离

注意这里的标记的意思是该结点到起始结点的最小距离已经知道了

思路：

1. 每次从setds取出最小元素，对应未标记的结点中距离起始点最近的结点，然后把它从setds中删除

2.遍历该结点相邻的边，如果发现通过这些边到达的结点的最短路径（存放在dist中）可以更小，则更新dist, last以及setds

#include <bits/stdc++.h>
using namespace std;/*** @brief 生成邻接表* @param edges 边 [src, dst, weight]* @param adj 邻接表*/
void GenerateAdjList(vector<vector<int>> &edges, vector<vector<pair<int, int>>> &adj) {// 注意无向图，需要插入两条边for (auto &m : edges) {adj[m[0]].push_back(make_pair(m[1],m[2]));adj[m[1]].push_back(make_pair(m[0], m[2]));}
}/*** @brief 求src到dst的最短距离和对应的路径* @param edges 所有边的信息* @param src 源结点* @param dst 目标结点* @param path 最短路径信息* @return 最短路径长度*/
int ShortestPath(vector<vector<pair<int, int>>> &adj, int count, int src, int dst, vector<int> &path) {// 1.初始化准备set<pair<int, int>> setds; //pair is <weight, vertex>，用于快速找到未标记的距离起点最近的结点vector<int> dist(count, INT_MAX); //存放距离信息, vertex -> distancevector<int> last(count); //存放最短路径中该结点的上一个结点// 2.源结点设置setds.insert(make_pair(0, src));dist[src] = 0;last[src] = 0;// 3.正式处理while (!setds.empty()) {// 3.1 取出未标记的距离起点最近的结点auto shortest = *(setds.begin());setds.erase(setds.begin());int u = shortest.second;// 3.2 遍历最近点的边for (auto &i : adj[u]) {int v = i.first;int weight = i.second;// 更新dist和setdsif (dist[v] > dist[u] + weight) {// 如果不是第一次，则删除setds中原来的元素if (dist[v] != INT_MAX) {setds.erase(setds.find(make_pair(dist[v], v)));}dist[v] = dist[u] + weight;last[v] = u;setds.insert(make_pair(dist[v], v));}}}// 4.求出最短路径int curr = dst;path.push_back(dst);while (curr != src) {path.push_back(last[curr]);curr = last[curr];}reverse(path.begin(), path.end()); //反转路径return dist[dst];
}int main() {vector<vector<int>> edges;edges.push_back(vector<int>{0, 1, 4});edges.push_back(vector<int>{0, 7, 8});edges.push_back(vector<int>{1, 2, 8});edges.push_back(vector<int>{1, 7, 11});edges.push_back(vector<int>{2, 3, 7});edges.push_back(vector<int>{2, 8, 2});edges.push_back(vector<int>{2, 5, 4});edges.push_back(vector<int>{3, 4, 9});edges.push_back(vector<int>{3, 5, 14});edges.push_back(vector<int>{4, 5, 10});edges.push_back(vector<int>{5, 6, 2});edges.push_back(vector<int>{6, 7, 1});edges.push_back(vector<int>{6, 8, 6});edges.push_back(vector<int>{7, 8, 7});// 生成邻接表int count = 9;vector<vector<pair<int, int>>> adj(count); //dst,weightGenerateAdjList(edges, adj);// 生成最短路径vector<int> shortest_path;int length = ShortestPath(adj, count, 0, 4, shortest_path);for (auto &m : shortest_path) {cout << m << " ";}cout << endl;cout << "Total length: " << length << endl;return 0;
}

时间复杂度O(ElogV)，因为对每条边都有常量级的处理操作，每次操作比如往set插入元素，或者删除元素的复杂度为O(logV)，所以最终的时间复杂度为O(ElogV)

空间复杂度为O(E+V)，其中E是边的数量，V是结点的数量 

相关题目：leetcode743

class Solution {
private:void shortestTime(vector<vector<pair<int, int>>> &adj_list, int src, vector<int> &times) {// 1.初始化准备set<pair<int, int>> setts; //pair是[w, v]setts.insert(make_pair(0, src));times[src] = 0;// 2.正式处理while (!setts.empty()) {// 2.1 处理setts首元素,移除auto temp = *(setts.begin());setts.erase(setts.begin());int u = temp.second;// 2.2 处理首元素的所有下一个结点for (auto &m : adj_list[u]) {int v = m.first; //下一个结点int w = m.second; //到达下一个结点花费时间//若未标记结点存在更短路径则更新相应数据if (times[v] > times[u] + w) {//对于已经存在于setts中的结点需要先删除if (INT_MAX != times[v]) {setts.erase(setts.find(make_pair(times[v], v))); //注意先要找到迭代器}//更新times[v] = times[u] + w;setts.insert(make_pair(times[v], v));}}}}
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {// 1.初始化准备vector<vector<pair<int, int>>> adj_list(n); //pair指[v,w]vector<int> shortest_times(n, INT_MAX); //从结点到达该结点的最短时间for (auto &m : times) {adj_list[m[0]-1].push_back(make_pair(m[1]-1, m[2])); //注意题目中结点序号从1开始}// 2.求从k出发到达其他所有结点的最短时间shortestTime(adj_list, k-1, shortest_times);// 3.返回结果// 3.1 如果存在不可到达的结点，那么返回-1(可以通过shortest_times的元素最大值是否是INT_MAX来判断)// 3.2 所有最短时间的最大时间就是网络延迟时间int ans = *max_element(shortest_times.begin(), shortest_times.end());return ans == INT_MAX ? -1 : ans;}
};

时间复杂度O(ElogV)，空间复杂度O(E+V) 

6. A*算法

对Dijkstra算法的改造，启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。这种算法找出的路线，并不是最短路线。Dijkstra算法每次是从距离起点距离最小的结点出发，使用队列进行处理，而A*算法同时考虑到终点的距离，启发式地进行搜索。