算法总结-图

最小生成树问题

「Kruskal 算法」是求解「加权无向图」的「最小生成树」的一种算法。

1. 所有边从小到大排序
2. 依次加入最小生成树中，形成环则跳过
3. 知道选择N-1条边为止

LC. 1584

三元组：stl的对类，用户定义结构

class Solution {
public:
    vector<int> fa;
    int find(int x) {
        if ( x != fa[x] ) 
            fa[x] = find(fa[x]);
        return fa[x];
    }
    void unify(int x, int y) {
        fa[find(x)] = find(y);
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto dist = [&](int x, int y) {
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        int n = points.size();
        fa.resize(n);
        for ( int i = 0; i < n; i++ ) {
            fa[i] = i;
        }
        vector<pair<int, pair<int, int>>> edges;
        for ( int i = 0; i < n; i++ ) {
            for ( int j = i + 1; j < n; j++ ) {
                edges.push_back(make_pair(dist(i,j), make_pair(i, j)));
            }
        }
        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b){
            return a.first < b.first;
        });
        // sort(edges.begin(), edges.end()); 也可以
        int ans = 0;
        for ( auto& [len, pair] : edges ) {
            if (find(pair.first) != find(pair.second)) {
                ans += len;
                unify(pair.first, pair.second);
            } 
        }
        return ans;
    }
};

三元组写成用户定义

class Solution {
public:
    vector<int> fa;
    int find(int x) {
        if ( x != fa[x] ) 
            fa[x] = find(fa[x]);
        return fa[x];
    }
    void unify(int x, int y) {
        fa[find(x)] = find(y);
    }
    struct Edge { // 注意此处
        int len, x, y;
        Edge(int len, int x, int y) : len(len), x(x), y(y) {}
    };
    int minCostConnectPoints(vector<vector<int>>& points) {
        
        auto dist = [&](int x, int y) {
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        int n = points.size();
        fa.resize(n);
        for ( int i = 0; i < n; i++ ) {
            fa[i] = i;
        }
        // vector<pair<int, pair<int, int>>> edges;
        vector<Edge> edges;
        for ( int i = 0; i < n; i++ ) {
            for ( int j = i + 1; j < n; j++ ) {
                // edges.push_back(make_pair(dist(i,j), make_pair(i, j)));
                edges.emplace_back(dist(i, j), i, j);  // 注意此处
            }
        }
        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b){ 
            return a.len < b.len;  // 注意此处
        });
        int ans = 0;
        int num = 1;
        for ( auto& [len, x, y] : edges ) {
            // cout << len << " " << pair.first << " " << pair.second << endl;
            if (find(x) != find(y)) {
                ans += len;
                num++;
                if ( num == n ) break;
                unify(x, y);
            } 
        }
        return ans;
    }
};

并查集写成一个类

class UnionFind {
    vector<int> fa;
public: 
    UnionFind (int n) {
        fa.resize(n);
        for ( int i = 0; i < n; i ++ ) fa[i] = i;
    }
    int find(int x) {
        if ( x != fa[x] ) 
            fa[x] = find(fa[x]);
        return fa[x];
    }
    void unify(int x, int y) {
        fa[find(x)] = find(y);
    }
};
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto dist = [&](int x, int y) {
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        int n = points.size();
        UnionFind uf(n);
        vector<pair<int, pair<int, int>>> edges;
        for ( int i = 0; i < n; i++ ) {
            for ( int j = i + 1; j < n; j++ ) {
                edges.push_back(make_pair(dist(i,j), make_pair(i, j)));
            }
        }
        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b){
            return a.first < b.first;
        });
        int ans = 0, num = 1;
        for ( auto& [len, pair] : edges ) {
            if (uf.find(pair.first) != uf.find(pair.second)) {
                ans += len;
                if ( ++num == n ) break;
                uf.unify(pair.first, pair.second);
            } 
        }
        return ans;
    }
};

时间复杂度：O(n2 log(n))，其中 n 是节点数。一般Kruskal 是O(mlogm) 的算法，但本题中m=n2

空间复杂度：O(n^2)，其中 n是节点数。并查集使用 O(n)的空间，边集数组需要使用 O(n^2) 的空间。

---

prim算法

在「Kruskal 算法」中，我们通过增加边数来扩大「最小生成树」；适用于稀疏图

在「Prim 算法」中，我们通过增加顶点来扩大「最小生成树」。适用于稠密图

「切分定理」指的是：在一幅连通加权无向图中，给定任意的切分，如果有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树中的一条边。

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto dist = [&](int x, int y) {
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        int n = points.size();
        vector<bool> visited(n, false);
        visited[0] = true;
        vector<int> mindist(n, 0); // 生成树 到 各点的最短距离
        for(int i = 1; i < n; i++)
        {
            mindist[i] = dist(0, i);
        }
        mindist[0] = 0;
        int cost = 0;
        for(int k = 0; k < n-1; k++) // n-1次
        {
            int pos = -1;
            int minn = INT_MAX;
            for(int i = 0; i < n; i++)
            {
                if(!visited[i] && minn > mindist[i])
                {
                    minn = mindist[i]; // 找最小值
                    pos = i;
                }
            }
            cost += minn;
            visited[pos] = true;
            mindist[pos] = 0;
            for(int i = 0; i < n; i++)
            {
                if(!visited[i] && dist(pos, i) < mindist[i])
                    mindist[i] = dist(pos, i);
            }
        }
        return cost;
    }
};

Dijkstra 算法/ˈdɛɪkstra/.

「Dijkstra 算法」解决的是加权有向图「单源最短路径」问题，其中该图的所有权重必须为非负数。

LC 743 网络延迟时间

将所有节点分成两类：已确定从起点到当前点的最短路长度的节点，以及未确定从起点到当前点的最短路长度的节点（下面简称「未确定节点」和「已确定节点」）。

每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。

用节点 AA「更新」节点 BB 的意思是，用起点到节点 AA 的最短路长度加上从节点 AA 到节点 BB 的边的长度，去比较起点到节点 BB 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。

这里暗含的信息是：每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定。

可以这样理解，因为我们已经用了每一个「已确定节点」更新过了当前节点，无需再次更新（因为一个点不能多次到达）。而当前节点已经是所有「未确定节点」中与起点距离最短的点，不可能被其它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf = INT_MAX / 2;
        vector<vector<int>> dist(n , vector<int>(n , inf));
        for ( auto& t : times ) {
            int x = t[0] - 1;
            int y = t[1] - 1;
            dist[x][y] = t[2];
        }

        vector<int> mindist(n, inf);
        mindist[k - 1] = 0;  // 初始化

        vector<bool> visited(n, false);
        for ( int num = 0; num < n; num++ ) {
            int pos = -1;
            int minn = INT_MAX;
            for ( int i = 0; i < n; i++ ) {
                if ( !visited[i] && ( minn > mindist[i] ) ) {  // 找最小值
                    minn = mindist[i];
                    pos = i;
                }
            }
            visited[pos] = true;

            for ( int i = 0; i < n; i++ ) {
                mindist[i] = min(mindist[i], mindist[pos] + dist[pos][i] );
            }
        }
        int ans = *max_element(mindist.begin(), mindist.end());
        return ans == inf ? -1 : ans;
    }
};

---

FLOYD

复杂度为O(n3 ) 的「多源汇最短路」算法 Floyd 算法进行求解，同时使用「邻接矩阵」来进行存图，可以得到「从任意起点出发，到达任意点。

A1,0 = 6，path 1,0 = 3; path 3,0 = 2; path 2,0 = -1 直接相连

void  printPath (int i, int j, int path[][max]) { // i = 1, j = 0 
    if ( path[i][j] == -1 ) { /*直接输出*/ };
    else {
        int v = path[i][j]; // path[1][0] = 3
        printPath(i, mid, path);  // path[1][3]
        printPath(mid, j, path);  // path[3][0]
    }
}

// 外循环v为中间变量，Av，Pathv修改为v;内循环i，j ≠ v
for ( int v = 0; v < n; v++ ) 
    for ( int i = 0; i < n; i++ ) 
        for ( int j = 0; j < n; j++ ) 
            if ( A[i][j] > A[i][v] + A[v][j] ) {
                A[i][j] = A[i][v] + A[v][j];
                path[i][j] = v;
            }

---

Bellman-Ford 算法（单源最短路径）

「Bellman-Ford 算法」虽然不能检测到「负权环图」的最短路径，但是它能检测到「图」中是否存在「负权环」。

定理一：在一个有 N 个顶点的「非负权环图」中，两点之间的最短路径最多经过 N-1 条边。

定理二：「负权环」没有最短路径。环上 边权 为正为负，正权环图有最短距离。

DJ算法关注的是点，B-F算法关注的是边，动态规划

// LC 743
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> dist(n); // 存图方式
        for ( auto& t : times ) {
            int x = t[0] - 1;
            int y = t[1] - 1;
            dist[x].push_back( make_pair(y, t[2]) );
        }

        vector<int> mindist(n, INT_MAX); // |V| - 1 次
        mindist[k - 1] = 0;  // 初始化
        bool finished;
        for ( int k = 0; k < n - 1; k++ ) {// n - 1 次
            for ( int u = 0; u < n; u++ ) { // 前一节点
                if ( mindist[u] == INT_MAX ) continue;
                for ( auto& [ v, weight ] : dist[u] ) {
                    long newV = mindist[u] + weight;
                    if ( newV < mindist[v] ) {
                        mindist[v] = newV;
                        finished = false;
                    }
                }
            }
            if ( finished ) break;
        }
        int ans = *max_element(mindist.begin(), mindist.end());
        return ans == INT_MAX ? -1 : ans;
    }
};

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> dist(n); // 存图方式
        for ( auto& t : flights ) {
            int x = t[0];
            int y = t[1];
            dist[x].push_back( make_pair(y, t[2]) );
        }
        vector<int> mindist(n, INT_MAX); // |V| - 1 次
        mindist[src] = 0;  // 初始化
        for ( int kk = 0; kk < k + 1; kk++ ) {
            vector<int> newdist(mindist);
            for ( int u = 0; u < n; u++ ) { // 前一节点
                if ( mindist[u] == INT_MAX ) continue;
                for ( auto& [ v, weight ] : dist[u] ) {
                    long newV = mindist[u] + weight;
                    if ( newV < newdist[v] ) {
                        newdist[v] = newV;
                    }
                }
            }
            mindist.assign(newdist.begin(), newdist.end());
        }
        return mindist[dst] == INT_MAX ? -1 : mindist[dst];
    }
};

---

基于「队列」优化的 Bellman-Ford 算法 — SPFA 算法 Shortest Path Faster Algorithm

「SPFA 算法」主要是通过「队列」来维护我们接下来要遍历边的起点，而不是「Bellman Ford」算法中的任意还没有遍历过的边。每次只有当某个顶点的最短距离更新之后，并且该顶点不在「队列」中，我们就将该顶点加入到「队列」中。一直循环以上步骤，直到「队列」为空，我们就可以终止算法。此时，我们就可以得到「图」中其他顶点到给定顶点的最短距离了。

前缀树

#include <bits/stdc++.h>
using namespace std;

class Trie
{
public:
    vector<Trie *> children;
    bool isEnd;
    Trie() : children(26), isEnd(false) {}
    Trie *searchPrefix(string prefix)
    {
        Trie *node = this;
        for (char ch : prefix)
        {
            ch -= 'a';
            if (node->children[ch] == nullptr)
            {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }
    void insert(string word)
    {
        Trie *node = this;
        for (char ch : word)
        {
            ch -= 'a';
            if (node->children[ch] == nullptr)
            {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(string word)
    {
        Trie *node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }
    bool startsWith(string prefix)
    {
        return this->searchPrefix(prefix) != nullptr;
    }
};

void bfs(Trie *trie, string s)
{
    if (trie->isEnd)
        cout << s << endl;
    for (int i = 0; i < 26; i++)
    {
        if (trie->children[i] != nullptr)
        {
            string st = s;
            st += (i + 'a');
            bfs(trie->children[i], st);
        }
    }
}

int main()
{
    int N;
    cin >> N;
    string s;
    cin.ignore();
    Trie *trie1 = new Trie();
    for (int i = 0; i < N; i++)
    {
        getline(cin, s);
        trie1->insert(s);
    }
    getline(cin, s);
    if (trie1->startsWith(s)) //有这个前缀
    {
        bfs(trie1->searchPrefix(s), s);
    }
    else
    {
        //没这个前缀
        cout << "no" << endl;
        system("pause");
        return 0;
    }
    system("pause");
    return 0;
}