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

以LeetCode实例说明图问题——初学图,第1张

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

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


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

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

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

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;
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562504.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-01
下一篇 2022-04-01

发表评论

登录后才能评论

评论列表(0条)

保存