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

以实例说明图问题——面向图新手 序

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

这里图的概念什么的就不多提，我们主要讲一下算法题里的图；

有向图 简单有向图矩阵(我定义的)

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

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

那么有两个问题：

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

第一个问题不想那么复杂，直接用二维数组存：

// n = 5

vector<vector<int>> edges(n);

二维数组一行代表该行行号对应的元素指向改行元素，也就构成了几条有向边，如本题的有向图矩阵应为：

[[2, 4],

 [4],

 [0, 1],

 [4],

 []]

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

vector<vector<int>> 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<vector<int>> &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<vector<int>> &relation, int k) {
        vector<vector<int>> 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的时候判断当前节点是否最后一个节点，并停止递归。

这样就有这个效果：

其他可以用简单有向图矩阵和dfs轻松搞定的：

1971. 寻找图中是否存在路径（题干说的有效路径就是不重复经过同一节点，这个题干没说清）

class Solution {
private:
    bool res = false;
    unordered_set<int> visited; // 已走过的节点
    void dfs(int curIdx, int destIdx, vector<vector<int>> &arr) {
        visited.emplace(curIdx);
        if (curIdx == destIdx || res) {
            res = true;
            return;
        }
        for (auto next : arr[curIdx]) {
            if (!visited.count(next)) dfs(next, destIdx, arr);
        }
    }
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if (n == 1) return true;
        if (edges.size() == 0) return false;
        vector<vector<int>> arr(n); // 简单有向图矩阵
        for (auto edge : edges) { // 由于是双向图，两个方向都要更新
            arr[edge[0]].push_back(edge[1]);
            arr[edge[1]].push_back(edge[0]);
        }
        dfs(source, destination, arr);
        return res;
    }
};

有向图的出度和入度

997. 找到小镇的法官这道题就属于很经典的出度入度题。

当然就算不了解概念我们也可以用简单有向图矩阵完成：

/ 还是简单有向图能解决的问题，A->B代表A信任B
// 我们建立简单有向图矩阵vector> edges(n)
// 小镇法官存在的条件：edges[i]为空，且其他edges[j]都含i，这种情况有且只有一个
// 仔细想想，如果有两行edges为空，那条件2也没法互相满足，
// 所以：edges为空的行数是否为1，其他都返-1；
//       再看其他行是否都有它，没有的话返-1；

// 警觉：自己能信任自己吗？不能
//       警觉，一个人的时候，没人信任自己，也算“除了小镇法官每个人都信任自己...”

// 注：人编号和数组下标相差1
class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if (n == 1) return 1;
        if (trust.empty()) return -1;

        // 构建简单有向图矩阵
        vector<vector<int>> edges(n);
        for (int i = 0; i < trust.size(); ++i) {
            edges[trust[i][0] - 1].push_back(trust[i][1] - 1);
        }

        // 遍历一遍，找到零信任对象
        int emptyNum = 0, emptyIdx;
        for (int i = 0; i < n; ++i) {
            if (edges[i].empty()) {
                emptyIdx = i;
                emptyNum++;
            }
        }
        if (emptyNum == 1) { // 只有零信任对象数量为1才可能有法官
            for (int i = 0; i < n && i != emptyIdx; ++i) {
                bool exist = false;
                for (int j = 0; j < edges[i].size(); ++j) { // 遍历该节点的有向边查看是否指向零信任对象
                    if (edges[i][j] == emptyIdx) {
                        exist = true;
                        break;
                    }
                }
                if (!exist) return -1;
            }
            return emptyIdx + 1; // 其他人都信任零信任对象，满足条件，返回零信任对象
        } else {
            return -1;
        }
    }
};

我们知道了入度出度的概念，也就知道了我们要找的就是出度为0，入度为n-1的节点。

问题也就转为如何构建入度和出度：

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegrees(n + 1);
        vector<int> outDegrees(n + 1);
        for (auto& edge : trust) { // 每个trust[i]相当于一条边,元素是两个节点,trust[i][0]指向trust[i][1],所以[1]加入度,[0]加出度
            int nodeX = edge[0], nodeY = edge[1];
            ++inDegrees[nodeY];
            ++outDegrees[nodeX];
        }
        for (int i = 1; i <= n; ++i) {
            if (inDegrees[i] == n - 1 && outDegrees[i] == 0) { // n - 1入度和0出度的节点即为所求
                return i;
            }
        }
        return -1;
    }
};