以LeetCode实例说明图问题——初学图

很多题能用很简单的图做出来，但思路到了，代码实施不出来，脑海中没有一个模板。

这里图的概念什么的就不多提，自己看，我们主要讲一下算法题里的图，可能和标准方案不同，我理解能套路地解决问题就好。

存储、构建有向图的例子：

LCP 07. 传递信息这道题就属于可以用有向图形象地做出来的题，题干我就不放了。我们建立这么一张有向图，并从节点0开始进行dfs遍历，走步k次以后判断结果。

那么有两个问题：

有向图的数据结构如何表示？如何dfs遍历有向图？

第一个问题不想那么复杂，除非要求邻接矩阵什么的，我直接用二维数组存：

// n = 5
vector> edges(n);

二维数组一行代表该行序对应的元素指向哪些元素，如0指向2和4，本题的有向图矩阵应为：

[[2, 4],

 [4],

 [0, 1],

 [4],

 []]

本题给的是一系列指向，那么有向图矩阵的初始化：

vector> edges(n);
for (int i = 0; i < relation.size(); ++i) {
    edges[relation[i][0]].push_back(relation[i][1]);
}

到此有向图的表示解决了，然后是如何dfs遍历有向图，我学到的是这个套路：

class Solution {
private:
    int res = 0;

    void dfs(int k, int idx, vector> &edges, int &n) {
        if (k == 0) { // dfs停止的条件，一定要有
            if (idx == n - 1) res++; // 满足条件了记录下来
            return;
        }
        for (int i = 0; i < edges[idx].size(); ++i) {
            dfs(k - 1, edges[idx][i], edges, n);
        }
    }

public:
    int numWays(int n, vector> &relation, int k) {
        vector> edges(n);
        for (int i = 0; i < relation.size(); ++i) {
            edges[relation[i][0]].push_back(relation[i][1]);
        }
        dfs(k, 0, edges, n);
        return res;
    }
};

每次递归将条件判断对象k减1，减到0的时候判断当前节点是否最后一个节点，并停止递归。

这样就有这个效果：

当然，图还有更多概念，题也有更多种，不间断更新中……