One,shortest pathconcern
1. Single-source shortest path
Depth or breadth-first algorithm that accesses all depth traversal paths or breadth-first paths from the starting point, then there are multiple paths to the end node, and the one with the shortest path weights is the shortest path.
-
void dfs(int cur, int dst){
-
if(minPath < dst) return;//The current path is larger than the previous shortest path, so there is no need to go further.
-
if(cur == n){//critical condition
-
if(minPath > dst) minPath = dst;
-
return;
-
}
-
else{
-
int i;
-
for(i = 1; i <= n; i++){
-
//Guarantee that paths exist between nodes and have not been accessed, non-existing node paths are set to infinity 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、Multi-source shortest path
Floyd-Warshall algorithm, basic idea: at first only allow transit through vertex #1, next only allow transit through vertices #1 and #2 ...... Allow transit through all vertices from 1 to n to constantly and dynamically update the shortest distance between any two points. That is, find the shortest distance from vertex i to vertex j through only the first k points.
-
//Using Floyd's algorithm
-
int k; //Join nodes k in turn
-
for(k = 1; k <= n; k++){
-
for(i = 1; i <= n; i++){
-
for(j = 1; j <= n; j++){
-
//Guarantees that edges exist, that non-existing edge weights are set to infinity inf, and that shorter paths exist
-
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];
-
}
-
}
-
}
II. Determine if there is a ring in the diagram
Depth or breadth-first algorithms that determine whether duplicate searched nodes are encountered during the search.
Ideas: adjacency table to build a graph, determine whether the graph has a ring, if there is a ring does not satisfy the question
-
class Solution {
-
public:
-
bool dfs(int i,vector<vector<int>>&adjacent,vector<int>&flag){
-
if(flag[i]==-1) return true; //The current node has already been visited, no need to repeat the search
-
if(flag[i]==1) return false; //Repeated in one round of dfs, i.e., with rings
-
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);
-
//Neighbor-joining table construction
-
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;
-
}
-
};
III. Concurrent sets
Solving connectivity problems.
-
class DisjointSetUnion {
-
private:
-
//f i.e., save the parent array of the node, rank in order to balance the inserted nodes
-
vector<int> f, rank;
-
int n;
-
public:
-
//initialization
-
DisjointSetUnion(int _n) {
-
n = _n;
-
(n, 1);
-
(n);
-
for (int i = 0; i < n; i++) {
-
f[i] = i;
-
}
-
}
-
//find
-
int find(int x) {
-
return f[x] == x ? x : f[x] = find(f[x]);
-
}
-
//parallel operation
-
void unionSet(int x, int y) {
-
int fx = find(x), fy = find(y);
-
if (fx == fy) {
-
return;
-
}
-
//Let the low number of nodes join to the high number of nodes in the concatenation set
-
if (rank[fx] < rank[fy]) {
-
swap(fx, fy);
-
}
-
rank[fx] += rank[fy];
-
f[fy] = fx;
-
}
-
};
IV. The minimum spanning tree problem
1. Prim (Prim) algorithm
Basic Idea: Primm's algorithm divides the vertices into two classes when finding the minimum spanning tree, one class is already included in the tree during the search (assumed to be class A), and the rest is the other class (assumed to be class B). For a given connected network, all vertices in the starting state are categorized into class B. In finding the minimum spanning tree, any vertex is selected as the starting point and moved from class B to class A. Then the vertex with the smallest weight between the vertices in class B and those in class A is found (all edges between all the vertices in A and B are computed), and is moved from class B to class A, and so on until there are no vertices in class B. The minimum spanning tree is then used as the starting point of the minimum spanning tree. The vertices and edges traveled are the minimum spanning tree of the connected graph.
2. Kruskal (Kruskal) algorithm and parallel checking set
Idea: Sort all distances, then scan and update based on whether the scanned edge is in a connected block.
-
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;
-
}
-
};