检查根据给定条件从数组构建的图是否包含循环

简介

在图论中，弄清楚由数组构建并满足某些条件的图是否有环是一项非常重要的任务。图表是一种显示事物如何联系在一起的想象方式。它被用在很多地方，比如计算机网络和社交网络。本文讨论了图构造的条件、BFS 和 DFS 算法，并逐步指导如何识别无向图中的循环。

图的数组表示

图论中基于数组的方法将顶点和边存储在数组中，这使得它们易于在算法中使用和使用。从一张空图开始，根据数组中的信息一次添加一个顶点和边，这是进一步探索的基础，例如循环检测，这对于理解图如何链接以及是否存在循环非常重要。

图构建条件

给定条件的解释

• 图是由数组构造的，其中数组表示一组顶点及其连接或边。

• 数组的每个元素对应图中的一个顶点

• 数组中每个元素的值表示它所连接的顶点（其相邻顶点）的索引。

• 数组的索引代表顶点本身，其对应的值代表它所连接的顶点。

验证图构建的条件

• 在构建图表之前检查数组是否有效并满足所需条件。

• 确保数组不为空并且至少包含一个元素来创建顶点。

• 验证数组是否仅包含非负整数，因为负值或无效数据无法表示有效的顶点或边

• 确保数组索引在适当的范围内。它们应该从 0 开始到 n-1，其中 n 是图中的顶点总数。

• 确认数组中的值（连接）也在0到n-1的有效范围内，确保它们对应于现有的顶点

• 检查是否有重复连接或自循环，因为它们违反了有效图表的条件

• 验证没有丢失连接，这意味着所有顶点都连接起来形成完整的图或连接的组件

DFS 和 BFS 算法

• 深度优先搜索 (DFS) 用于探索图的顶点和边，方法是在转身之前尽可能深入每个分支

伪代码

procedure DFS(graph, start_vertex, visited)
   if start_vertex is not in visited:
      mark start_vertex as visited
      process start_vertex (e.g., check for cycles)
      for each neighbor in graph[start_vertex]:
      if neighbor is not in visited:
      DFS(graph, neighbor, visited)
   end if
end procedure
    pocedure DFS_Traversal(graph)
    visited = empty set
      for each vertex in graph:
      if vertex is not in visited:
         DFS(graph, vertex, visited)
   end for
end procedure

• 广度优先搜索 (BFS) 是一种图遍历算法，一次一层地遍历图的所有顶点。这使得它成为在图表中查找周期的好方法

伪代码

procedure BFS(graph, start_vertex):
   create an empty queue Q
   create a set visited to keep track of visited vertices
   
   enqueue start_vertex into Q
   add start_vertex to visited set
   
   while Q is not empty:
      current_vertex = dequeue from Q
      for each neighbor_vertex of current_vertex:
         if neighbor_vertex is not in visited set:
            enqueue neighbor_vertex into Q
            add neighbor_vertex to visited set
      else:
         // A cycle is detected, return true
         return true
      // No cycle found, return false
      return false

复杂性

• 时间复杂度

BFS 和 DFS 的时间复杂度都是 O(V + E)，其中 V 是顶点数，E 是边数。

• 空间复杂度

BFS 和 DFS 的时间复杂度为 O(V)。

分步循环检测过程

让我们考虑一个带有图表的示例

• 从一个空集合开始监视访问过的顶点

Visited set: {}

• 选择任意顶点作为循环检测过程的起点。我们选择顶点 A。

Visited set: {A}
Current Vertex: A

• 检查当前顶点 (A) 的相邻顶点。在本例中，A 的邻居是 B 和 D。将它们添加到访问集中，并将 A 标识为其父节点

Visited set: {A, B, D}
Current Vertex: A
Parent of B: A
Parent of D: A

• B 是访问集中的下一个访问顶点。

Visited set: {A, B, D}
Current Vertex: B
Parent of B: A

• 探索 B 的周围环境。 B 的直接邻居是 A、C 和 E。A 已经在访问顶点集合中，但它不是 B 的父节点，因此不构成环。

Visited set: {A, B, D, C, E}
Current Vertex: B

• 继续到下一个访问的顶点，即 D。

Visited set: {A, B, D, C, E}
Current Vertex: D
Parent of D: A

• 发现 D 的熟人。 A 和 E 是 D 的最近邻居。由于 A 已经包含在访问集中并且是 D 的父代，因此必须有一条边 (D -> A) 将 D 连接到其父代。这表明该图包含一个循环。

Cycle detected! There is an edge (D -> A) forming a cycle

过程到这里就结束了，我们已经使用BFS成功检测到了图中的环路 即（A->B->E->D->A）。

结论

总之，对于许多应用程序来说，能够在根据给定参数从数组构建的图中找到循环非常重要。无论您使用 DFS 还是 BFS，此过程都有助于找到可能的循环并解决涉及网络、电路和关系的现实问题。有效的循环检测可以提高算法的速度并确保数据正确。

以上是检查根据给定条件从数组构建的图是否包含循环的详细内容。更多信息请关注PHP中文网其他相关文章！