Let (V, E) be a directed graph. A node upsilon Element V is an attractor iff ups

Question

Let (V, E) be a directed graph. A node upsilon Element V is an attractor iff upsilon is a sink, and moreover, for every node u Element V with u notequalto upsilon, (u, upsilon) Element E. Note that a graph can have at most one attractor. We want an algorithm that will identify an attractor in an input graph (V, E) if there is one. Assume that a graph is represented as an adjacency matrix A, with the nodes in V labelled 1 to n. The function Attractor(A[., ], n) should return i if node i is an attractor, and 0 if the graph has no attractor. (a) Give an O(n^2) algorithm for the problem, using pseudo-code. (b) (Harder.) Give an O(n) algorithm for the problem, using pseudo-code. Maximum marks will (only) be given for a solution that is both readable, intelligible, carefully explained and analysed, and, importantly, runs in linear time.

Explanation / Answer

In a cyclic graph the sink node is the node from which there is no edge which emerge out of it.

To find sink node we have to traverse through all the edges and for each edge we will find from which node it is emerge.

and we also check if a node is already marked or not. check for unmarked nodes.

G(V,E)

V: number of Vertices

E: number of edges

(a)

As there is upmost 1 sink node.

for each vertex u:

u.might_be_sink := true

for each vertex u:

if u.might_be_sink:

for each other vertex v:

if u -> v:

give up on u and try next candidate

else:

v.might_be_sink := false

if v -> u:

v.might_be_sink := false

else:

give up on u and try next candidate

u is a sink.

As there is two for loop for each inner loop one vertex we are discovring is not to be a sink node.

So in worst case we have to traverse inner loop n times for all outer vertex.

Time complexity = O(n*n)

= O(n^2)

(b) Pseudo:

1. Create an array arr[E]

initilise arr with 1

for(int i=0;i<E;i++)

arr[i] = 1;

2.Now traverse all the edges one by one

say u -> v

and mark arr[u] = 1

3. bool found -> false

Now traverse through arr[] i in 0 to E

if any unmarked node is founded then

found -> true

return i index of node

if found == false

return 0

This algorithm run through the number of E + number of V.

So time complexity is O(V+E) and we have adjacency matrix on n node and n edge.

T(n) = O(n+n)

t(n) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.