Write an algorithm that given a directed graph g nds a sink


A vertex s of a directed graph G(V;E) is called a sink if for every vertex v ∈ V - {s}, (v, s) ∈ E and (s, v) ∉ E. In other words, every vertex has an edge to s and no edge froms. Write an algorithm that given a directed graph G, nds a sink or returns that one does not exist in only O(|V|) time. The graph is given by adjacency matrix A. Notice that a running time of O(|V|) is remarkable given that the input can have potentially O(|V|^2) edges.

Solution Preview :

Prepared by a verified Expert
Basic Computer Science: Write an algorithm that given a directed graph g nds a sink
Reference No:- TGS02241941

Now Priced at $20 (50% Discount)

Recommended (99%)

Rated (4.3/5)