0
$\begingroup$

Let $G= (V,E)$ be a directed graph with $n$ vertices.
A sink is a vertex $s\in V$ such that for all $ v \in V$, $(v,s) \notin E$. Devise an algorithm that, given the adjacency matrix of $G$, determines whether or not $G$ has a sink in time $O(n)$.

Does this pseudocode code look good?

# Input: An adjacency matrix G

# Output: True if G has a sink and False if G does not have a sink.

Algorithm DetermineSink(G)
i←0
j←0
for 0 to len(G)
   if G[i,j] = 1 ∧ j ≠ i # if there is an edge emanating from i, it is not a sink.
    
     return False
   if G[j,i] = 0 ∧ j ≠ i # there exists no edge and hence it is not a sink
     
     return False
return True
Improve this question
$\endgroup$
9
  • $\begingroup$ What does "for 0 to len(G)" do? How are $i,j$ updated? $\endgroup$
    – Yuval Filmus
    Oct 17 '20 at 9:13
  • $\begingroup$ A simple adversary argument shows that given an adjacency matrix, you need to look at all entries in order to determine whether there is a sink or not. The adversary simply answers $A[i,j] = 0$ to all queries, unless the query is the last one in its row, in which case it answers $A[i,j] = 1$. $\endgroup$
    – Yuval Filmus
    Oct 17 '20 at 9:16
  • $\begingroup$ Yes I know that but I dont know how to change my code to check all the rows if they are zero when you get the 1 in any one column. $\endgroup$
    – jelli
    Oct 17 '20 at 9:47
  • $\begingroup$ If there is a sink,the adjacency matrix will contain all 1's except diagnol in one column and all 0's(except diagnol)in the corresponding row of the vertex. $\endgroup$
    – jelli
    Oct 17 '20 at 9:55
  • $\begingroup$ The argument implies that any valid algorithm would take $\Omega(n^2)$ time. $\endgroup$
    – Yuval Filmus
    Oct 17 '20 at 10:25

Your Answer

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

Browse other questions tagged or ask your own question.