图算法

Dijkstra算法

输入是一个图graph,返回是一个最短路径权重的数组。

思路：将dis的初始值出start之外设置为INT_MAX，start设置为0，然后将start加入到优先级队列中，依次将优先级队列中到start距离最小的节点cur弹出，看是否可以更新cur相邻节点next_node的dis值，如果出现下面next_cost < dis[edge.first]的情况，那么就表示next_node的值可以被更新，且新的最短距离是经过cur的，同时将next_node加入到优先级队列中。重复这个过程，最终得到的dis数组就是start到其他节点的距离。

// graph为输入的图，graph[i]为节点i的邻接表，pair.first为相邻的节点编号,pair.second为该边的权重
// start为起点
// n为图的节点个数
vector<int> Dijkstra(vector<vector<pair<int, int>>> &graph, int start, int n)
{
    vector<int> dis(n + 1, INT_MAX);   // 距离起点的距离数组,初始设置为INT_MAX,方便以后遍历到之后更新
    auto cmp = [](pair<int, int> &p1, pair<int, int> &p2) {return p1.second < p2.second;};
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);  // 使用优先级队列，pair.first为节点编号,pair.second到该节点的最小距离
    dis[start] = 0;
    pq.emplace(make_pair(start, 0));
    while(!pq.empty())
    {
        auto [id, cost] = pq.top();
        pq.pop();
        if(cost > dis[id])  
            continue;
        for(auto edge : graph[id])
        {
            int next_cost = edge.second + dis[id];
            if(next_cost < dis[edge.first])     // 如果下一个节点cost小于dis存储的值，更新dis并将其加入到优先级队列中
            {
                dis[edge.first] = next_cost;
                pq.emplace(make_pair(edge.first, next_cost));   // 该节点的cost更新之后，其相邻节点的cost可能也会因此更新
            }
        }
    }
    return dis;
}

Floyd算法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 用INF初始化那些无法直接到达的顶点对之间的距离
const int INF = 1e9;

// graph是二维数组, graph[i][j]表示i到j的距离，i到i的距离为0，若i没有到j的通路，则graph[i][j]为INF
void floydWarshall(vector<vector<int>>& graph) {
    int V = graph.size();
    
    // distances数组会存储最终的最短路径结果
    vector<vector<int>> distances = graph;
    
    // k是中间顶点的编号
    for (int k = 0; k < V; ++k) {
        // i是起点
        for (int i = 0; i < V; ++i) {
            // j是终点
            for (int j = 0; j < V; ++j) {
                // 如果i到k和k到j的路径长度之和小于直接i到j的路径长度，则更新i到j的路径长度
                if (distances[i][k] < INF && distances[k][j] < INF) {
                    distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }
        }
    }
    
    // 打印最短路径的结果
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (distances[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << distances[i][j] << " ";
            }
        }
        cout << "\n";
    }
}

int main() {
    // 示例图，使用邻接矩阵表示，INF表示两个顶点之间没有直接的路径
    std::vector<std::vector<int>> graph = {
        {0,   5, INF, 10},
        {5,   0,   3, INF},
        {INF, 3,   0,   1},
        {10, INF, 1,   0}
    };

    floydWarshall(graph);
    return 0;
}

Kruskal 最小生成树算法

思想：从图graph中每次选择一条最短的边e，若加入e之后不构成环，将e加入到最小生成树的结果中；重复上述步骤，一直到有n - 1条边为止（n为图的节点个数，因为n个节点不存在环的连通图中必定有n - 1条边）。

Kruskal算法步骤：

1. 将所有边按照权重从小到大排序
2. 初始化一个集合，并且把所有节点分别加入集合，每个节点都是单独一个集合。
3. 遍历排序后的边，将它们加入树中(如果边的两个节点不在同一个集合中)。
4. 最后得到的tree就是最小生成树。

这里实现KRUSKAL使用了并查集，并查集的概念与代码见并查集。

// graph[i] = [x, y, cost]，表示节点x和y之间有一条权值为cost的边
int Kruskal(int n, vector<vector<int>>& graph) 
{
    int count = 0;
    vector<vector<int>> res;
    sort(graph.begin(), graph.end(), [](const vector<int> &v1, const vector<int> v2) -> bool {return v1[2] < v2[2];});
    UF my_uf(n + 1);      // 定义并查集
    for(auto edge : graph)
    {
        int x = edge[0], y = edge[1], cost = edge[2];
        if(my_uf.isConnected(x, y))    // 若x，y已经连通那么不能把这条边加入到结果中
            continue;
        ++count;
        my_uf.unionNode(x, y);
        res.emplace_back(edge);     // 将这条边添加到结果中，可以根据实际情况执行不同操作
        
    }
    return count == n - 1 ? res : -1;
}

Prim 最下生成树算法

Prim算法与 Kruskal的区别在于，Kruskal算法是每次选择一条最短的且不构成环的边，而Prim算法是使用BFS算法思想和visited数组避免成环，保证选出来的边一定是一棵树。

Prim算法步骤：

1. 从任意一个节点开始，将该节点加入到已访问节点集合中。
2. 在未访问节点中找到与已访问节点集合中节点权值最小的边（也就是跨越已访问节点集合和未访问节点中某个节点的边），将该边和对应的节点加入到已访问节点集合中。
3. 重复第二步操作，直到所有节点都被加入到已访问节点集合中为止。

Prim算法也是一种贪心算法,它的时间复杂度为\(O(n^2)\)，其中n为节点个数。在实际应用中，Prim算法通常用于处理稠密图中的最小生成树问题。

这里Prim算法的实现使用了优先级队列priority_queue,实现代码如下：

// graph为邻接表graph[i] = [node, cost]，start为Prim算法起始节点
int Prim(int n, vector<vector<int>>& graph, int start) 
{   
    if(graph[start].empty())
        return -1;
    visited[start] = true;

    auto cmp = [](pair<int, int> &p1, pair<int, int> &p2) -> bool {return p1.second > p2.second;};
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
    vector<bool> visited = vector<bool>(n + 1, false);      // visited数组判断当前节点是否访问过

    for(auto &edge : graph[start])
    {
        pq.emplace(make_pair(edge.first, edge.second));
    }
    int res = 0, count = 0;
    while(!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        if(visited[cur.first])
            continue;
        visited[cur.first] = true;
        res += cur.second;      // 这里是计算最小生成树边的权值之和，可以根据实际情况调整
        ++count;
        if(count == n - 1)
            return res;
        for(auto &edge : graph[cur.first])
        {
            if(!visited[edge.first])        // 将当前节点的邻接节点加入优先级队列
                pq.emplace(make_pair(edge.first, edge.second));
        }
    }
    return -1;
}

拓扑排序算法

Leetcode上的 210. 课程表 II 便是一道典型的拓扑排序题，问题如下：

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

拓扑排序分为DFS版本和BFS版本。

DFS版本

步骤：

1. 首先，需要先建立一个 DAG（有向无环图），包含顶点和边。
2. 初始化入度为 0 的顶点队列，将初始顶点加入队列中。
3. 从队列头部开始处理。
4. 遍历该顶点的出边，将出边对应的顶点的入度减 1。
5. 如果入度为 0，则将该顶点加入队列末尾。
6. 重复步骤 3-5 直到队列为空。

DFS版本实现类似二叉树的前序遍历或者树的DFS遍历，代码如下：

class Solution {
public:
    vector<int> visited;    // 用于判断节点是否已经访问
    vector<int> inedges;    // 入度数组
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // DFS
        vector<vector<int>> graph(numCourses, vector<int>());
        visited = vector<int>(numCourses, 0);
        inedges = vector<int>(numCourses, 0);
        buildGraph(numCourses, prerequisites, graph, inedges);  // 建图
        vector<int> path;
        for(int i = 0; i < numCourses; ++i)     // 确保在图不是连通的情况下也能正确得到拓扑排序
        {
            if(inedges[i] == 0)
                dfs(graph, path, i, numCourses);
        }
        return (int)path.size() == numCourses ? path : vector<int>();
    }
    
    void dfs(vector<vector<int>> &graph, vector<int> &path,int s, int numCourses)
    {
        if(visited[s])
            return ;
        
        visited[s] = 1;
        path.emplace_back(s);
        if((int)path.size() == numCourses)
        {
            return ;
        }
        for(int &i : graph[s])
        {
            --inedges[i];
            if(inedges[i] == 0)
                dfs(graph, path, i, numCourses);
        }
    }
    
    void buildGraph(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &graph, vector<int> &inedges)
    {
        for(const auto &p : prerequisites)
        {
            int from = p[1], to = p[0];
            graph[from].emplace_back(to);
            ++inedges[to];
        }
    }
};

BFS版本

BFS版本和DFS版本的思路其实是一样的，BFS和DFS的区别类似树的遍历，无非是在遍历节点的时候以不同的顺序访问其邻接节点。DFS的实现用到了递归而BFS的实现用到了队列，类似二叉树的层序遍历或树的BFS遍历。

代码如下：

class Solution {
public:
    
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // BFS
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> visited(numCourses, 0);     // 判断节点是否已经访问
        vector<int> inedges(numCourses, 0);     // 入度数组
        buildGraph(numCourses, prerequisites, graph, inedges);      // 建图
        queue<int> q;
        for(int i = 0; i < numCourses;++i)
        {
            if(inedges[i] == 0)
                q.emplace(i);
        }
        int count = 0;
        vector<int> path;
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            visited[cur] = 1;
            path.emplace_back(cur);     // 将当前节点加入到拓扑排序结果
            for(int i : graph[cur])
            {
                --inedges[i];
                if(inedges[i] == 0)     // 若相邻节点的入度为0，加入到队列中
                    q.emplace(i);
            }
        }
        return (int)path.size() == numCourses? path : vector<int>();
    }

    void buildGraph(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &graph, vector<int> &inedges)
    {
        for(const auto &p : prerequisites)
        {
            int from = p[1], to = p[0];
            graph[from].emplace_back(to);
            ++inedges[to];
        }
    }
};