Checks whether a graph built from an array based on a given condition contains a cycle

Introduction

In graph theory, it is a very important task to figure out whether a graph constructed from arrays and satisfying certain conditions has a cycle. A diagram is an imaginative way of showing how things are connected. It is used in many places, such as computer networks and social networks. This article discusses the conditions for graph construction, BFS and DFS algorithms, and provides step-by-step instructions on how to identify cycles in undirected graphs.

Array representation of the graph

Array-based methods in graph theory store vertices and edges in arrays, which makes them easy to use and work with in algorithms. Starting with an empty graph, adding vertices and edges one at a time based on the information in the array is the basis for further exploration, such as cycle detection, which is important for understanding how the graph is linked and whether there are cycles.

Graph construction conditions

Explanation of given conditions

• Graphs are constructed from arrays, where arrays represent a set of vertices and their connections or edges.

• Each element of the array corresponds to a vertex in the graph

• The value of each element in the array represents the index of the vertex it is connected to (its adjacent vertices).

• The index of the array represents the vertex itself, and its corresponding value represents the vertex it is connected to.

Conditions for verifying graph construction

• Check that the array is valid and meets the required conditions before building the chart.

• Make sure the array is not empty and contains at least one element to create the vertex.

• Verify that the array contains only non-negative integers, since negative values ​​or invalid data cannot represent valid vertices or edges

• Make sure the array index is within the appropriate range. They should start from 0 and go to n-1, where n is the total number of vertices in the graph.

• Confirm that the values ​​(connections) in the array are also in the valid range of 0 to n-1, ensuring that they correspond to existing vertices

• Check if there are duplicate connections or self-loops as they violate the conditions for a valid graph

• Verify that there are no lost connections, meaning that all vertices are connected to form a complete graph or connected components

DFS and BFS algorithms

• Depth-first search (DFS) is used to explore the vertices and edges of a graph by going as deep into each branch as possible before turning around

pseudocode

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

• Breadth-first search (BFS) is a graph traversal algorithm that traverses all vertices of the graph one level at a time. This makes it a good way to find cycles in charts

pseudocode

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

Complexity

• time complexity

The time complexity of both BFS and DFS is O(V E), where V is the number of vertices and E is the number of edges.

• Space complexity

The time complexity of BFS and DFS is O(V).

Step-by-step cycle detection process

Let us consider an example with a diagram

• Start monitoring visited vertices from an empty set

Visited set: {}

• Select any vertex as the starting point for the loop detection process. We select vertex A.

Visited set: {A}
Current Vertex: A

• Check the adjacent vertices of the current vertex (A). In this example, A's neighbors are B and D. Add them to the access set and identify A as its parent node

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

• B is the next access vertex in the access set.

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

• Explore B's surroundings. B's immediate neighbors are A, C, and E. A is already in the visited vertex set, but it is not the parent of B and therefore does not form a cycle.

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

• Continue to the next visited vertex, which is D.

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

• Found D’s acquaintance. A and E are D's nearest neighbors. Since A is already included in the access set and is the parent of D, there must be an edge (D -> A) connecting D to its parent. This indicates that the graph contains a cycle.

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

The process ends here. We have successfully detected the loop in the graph using BFS. That is (A->B->E->D->A).

in conclusion

In summary, for many applications it is important to be able to find loops in graphs built from arrays based on given parameters. Whether you use DFS or BFS, this process helps find possible loops and solve real-world problems involving networks, circuits, and relationships. Effective loop detection can increase the speed of your algorithm and ensure that your data is correct.

The above is the detailed content of Checks whether a graph built from an array based on a given condition contains a cycle. For more information, please follow other related articles on the PHP Chinese website!