。找到最终的安全状态

802。查找最终的安全状态

难度：中等

>主题：深度优先搜索，广度优先搜索，图形，拓扑排序

有一个定向的n个节点图，每个节点从0到n -1标记。该图由a 0- indexed 2D integer阵列图表示，其中图[i]是一个整数阵列与节点I相邻的节点的源，这意味着从节点i到图中的每个节点有一个边缘[i]。

。 如果没有传出边缘，则一个节点为

终端节点。节点是a安全节点如果从该节点开始的每个可能的路径都会导致>终端节点（或另一个安全节点）。

返回

一个包含图形的所有安全节点的数组。答案应以上升顺序排序。 >>示例1：

>输入：

graph = [[1,2]，[2,3]，[5]，[0]，[5]，[5]，[]，[]，[]]

>输出： [2,4,5,6]

>说明：给定的图如上所示。 节点5和6是终端节点，因为其中任何一个都没有外向。 从节点2、4、5和6开始的每条路径都导致节点5或6。

>

>示例2：

输入：

graph = [[1,2,3,4]，[1,2]，[3,4]，[0,4]，[0,4]，[]] >输出：

[4]

• >说明：只有节点4是一个终端节点，从节点4开始的每个路径都会导致节点4。
>
• >约束：
• > n == graph.length

1＆lt; = n＆lt; = 10 4 > 0＆lt; = graph [i] .length＆lt; = n

• 0＆lt; = graph [i] [j]＆lt; = n -1
• 图[i]以严格增加的顺序进行排序。 该图可能包含自宽。
>
• 图中的边数将在[1，4 * 10
4
• ]范围内。
• 解决方案：
• 我们需要识别图表中的所有安全节点。这涉及检查是否从给定节点开始，每个路径最终都到达终端节点或其他安全节点。该解决方案使用深度优先搜索（DFS）来检测周期并将节点分类为安全或不安全。

  关键见解：

  1. >终端节点：一个没有传出边缘的节点是终端节点。
  2. >安全节点：一个节点是安全的，如果从该节点开始，所有路径最终都会导致终端节点或其他安全节点。
  循环检测
  3. ：如果节点是周期的一部分，则不是一个安全的节点，因为从其开始的路径不会导致终端节点。 方法：

  我们使用DFS探索每个节点并确定它是否是周期的一部分。循环或导致周期的一部分的节点标记不安全。 最终导致终端节点或其他安全节点的节点被标记为安全。

  >
  • 我们使用一个访问的数组，带有三个状态：
  0：尚未访问该节点。

  1：该节点当前正在访问（即，在递归堆栈中）。

  >
  2：该节点已完全处理并且是安全的。
  • 步骤：
  >为每个节点执行DFS。

  使用访问的状态标记安全/不安全的节点。收集所有安全的节点。

  1. >让我们在PHP中实现此解决方案： 802。查找最终的安全状态
  解释：

  
  dfs函数

  ：

  <?php /**
   * @param Integer[][] $graph
   * @return Integer[]
   */
  function eventualSafeNodes($graph) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  /**
   * DFS helper function
   *
   * @param $node
   * @param $graph
   * @param $visited
   * @return int|mixed
   */
  function dfs($node, $graph, &$visited) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  // Example usage:
  $graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
  $graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
  
  print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
  print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
  ?>
  

  > DFS函数在节点上执行深度优先搜索，在开始时将其标记为“访问”（1），并且“安全”（2）当其所有邻居都安全时（2）

  如果其任何邻居都导致一个周期（由DFS（$ neighbor）== 1表示），则该节点标记为不安全（1）。
  1. 如果所有邻居都导致终端节点或安全节点，则标记为安全（2）。
     主函数
     • ：
     我们迭代所有节点，并使用DFS检查每个节点是否安全。
     • >
     >所有安全节点均收集在$ Safenodes数组中并返回。>

  2. 示例演练： 示例1：

     在此示例中，节点5和6是终端节点（无外部边缘）。
     • >节点4导致节点5，因此也是安全的。>节点2导致节点5，因此它是安全的。>

  输出：

  $graph = [[1,2],[2,3],[5],[0],[5],[],[]];
  print_r(eventualSafeNodes($graph));
  

  示例2：
  在此示例中，只有节点4是终端节点，从节点4开始的所有路径引向节点4。>
  • 所有其他节点最终导致周期或不安全的节点。
  • 输出：

  <?php /**
   * @param Integer[][] $graph
   * @return Integer[]
   */
  function eventualSafeNodes($graph) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  /**
   * DFS helper function
   *
   * @param $node
   * @param $graph
   * @param $visited
   * @return int|mixed
   */
  function dfs($node, $graph, &$visited) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  // Example usage:
  $graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
  $graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
  
  print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
  print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
  ?>
  

  时间和空间复杂度：

  • 时间复杂度：O(n e)，其中n是节点数，e 是边数。我们访问每个节点一次并处理每条边一次。
  • 空间复杂度：O(n) 用于访问的数组和递归堆栈。

  该解决方案使用 DFS 有效地确定安全节点，确保满足问题约束。

  联系链接

  如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

  如果您想要更多类似的有用内容，请随时关注我：

  • 领英
  • GitHub

以上是。找到最终的安全状态的详细内容。更多信息请关注PHP中文网其他相关文章！