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, 2020 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, 2020 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, 2020 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, 2020 at 9:55
  • $\begingroup$ The argument implies that any valid algorithm would take $\Omega(n^2)$ time. $\endgroup$
    – Yuval Filmus
    Oct 17, 2020 at 10:25

0

Reset to default

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.