Frank's blogs

永远好奇

0%

Leetcode图相关遍历

发表于 更新于
本文字数： 12k 阅读时长 ≈ 22 分钟

图的拓扑排序

广度优先搜索（Leetcode 207.课程表）

  • 用一个数组记录每个节点的进入边的数量
  • 开始的时候将所有入度为0的点加入队列
  • 依次从队列中弹出点，将从这个点出发指向的所有点的入度-1，然后将跟这个点相关的路径全部删除
    • 假如此时遇到点的入度是0的话，将这个点加入队列
  • 将队列中弹出的点加入输出序列中
  • 假如最后图上的所有点都在输出序列中，说明无环，否则有环
    class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            vector<vector<int>> vMap(numCourses);
            vector<int> inCnt(numCourses, 0);
            vector<int> ans;
            for(int i = 0; i<prerequisites.size(); i++)
            {
                vMap[prerequisites[i][1]].push_back(prerequisites[i][0]);
                ++inCnt[prerequisites[i][0]];
            }
            queue<int> q;
            for(int i = 0; i<numCourses; i++)
            {
                if(inCnt[i] == 0)
                {
                    q.push(i);
                }
            }

            while(q.size())
            {
                auto temp = q.front();
                q.pop();
                for(auto& i:vMap[temp])
                {
                    --inCnt[i];
                    if(inCnt[i] == 0)q.push(i);
                }
                vMap[temp] = vector<int>();
                ans.push_back(temp);
            }
            if(ans.size()<numCourses)return false;
            else return true;

        }
    };

深度优先搜索

  • 遍历所有节点，先标记自己被遍历过了
  • 每个节点递归的遍历自己所有边指向的没有被打上遍历过的标签的节点
  • 回溯的时候（也就是之后的节点都遍历结束之后）将自己添加到拓扑顺序的栈中
  • 依次弹出栈中元素，得到顺序
    #include <iostream>
    #include <vector>
    #include <stack>

    using namespace std;

    class Graph {
    public:
        int vertices;
        vector<vector<int>> adjList;

        Graph(int V) : vertices(V), adjList(V) {}

        void addEdge(int u, int v) {
            adjList[u].push_back(v);
        }

        void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& result) {
            visited[v] = true;

            for (int neighbor : adjList[v]) {
                if (!visited[neighbor]) {
                    topologicalSortUtil(neighbor, visited, result);
                }
            }

            result.push(v);
        }

        void topologicalSort() {
            stack<int> result;
            vector<bool> visited(vertices, false);

            for (int i = 0; i < vertices; ++i) {
                if (!visited[i]) {
                    topologicalSortUtil(i, visited, result);
                }
            }

            cout << "Topological Sort: ";
            while (!result.empty()) {
                cout << result.top() << " ";
                result.pop();
            }
        }
    };

    int main() {
        Graph g(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        g.topologicalSort();

        return 0;
    }

    417. 太平洋大西洋水流问问题

  • 此题主要是使用逆向搜索
  • 也就是从海边往上倒溯看能到达哪个位置，减少遍历的次数
    class Solution {
    public:
        vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
            vector<vector<bool>> passed(heights.size(), vector<bool>(heights[0].size(), false));
            vector<vector<bool>> passedR(heights.size(), vector<bool>(heights[0].size(), false));
            int m = heights.size(), n = heights[0].size();
            vector<vector<int>> ret;
            vector<vector<bool>> visited(heights.size(), vector<bool>(heights[0].size(), false));
            for(int i = 0; i<m; ++i)
            {
                if(passed[i][0])continue;
                queue<pair<int, int>> q;
                passed[i][0] = true;
                q.push(make_pair(i, 0));
                while(q.size())
                {
                    auto t = q.front();
                    q.pop();
                    int curH = heights[t.first][t.second];
                    visited[t.first][t.second] = true;
                    if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passed[t.first-1][t.second])
                    {
                        passed[t.first-1][t.second] = true;
                        q.push(make_pair(t.first-1, t.second));
                    }
                    if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passed[t.first][t.second-1])
                    {
                        passed[t.first][t.second-1] = true;
                        q.push(make_pair(t.first, t.second-1));
                    }
                    if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passed[t.first+1][t.second])
                    {
                        passed[t.first+1][t.second] = true;
                        q.push(make_pair(t.first+1, t.second));
                    }
                    if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passed[t.first][t.second+1])
                    {
                        passed[t.first][t.second+1] = true;
                        q.push(make_pair(t.first, t.second+1));
                    }

                }
            }

            for(auto& i : visited)
            {
                fill(i.begin(), i.end(), false);
            }
            // cout<<'!'<<endl;
            for(int i = 0; i<n; ++i)
            {
                if(passed[0][i])continue;
                queue<pair<int, int>> q;
                passed[0][i] = true;
                q.push(make_pair(0, i));
                while(q.size())
                {
                    auto t = q.front();
                    q.pop();
                    int curH = heights[t.first][t.second];
                    visited[t.first][t.second] = true;
                    if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passed[t.first-1][t.second])
                    {
                        passed[t.first-1][t.second] = true;
                        q.push(make_pair(t.first-1, t.second));
                    }
                    if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passed[t.first][t.second-1])
                    {
                        passed[t.first][t.second-1] = true;
                        q.push(make_pair(t.first, t.second-1));
                    }
                    if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passed[t.first+1][t.second])
                    {
                        passed[t.first+1][t.second] = true;
                        q.push(make_pair(t.first+1, t.second));
                    }
                    if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passed[t.first][t.second+1])
                    {
                        passed[t.first][t.second+1] = true;
                        q.push(make_pair(t.first, t.second+1));
                    }

                }
            }

            for(auto& i : visited)
            {
                fill(i.begin(), i.end(), false);
            }
            for(int i = 0; i<m; ++i)
            {
                if(passedR[i][n-1])continue;
                queue<pair<int, int>> q;
                passedR[i][n-1] = true;
                q.push(make_pair(i, n-1));
                while(q.size())
                {
                    auto t = q.front();
                    q.pop();
                    int curH = heights[t.first][t.second];
                    visited[t.first][t.second] = true;
                    if(passed[t.first][t.second])ret.push_back({t.first, t.second});
                    if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passedR[t.first-1][t.second])
                    {
                        passedR[t.first-1][t.second] = true;
                        q.push(make_pair(t.first-1, t.second));
                    }
                    if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passedR[t.first][t.second-1])
                    {
                        passedR[t.first][t.second-1] = true;
                        q.push(make_pair(t.first, t.second-1));
                    }
                    if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passedR[t.first+1][t.second])
                    {
                        passedR[t.first+1][t.second] = true;
                        q.push(make_pair(t.first+1, t.second));
                    }
                    if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passedR[t.first][t.second+1])
                    {
                        passedR[t.first][t.second+1] = true;
                        q.push(make_pair(t.first, t.second+1));
                    }

                }
            }
            for(auto& i : visited)
            {
                fill(i.begin(), i.end(), false);
            }
            for(int i = 0; i<n; ++i)
            {
                if(passedR[m-1][i])continue;
                queue<pair<int, int>> q;
                passedR[m-1][i] = true;
                q.push(make_pair(m-1, i));
                while(q.size())
                {
                    auto t = q.front();
                    q.pop();
                    int curH = heights[t.first][t.second];
                    visited[t.first][t.second] = true;
                    if(passed[t.first][t.second])ret.push_back({t.first, t.second});
                    if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passedR[t.first-1][t.second])
                    {
                        passedR[t.first-1][t.second] = true;
                        q.push(make_pair(t.first-1, t.second));
                    }
                    if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passedR[t.first][t.second-1])
                    {
                        passedR[t.first][t.second-1] = true;
                        q.push(make_pair(t.first, t.second-1));
                    }
                    if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passedR[t.first+1][t.second])
                    {
                        passedR[t.first+1][t.second] = true;
                        q.push(make_pair(t.first+1, t.second));
                    }
                    if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passedR[t.first][t.second+1])
                    {
                        passedR[t.first][t.second+1] = true;
                        q.push(make_pair(t.first, t.second+1));
                    }
                }
            }

            return ret;
        }
    };

Leetcode 827. 最大人工岛

  • 此题关键是要使用grid本身的空间在岛屿的每个位置上存储本身的大小方便计算
  • 要额外维护一张表，将同一个岛屿的点编号为同样的，不同的岛屿编为不同的，防止最后求和的时候比如某个0的位置被同一个岛屿的多个点包围导致同一个岛屿累加了多次的重复
    class Solution {
    public:
        int largestIsland(vector<vector<int>>& grid) {
            vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
            vector<vector<int>> identity(grid.size(), vector<int>(grid[0].size(), 0));
            vector<pair<int, int>> visQue;
            int m = grid.size(), n = grid[0].size();
            int id = 0;
            for(int i = 0; i<grid.size(); ++i)
            {
                for(int j = 0; j<grid[0].size(); ++j)
                {
                    int cnt = 0;
                    if(visited[i][j] || grid[i][j] == 0)continue;
                    queue<pair<int, int>> q;
                    visited[i][j] = true;
                    q.push(make_pair(i, j));
                    while(q.size())
                    {
                        auto tmp = q.front();
                        // cout<<tmp.first<<'|'<<tmp.second<<endl;
                        q.pop();
                        visQue.push_back(tmp);
                        
                        ++cnt;
                        if(tmp.first-1>=0 && !visited[tmp.first-1][tmp.second] && grid[tmp.first-1][tmp.second] == 1)
                        {
                            q.push(make_pair(tmp.first-1, tmp.second));
                            visited[tmp.first-1][tmp.second] = true;
                        }
                        if(tmp.second-1>=0 && !visited[tmp.first][tmp.second-1] && grid[tmp.first][tmp.second-1] == 1)
                        {
                            q.push(make_pair(tmp.first, tmp.second-1));
                            visited[tmp.first][tmp.second-1] = true;
                        }
                        if(tmp.first+1<m && !visited[tmp.first+1][tmp.second] && grid[tmp.first+1][tmp.second] == 1)
                        {
                            q.push(make_pair(tmp.first+1, tmp.second));
                            visited[tmp.first+1][tmp.second] = true;
                        }
                        if(tmp.second+1<m && !visited[tmp.first][tmp.second+1] && grid[tmp.first][tmp.second+1] == 1)
                        {
                            q.push(make_pair(tmp.first, tmp.second+1));
                            visited[tmp.first][tmp.second+1] = true;
                        }
                    }
                    for(auto& k : visQue)
                    {
                        grid[k.first][k.second] = cnt;
                        identity[k.first][k.second] = id;
                    }
                    id++;
                    visQue.clear();
                }
            }
            unordered_set<int> ids;
            int maxS = 0;
            for(int i = 0; i<m; ++i)
            {
                for(int j = 0; j<n; ++j)
                {
                    maxS = max(maxS, grid[i][j]);
                    if(grid[i][j]>0)continue;
                    int sum = 0;
                    if(i>0 && grid[i-1][j]>0 && ids.count(identity[i-1][j]) == 0)
                    {
                        ids.insert(identity[i-1][j]);
                        sum+=grid[i-1][j];
                    }
                    if(j>0 && grid[i][j-1]>0 && ids.count(identity[i][j-1]) == 0)
                    {
                        ids.insert(identity[i][j-1]);
                        sum+=grid[i][j-1];
                    }
                    if(i<m-1 && grid[i+1][j]>0 && ids.count(identity[i+1][j]) == 0)
                    {
                        ids.insert(identity[i+1][j]);
                        sum+=grid[i+1][j];
                    }
                    if(j<n-1 && grid[i][j+1]>0 && ids.count(identity[i][j+1]) == 0)
                    {
                        ids.insert(identity[i][j+1]);
                        sum+=grid[i][j+1];
                    }
                    maxS = max(maxS, sum+1);
                    ids.clear();
                }
            }
            return maxS;
        }   
    };

Leetcode 127. 单词接龙

  • 此题是讲字母相邻的单词组织成一张图
  • 实际上是求图上两个点的最近距离
  • 题解
  • 广度优先搜索法
    • 每循环一次，找一个没有接触过的位置，将其距离更新为接触过的位置+1，然后也放入队列遍历
    • 注意，只考虑之前没有加入过的点，防止环的影响
    • 广搜到的第一条路一定是最近的，因为广搜会一次遍历所有可能的路径
      class Solution {
      public:
          unordered_map<int, vector<int>> edges;
          int getdistence(string& s1, string& s2)
          {
              int cnt = 0;
              for(int m = 0; m<s1.size(); ++m)
              {
                  if(s1[m]!=s2[m])++cnt;
              }
              return cnt;
          }
          int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
              // if(wordList.find(endWord) == wordList.end())return 0;
              vector<bool> visited(wordList.size(), false);
              vector<int> toBegin;
              queue<int> q;
              int endIndex = -1;
              for(int i = 0; i<wordList.size(); ++i)
              {
                  if(wordList[i] == endWord)endIndex = i;
                  if(getdistence(wordList[i], beginWord) == 1)
                  {
                      // toBegin.push_back(i);
                      q.push(i);
                      visited[i] = true;
                  }
                  for(int j = i+1; j<wordList.size(); ++j)
                  {
                      int cnt = getdistence(wordList[i], wordList[j]);
                      if(cnt == 1)
                      {
                          edges[i].push_back(j);
                          edges[j].push_back(i);
                      }
                  }
              }
              if(endIndex == -1)return 0;

              int cnt = 1;
              while(q.size())
              {
                  int s = q.size();
                  ++cnt;
                  for(int i = 0; i<s; ++i)
                  {
                      auto tmp = q.front();
                      // cout<<wordList[tmp]<<' ';
                      if(wordList[tmp] == endWord)
                      {
                          return cnt;
                      }
                      q.pop();
                      if(!edges.count(tmp))
                      {
                          continue;
                      }
                      for(auto& f : edges[tmp])
                      {
                          if(visited[f])continue;
                          q.push(f);
                          visited[f] = true;
                      }
                  }
                  // cout<<endl;
              }
              return 0;
          }
      };

Leetcode 463. 岛屿的周长

  • 这道题不需要使用搜索
  • 只使用遍历即可，招每个节点左和上的相邻节点，减去内部边界
  • 不找右和下是因为怕重复
    class Solution {
    public:
        int islandPerimeter(vector<vector<int>>& grid) {
            int sum = 0;    // 陆地数量
            int cover = 0;  // 相邻数量
            for (int i = 0; i < grid.size(); i++) {
                for (int j = 0; j < grid[0].size(); j++) {
                    if (grid[i][j] == 1) {
                        sum++;
                        // 统计上边相邻陆地
                        if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                        // 统计左边相邻陆地
                        if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                        // 为什么没统计下边和右边？ 因为避免重复计算
                    }
                }
            }
            return sum * 4 - cover * 2;
        }
    };