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-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.
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.
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
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
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
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
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).
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 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!