2
$\begingroup$

Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles, which we call the branches. Describe a linear time algorithm that identifies all of the cycles and computes the length of each cycle. You can assume that the input is given as an array A, where A[i] is the neighbor of i, so that the graph has the edge (i, A[i]).

I kind of have an idea of how to approach the algorithm but have no idea what to do with the proof of my algorithm. So far I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex.

Edit: what I ended up writing

For all element i of A:
    If i has not been visited (not in the map)
        Store the index i as key and order of traversal as value in a map
        Add i to an array
        Get A[i] as neighbor j
        While j is not in the map (not visited)
            Store the j as key and order of traversal as value in a map
            Add j to an array
            j’s neighbor becomes j
        Endwhile
        If resulting index j is not already part of a confirmed cycle
            Store array into confirmed cycle set
            Get j’s order of traversal of from map as o
            Output length of cycle by deducting o from array length
            Output part of the array that is the solution 
            Store array from index array.size() - o to the end into solution set
        Endif
    Endif
Endfor
$\endgroup$
  • $\begingroup$ Do you have a concrete algorithm in mind? $\endgroup$ – Yuval Filmus Jan 30 at 5:36
  • $\begingroup$ @YuvalFilmus I ended up writing something like what's in the edited code chunk, but it is probably very wrong because that's just the way with pseudocode. $\endgroup$ – ern36 Jan 31 at 7:53
  • $\begingroup$ Have you tried something like Floyd’s linked list cycle detection algorithm? $\endgroup$ – Matthew C Jan 31 at 20:01
  • $\begingroup$ @JohnL. Yes, it is very helpful! Sorry I forgot to accept the answer. $\endgroup$ – ern36 Feb 4 at 11:42
1
$\begingroup$

Unfortunately, your algorithm is not correct.

Let us call a directed graph where each vertex has exactly one outgoing edge a unique-outgoing graph.

What does a unique-outgoing graph look like?

It consists of some directed tree and some directed cycles, all of which are disjoint except that every root of the trees is also a vertex of some cycle. Or, it looks like a collection of directed cycles with some directed trees attached to them.

graph for cs 120088, made at graphonline.ru/en/

Here is an illustration, which corresponds to the array $[5, 12, 3, 10, 9, 2, 3, 14, 14, 7, 2, 14, 5, 11, 4]$. There are two connected components in that graph. One component has the cycle of vertices 2, 3, 10 with two attached trees, the tree with vertices 2, 5, 0, 12, 1 and the tree with vertices 3, 6. The other component has the cycle of vertices 4, 9, 7, 14 with one attached tree, which has vertices 14, 8, 11, 13.

A simple algorithm

Here is the pseudocode, which is about as simple as possible.

Input: Array $arr[0], arr[1], \cdots, arr[n-1]$, such that the graph has the edge $(i, arr[i])$.

Procedure:

  1. $round\leftarrow 0$.
  2. Create array $first\_visited$ of $n$ zeros, where $first\_visited[i]$ will record the round at which $arr[i]$ is first visited. No element is visited at round 0.
  3. Loop $i$ from 0 to $n-1$:
    If $first\_visited[i]$ is 0:
    1. Increase $round$ by 1.
    2. $index\leftarrow i$
    3. Loop the following as long as $first\_visited[index]$ is zero, i.e., $arr[index]$ is not visited.
      1. $first\_visited[index]\leftarrow round$
      2. $index \leftarrow arr[index]$
    4. Now $first\_visited[index]$ must be non-zero.
      If $first\_visited[index]$ is equal to $round$, a new cycle has been found! Record (or output) the cycle as well as its length by chasing the elements starting from $index$. Otherwise, do nothing.

When we run the algorithm on the aforementioned array, we will visit

  • 0, 5, 2, 3, 10, 2 in round 1. The cycle 2, 3, 10 of length 3 will be recorded.

  • 1, 12, 5 in round 2.

  • 4, 9, 7, 14, 4 in round 3. The cycle 4, 9, 7, 14 of length 4 will be recorded.

  • 6, 3 in round 4.

  • 8, 14 in round 5.

  • 11, 14 in round 6.

  • 13, 11 in round 7.

Basically, the algorithm loops over all elements from index 0 to $n-1$. From each unvisited element, it makes an inner loop where it chases the next element via its outgoing edge, until it reaches a visited element. Each inner loop constitutes a round of chasing, during which each newly-visited element will be associated with the number of rounds happened so far.

The algorithm runs in $O(n)$ time with $O(n)$ space.

On your algorithm

I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex

You have got the basic idea. However, a new cycle might not be found when a vertex points back to a vertex that has been traversed, even if it is not part of any confirmed cycles. For example, consider the moment when your algorithm have visited 0, 5, 2, 3, 10, 2, 1, 12 and then 5 again. Vertex 5, although revisited, is not part of any cycle.

To ensure that a new cycle will be found when you revisited a vertex, the first visit to that revisited vertex must happen after the visit to the vertex i in your algorithm. That is why the variable $round$ is introduced in the above algorithm, which is, in fact, the only critical difference between the two algorithms.

Exercises

Here are a couple of exercises that help prove the above algorithm is correct.

Exercise 1. Show that there is exactly one cycle in each connected component.

Exercise 2. Prove the following invariant of the above algorithm. At the start of step 3.1, all visited vertices and edges so far form a unique-outgoing graph.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here is another way to characterize a connected uniq-outgoing graph: it is a rooted directed tree with all its edges pointing towards the root and an extra edge from the root to an existing vertex $\endgroup$ – John L. Feb 1 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.