Question

Assume that the adjacency list representing a directed graph G has already been constructed.

Show how to determine whether G contains a universal sink, that is a vertex with in-degree |V | − 1 and out-degree 0, in time O(|V |).

**Please explain in detail

Answer 1

We are looking for a universal sink i.e. a vertex in degree of | V | −1 and out degree of zero
In the adjacent matrix the elements the element in row i represent the edges that are out-going from node i
to other nodes. And the elements in column j represent the edges that are in-coming to node j.

If vertex i is a universal sink according to the definition, the i-th row of the adjacency-matrix will be all “0”, and
the i-th column will be all “1” except the aii entry, and clearly there is only one such vertex.

We then describe an algorithm to find out if a universal sink really exist.

Starts from a11.

The u-row must contain 0’s only

The u-column must contain 1’s only

If current entry aij = 0 then j = j + 1 (take one step right); if aij = 1 then i = i +1 (take one step down).

In this way, it will stop at an entry akn of the last row or ank of the last column (n = |V|, 1 ≦ k ≦|V|).

Check if vertex k satisfies the definition of universal sink, if yes then we found it, if no then there is no universal sink.

Since we always make a step right or down, and checking if a vertex is a universal sink can be done in O(V), the total running time is O(V).

If there is no universal sink, this algorithm won’t return any vertex.

The algorithm terminates once we find a row of all zero’s whether that row represents a universal sink or not, thus guaranteeing
O(V ) running time.

If there is a universal sink u, the path starts from a11 will definitely meet u-th column or u-th row at some entry.

Once it’s on track, it can’t get out of the track and will finally stop at the right entry.

Repeating the above procedure, examining one row at a time from vertices that have not yet been
eliminated, we can find whether a universal sink exist or not. Thus, finding whether a graph has a
universal sink or not, can be determined in O(V ) time.