c++ - 图表中的 DFS 需要多少时间间隔？

问题描述

问题：

假设您正在对图表进行广度优先搜索。你从一个特定的点开始，然后向外传播。在一个时间间隔内，在给定的条件下，你“感染”了你的邻居。我想知道遍历整个图需要多少时间间隔（即感染所有节点）。

这个问题是一个普遍的问题。但是，我将依靠 LeetCode 示例来提供可重现的内容。

我的做法：

使用队列的基本 bfs。在每次迭代期间，我都会在队列中插入一个间隔元素。如果我找到这个间隔，我知道一个时间间隔已经结束。

队列中的元素q：

q: a, b, c, timer // a, b and c are infected at first moment in time
q: d, e, timer    // above elements infect, d and e.
q: timer          // we only have a timer, total traversal took 2 time intervals

为什么我的方法不起作用：

我的方法的基本缺陷是我可能会q多次推送元素，如果它们会从多个方面受到感染。

带有队列的示例网格q。q图中节点的存储索引。 1健康，2被感染：

1,1
2,2

q: {0,0}, {0,1}, timer // top 2 elements are in queue. They got infected by bottom 2 elements.

处理第一个元素

2,1
2,2

q: {0,1}, timer, {0,1}

处理第二个元素

2,2
2,2

q: timer, {0,1}, timer

我们将同一个元素推到q两次，导致时间不正确。（时间 == 2，而不是时间 == 1）。

我该如何解决这个错误？

取自 LeetCode 的示例问题：

我曾经（不）解决LeetCode 问题 994的方法。

class Solution {
    struct position {
        position(size_t i, size_t j) : i_(i), j_(j), valid_(true) {}
        position(bool valid) : i_(0), j_(0), valid_(valid) {}
        
        const size_t i_;
        const size_t j_;
        const bool valid_;
    };
    
public:
    int orangesRotting(vector<vector<int>>& grid) {
        if (grid.empty()) return -1;
        size_t fresh_orange = 0;
        std::queue<position> q;
        
        for (size_t i = 0; i < grid.size(); ++i) {
            for (size_t j = 0; j < grid.at(0).size(); ++j) {
                int orange = grid.at(i).at(j);
                if (orange == 1) {
                    ++fresh_orange;
                } else if (orange == 2) {
                    q.emplace(i, j);
                }
            }
        }
        size_t minutes = 0;
        q.emplace(false);
        
        while(!q.empty()) {
            const position pos = q.front();
            q.pop();
            if (!pos.valid_ && !q.empty()) {
                ++minutes;
                q.emplace(false);
            }
            if (!pos.valid_) continue;
            
            // bfs next: top, right, bottom, left
            const size_t old_size = q.size();
            if (pos.i_ > 0) 
                if (grid.at(pos.i_ - 1).at(pos.j_) == 1) q.emplace(pos.i_ - 1, pos.j_);
            if (pos.j_ < grid.at(0).size() - 1)
                if (grid.at(pos.i_).at(pos.j_ + 1) == 1) q.emplace(pos.i_, pos.j_ + 1);
            if (pos.i_ < grid.size() - 1)
                if (grid.at(pos.i_  + 1).at(pos.j_) == 1) q.emplace(pos.i_  + 1, pos.j_);
            if (pos.j_ > 0)
                if (grid.at(pos.i_).at(pos.j_ - 1) == 1) q.emplace(pos.i_, pos.j_ - 1);
        
            if (grid.at(pos.i_).at(pos.j_) == 1) {
                --fresh_orange;
                grid.at(pos.i_).at(pos.j_) = 2;
            }
        }

        return fresh_orange == 0 ? minutes : -1;
    }
};

重现我的问题的输入：[[2,2],[1,1],[0,0],[2,0]].

标签： c++timegraphqueuedepth-first-search

解决方案

好的。我有（显而易见的）解决方案：您只需跟踪下一轮谁会被感染。我将-1其用作“将很快被感染”的标记。