一、最短路径问题
1、单源最短路径
深度或广度优先算法，从起点开始访问所有深度遍历路径或广度优先路径，则到达终点节点的路径有多条，取其中路径权值最短的一条则为最短路径。
-
void dfs(int cur, int dst){
-
if(minPath < dst) return;//当前走过路径大于之前最短路径，没必要再走下去
-
if(cur == n){//临界条件
-
if(minPath > dst) minPath = dst;
-
return;
-
}
-
else{
-
int i;
-
for(i = 1; i <= n; i++){
-
//保证节点间存在路径，且没有被访问过，不存在的节点路径设置为无穷大inf
-
if(edge[cur][i] != inf && edge[cur][i] != 0 && mark[i] == 0){
-
mark[i] = 1;
-
dfs(i, dst+edge[cur][i]);
-
mark[i] = 0;
-
}
-
}
-
return;
-
}
-
}
2、多源最短路径
弗洛伊德（Floyd-Warshall）算法，基本思想：最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转......允许经过1~n号所有顶点进行中转，来不断动态更新任意两点之间的最短路程。即求从i号顶点到j号顶点只经过前k号点的最短路程。
-
//使用弗洛伊德算法
-
int k; //依次加入节点k
-
for(k = 1; k <= n; k++){
-
for(i = 1; i <= n; i++){
-
for(j = 1; j <= n; j++){
-
//保证边存在，不存在的边权值设为无穷大inf，以及存在更短路径
-
if(edge[i][k] < inf && edge[k][j] < inf && edge[i][j] > edge[i][k] + edge[k][j])
-
edge[i][j] = edge[i][k] + edge[k][j];
-
}
-
}
-
}
二、判断图中是否有环
深度或广度优先算法，在搜索过程中判断是否遇到重复搜索的节点。
思路：邻接表建图，判断图中是否有环，有环的话就不满足题意
-
class Solution {
-
public:
-
bool dfs(int i,vector<vector<int>>&adjacent,vector<int>&flag){
-
if(flag[i]==-1) return true; //当前节点已被访问过，无需重复搜索
-
if(flag[i]==1) return false; //一轮dfs中重复，即有环
-
flag[i]=1;
-
for(auto j:adjacent[i]){
-
if(!dfs(j,adjacent,flag))
-
return false;
-
}
-
flag[i]=-1;
-
return true;
-
}
-
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
-
vector<vector<int>>adjacent(numCourses);
-
vector<int>flag(numCourses);
-
//邻接表建图
-
for(int i=0;i<prerequisites.size();i++){
-
adjacent[prerequisites[i][0]].push_back(prerequisites[i][1]);
-
}
-
for(int i=0;i<numCourses;i++) {
-
if(!dfs(i,adjacent,flag))
-
return false;
-
}
-
return true;
-
}
-
};
三、并查集
解决连通性问题。
-
class DisjointSetUnion {
-
private:
-
//f即保存节点的父数组，rank为了平衡插入的节点
-
vector<int> f, rank;
-
int n;
-
public:
-
//初始化
-
DisjointSetUnion(int _n) {
-
n = _n;
-
(n, 1);
-
(n);
-
for (int i = 0; i < n; i++) {
-
f[i] = i;
-
}
-
}
-
//查找
-
int find(int x) {
-
return f[x] == x ? x : f[x] = find(f[x]);
-
}
-
//并操作
-
void unionSet(int x, int y) {
-
int fx = find(x), fy = find(y);
-
if (fx == fy) {
-
return;
-
}
-
//让节点数少的加入到节点数多的并查集中
-
if (rank[fx] < rank[fy]) {
-
swap(fx, fy);
-
}
-
rank[fx] += rank[fy];
-
f[fy] = fx;
-
}
-
};
四、最小生成树问题
1、Prim(普利姆)算法
基本思想：普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在树中的（假设为 A 类），剩下的是另一类（假设为 B 类）。对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点(计算出来A、B所有顶点间的全部边)，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。
2、Kruskal(克鲁斯卡尔)算法和并查集
思路： 将所有距离排序，然后扫描，根据扫描到的边是否在连通块中进行更新。
-
class DisjointSetUnion {
-
private:
-
vector<int> f, rank;
-
int n;
-
-
public:
-
DisjointSetUnion(int _n) {
-
n = _n;
-
(n, 1);
-
(n);
-
for (int i = 0; i < n; i++) {
-
f[i] = i;
-
}
-
}
-
-
int find(int x) {
-
return f[x] == x ? x : f[x] = find(f[x]);
-
}
-
-
bool unionSet(int x, int y) {
-
int fx = find(x), fy = find(y);
-
if (fx == fy) {
-
return false;
-
}
-
if (rank[fx] < rank[fy]) {
-
swap(fx, fy);
-
}
-
rank[fx] += rank[fy];
-
f[fy] = fx;
-
return true;
-
}
-
};
-
-
struct Edge {
-
int len, x, y;
-
Edge(int len, int x, int y) : len(len), x(x), y(y) {
-
}
-
};
-
-
class Solution {
-
public:
-
int minCostConnectPoints(vector<vector<int>>& points) {
-
auto dist = [&](int x, int y) -> int {
-
return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
-
};
-
int n = points.size();
-
DisjointSetUnion dsu(n);
-
vector<Edge> edges;
-
for (int i = 0; i < n; i++) {
-
for (int j = i + 1; j < n; j++) {
-
edges.emplace_back(dist(i, j), i, j);
-
}
-
}
-
sort((), edges.end(), [](Edge a, Edge b) -> int { return < ; });
-
int ret = 0, num = 1;
-
for (auto& [len, x, y] : edges) {
-
if ((x, y)) {
-
ret += len;
-
num++;
-
if (num == n) {
-
break;
-
}
-
}
-
}
-
return ret;
-
}
-
};