Things to be discussed here,
defines the following graph.
Since each node of a successor graph has a unique successor, we can also define a function succ(x,k) that gives the node that we will reach if we begin at node x and walk k steps forward. For example, in the above graph succ(4,6) = 2 because we will reach node 2 by walking 6 steps from node 4.
A straight forward way to calculate a value of succ(x,k) is to start at node x and walk k steps forward, which takes O(k) time. Later we will look into another method that uses preprocessing from which we can calculate succ(x,k) in O(logk) time.
Now lets, study about Cycle Detection Problem in Successor Graphs.
Cycle Detection
Let us consider a successor graph that only contains a path that ends in a cycle. Now here we may ask the following question that if we begin our walk at the starting node, what is the first node in the cycle and how many nodes does the cycle contain?
For example, in the following graph,
we begin our alk at node 1, the first node that belongs to the cycle is 4 and the cycle consists of three nodes (4, 5, and 6).
Algorithm to detect a cycle
A simple way to detect a cycle is to walk in the graph and keep track of all the visited nodes. Once a node is visited for the second time, we can conclude that the node is the first node in the cycle. Thus this method works in O(n) time and also uses O(n) memory.
Okay, that's cool, now let us take a look at better algorithms for cycle detection. The time complexity of such algorithms is still O(n), but they use only O(1) memory which is an important improvement if n is large. And this algorithm is known as Floyd's Algorithm.
Floyd's Algorithm
Floyd's algorithm walks forward in the graph using two pointers a and b. Both pointers begin at a node x that is the starting node of the graph. Then, on each turn, the pointer a walks one step forward and the pointer b walks two steps forward. The process continues until the pointers meet each other.
Let's simulate this with the above example, consider pointer a to be "red" node, pointer b to be "green", and both pointer at the same position to "purple".
At this point, the pointer a has walked k steps and the pointer b has walked 2k steps, so the length of the cycle divides k. Thus the first node that belongs to the cycle can be found by moving the pointer a to node x and advancing the pointers step by step until they meet again. After this, the length of the cycle can be calculated.
Implementation in C++
Input will be in an array of size N table, which will have succ(x), as given in the first figure, x = 1, 2, .. N. The i th position has succ(i).
- Successor Graphs
- Cycle Detection in Successor Graphs
- Floyd's Algorithm
- Practice Problems
Successor Graphs
Successor Graphs are those graphs in which out degree of each node is 1, i.e. exactly one edge start at each node. A successor graph consists of one or more components, each of which contains one cycle and some paths that lead to it.
Successor Graphs are also known as Functional Graphs as any successor graph corresponds to a function that defines the edges of the graph. The parameter for the function is a node of the graph, and the function gives the successor of that node.
For example, the function
defines the following graph.
Now lets, study about Cycle Detection Problem in Successor Graphs.
Cycle Detection
Let us consider a successor graph that only contains a path that ends in a cycle. Now here we may ask the following question that if we begin our walk at the starting node, what is the first node in the cycle and how many nodes does the cycle contain?
For example, in the following graph,
Algorithm to detect a cycle
A simple way to detect a cycle is to walk in the graph and keep track of all the visited nodes. Once a node is visited for the second time, we can conclude that the node is the first node in the cycle. Thus this method works in O(n) time and also uses O(n) memory.
Okay, that's cool, now let us take a look at better algorithms for cycle detection. The time complexity of such algorithms is still O(n), but they use only O(1) memory which is an important improvement if n is large. And this algorithm is known as Floyd's Algorithm.
Floyd's Algorithm
Floyd's algorithm walks forward in the graph using two pointers a and b. Both pointers begin at a node x that is the starting node of the graph. Then, on each turn, the pointer a walks one step forward and the pointer b walks two steps forward. The process continues until the pointers meet each other.
Let's simulate this with the above example, consider pointer a to be "red" node, pointer b to be "green", and both pointer at the same position to "purple".
- Initially both a & b at the same starting position
- Then a moves to 2 and b moves to 3.
- Then a moves to 3 and b moves to 5.
- Then finally a moves to 4 and b moves to 4.
Implementation in C++
Input will be in an array of size N table, which will have succ(x), as given in the first figure, x = 1, 2, .. N. The i th position has succ(i).
The same algorithm can be used to find the presence of a cycle in Linked List.
Practice Problems ( Random )
That's all for this article, in the next session we will be discussing Strongly Connected Component and Kosaraju's Algorithm and problems related to it and for now practice problems. ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA
If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA