图分为有向图和无向图，相关常见问题及算法有最短路径算法、拓扑排序、关键路径以及最短路径等。本文介绍相关算法的C++实现，完整源码直接参看文末。

广度优先BFS和深度优先DFS搜索

与图相关的问题中大多数的节点遍历方式都采用BFS或DFS，顾名思义，广度优先就是先将节点相邻的节点全部遍历，然后递归搜索相邻接点的相邻接点，这一特点与队列比较类似因此在广度优先搜索时一般使用队列作为辅助结构，二叉树的层序遍历实际上就是BFS，而在二叉树的层序遍历中借助的正是队列。

与树不同的是，在图的遍历过程中都需要借助一个额外的数据结构来保存已经遍历过的节点，避免节点的重复遍历，这里借助一个名为visited的set来记录。

为了是的bfs能够多次被使用，这里借助template传入一个functor来操作x，便于代码重用。

template < class Func>
void bfs(node_t start, Func & & func) {
    que.push(start);
    visited.insert(start);
    while (!que.empty()) 
        auto x = que.front();
        func(x);
        que.pop();
        for (auto & & e : adjacent[x])
            if (!visited.count(e->v)) 
                visited.insert(e->v);
                que.push(e->v);
}

深度优先搜索最主要的区别就在于先遇到的相邻节点后访问，先进后出的特点与stack非常相似，因此在深度优先的时候上述代码将queue替换成stack行了。

最小生成树

常见的求最小生成树的算法包括prim和kruskal，prim算法基于动态规划，而kruskal则是贪心算法。

prim算法

普里姆算法以节点为核心，从任意节点出发，然后用一个集合来保存已经连接到的节点。

将集合看做一个整体，寻找新的边时，遍历与集合中节点相邻的边（即可以加入的边），并从中选取最小的那一个，将相邻节点加入到集合中。

Edge prim() {
    used.insert(begin());
    while (used.size() <  size()) 
        edge = nullptr;
        for (const auto & v : used) 
            for (const auto & e : adjacent[v])
                if (!used.count(e->v))
                    if (!edge || e->weight <  edge->weight) edge = e;
        if (edge) 
            used.insert(edge->v);
            mst += edge->weight;
    return mst;
}

kruskal算法

克鲁斯卡尔算法以边为核心，每次都选取能够使用的最短的边加入到生成树中。

先构造一个有序的结构来保存边，然后遍历每条边，将可用的边加入到最小生成树中。

当最小生成树中包含了所有的节点就结束。

在实现时比较麻烦的就是如何判断边是否可用，并且由于在开始的时候选取的边之间可能没有连接，所以会产生多个子图。如果判断的边上的两个节点都在一个子图中，说明该边不需要了。

这里在实现时借助额外的nodeset和nodes来保存子图信息，子图中节点在nodes中int值都是相同的。

Edge kruskal() {
    multiset edges; // 有序的edges
    for (const auto & e : edges) 
        int i = nodes[e->u], j = nodes[e->v];
        if (i != j) // 不在同一个子图
            if (i > j) std::swap(i, j);
            for (const auto & v : nodeset[j]) // 更新子图信息
                nodes[v] = i, nodeset[i].insert(v);

            mst += e->weight;
            if (nodeset[i].size() == size()) return mst;
    return mst;
}

拓扑排序

拓扑排序与其说是排序不如说是拓扑路径，可以看做一种遍历的方式。当然只有满足拓扑路径的网络才能进行拓扑排序，一般来说只有有向无环图满足这种条件。

拓扑排序反映了节点之间的依赖关系，这种关系用入度和出度表示，入度为0的节点不依赖于任何其它节点。

进行拓扑排序就是从入度为0的的节点开始遍历，经过每个节点，就拿掉该节点和其对应的边，可以表现为其相邻节点的入度减1。

由于拓扑排序是一种遍历方式，所以为了重用同样加入function来访问每个节点，并且还具备判断网络是否具有拓扑结构的功能，当访问到已经访问过的节点，也就是这里入度已经设置为-1的节点时，就说明出现了环路，不满足拓扑结构。

template < class Func>
bool toposort(node_t start, Func & & func) {
    que.push(start);
    while (!que.empty()) 
        auto x = que.front();
        func(x);
        que.pop();
        for (const auto & e : adjacent[x])
            if (indegree[e->v] == -1) return false;
            if (--indegree[e->v] == 0) 
                que.push(e->v);
                indegree[e->v] = -1;
    return true;
}

关键路径

关键路径一般用于AOE网络（Activity On Edge Network），用于工程项目的工期控制。关键路径就是网络中不能延误的边组成的路径。

在AOE网络中，边表示活动，节点表示活动的开始时刻或者结束时刻。计算关键路径通过比较节点的最晚开始时刻和最早开始时刻，最早开始时刻表示当前节点依赖的所有活动都结束然后立刻开始的时刻，最晚开始时刻表示在不影响整体工期的情况下当前节点最晚能够开始的时刻。

求最早开始时刻和最晚开始时刻的过程就是对图进行拓扑遍历和反向拓扑遍历的过程。

首先借助toposort遍历网络，在遍历的过程中将访问的节点保存到vector中，然后根据每个节点的最早开始时刻和相邻边的长度来更新相邻节点的最早开始时刻。

反向遍历时，需要借助反向边adjacent_reversed，其中保存了指向当前节点的边。根据当前节点的最晚开始时刻和反向边的长度来更新反向相邻节点的最晚开始时刻。

template < class Func>
int critical_path(node_t source, node_t target, Func & & func) {
    auto f = [this, & vec, & earlist](node_t v) {
        vec.push_back(v);
        for (const auto & e : adjacent[v])
            if (earlist[v] + e->weight > earlist[e->v])
                earlist[e->v] = earlist[v] + e->weight;
    };
    if (!toposort(source, f)) return -1;

    for (int i = vec.size() - 1; i >= 0; i--) 
        auto v = vec[i];
        for (const auto & e : adjacent_reversed[v])
            if (latest[v] - e->weight <  latest[e->u])
                latest[e->u] = latest[v] - e->weight;

    for (const auto & v : vec)
        if (earlist[v] == latest[v]) func(v);

    return earlist[target];
}

最短路径算法

最短路径算法包括dijkstra算法和Floyd算法，前者解决了两个节点之间的的最短路径问题，后者能够计算所有两个节点之间的最短路径。

Dijkstra算法

Dijkstra算法实际上就是一次遍历，可以借助bfs直接处理，对于每个节点，利用distance记录其与源节点的最短路径，每次经过一个节点，就更新其相邻节点与source的最短路径值。遍历完成之后distance中就保存了每个节点到源节点的最短路径。当然这里的遍历既可以用bfs也可以用dfs。

Edge dijkstra(node_t source, node_t target) {
    auto f = [& distance, this](node_t v) {
        for (const auto & e : adjacent[v])
            if (distance.count(e->v) == 0 ||
                distance[v] + e->weight <  distance[e->v])
                distance[e->v] = distance[v] + e->weight;
    };
    bfs(source, f);
    return distance[target];
}

Floyd算法

弗洛伊德算法目的在于求解所有的意两个节点之间的最短距离，主要思想就是，在计算节点i和节点j之间的最短距离时，判断引入额外的k节点作为中继是否能够使得i和j之间的距离更短，如果是的话就更新i和j之间的距离。

void floyd(std::vector< std::vector< Edge>> & distance,
            std::map< node_t, int> & index) {
    for (int i = 0; i <  n; i++) 
        auto u = nodes[i];
        for (const auto & e : adjacent[u])
            distance[index[u]][index[e->v]] = e->weight;

    for (int i = 0; i <  n; i++)
        for (int j = 0; j <  n; j++)
            for (int k = 0; k <  n; k++) 
                if (distance[i][k] >= 0 & &  distance[k][j] >= 0)
                    if (distance[i][j] == (Edge)-1 ||
                        distance[i][k] + distance[k][j] <  distance[i][j])
                        distance[i][j] = distance[i][k] + distance[k][j];
}

完整源码

完整源代码可以参看@wxggg graph.hh

Reference

1] https://github.com/wxggg/algorithm/blob/master/include/graph.hh