Graph Problem

Go down

Graph Problem

Post  shivang on Tue Aug 12, 2008 3:58 pm

Given an Adjacency Matrix representation of A directed Graph u have to find in O(V) time complexity if der is a Universal Sink in the Graph

Universal Sink:A vertex V is said to be universal sink if the rest |V| -1 vertices point to it and the vertex V itself doesnot have any out edge..i.e. it does not point to any other vertex.
example : consider the following Adj Matrix
..........a.....b.....c.....d
a.......0......1.....0.....1
b.......0......0.....0.....0
c........0......1......1.....1
d.........1......1.....0.....0

here node "b" is the universal sink

P.S. Ankur saale tu answer nahi dega... cheers Cool Evil or Very Mad
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

this should work....

Post  prani on Wed Aug 13, 2008 2:35 am

i=0,j=0;
while(i<n and j<n)
{
if(graph(i,j)==1)
i=i+1;
else j=j+1;
}
return i;
if i>=n no sink exists..
else i is the sink..

prani

Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

@BALLU

Post  mnnit.rahul on Wed Aug 13, 2008 7:58 am

..........a.....b.....c.....d
a.......0......1.....0.....1
b.......1......0.....0.....0
c........0......1......1.....1
d.........1......1.....0.....0

tiwari apna algo is input par chrck kar
according to ur algo b comes out to be sink but it is actuially not
bounce lol!

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

ha ha

Post  Dee2306 on Wed Aug 13, 2008 8:05 am

Ya, Right.. In the Above ARRAY, there is a path from b to a,
So, how come b be a SINK..
But the ALGO above still proves it a SINK.. lol!
avatar
Dee2306

Posts : 7
Join date : 2008-08-12
Age : 30

View user profile

Back to top Go down

@ETAWAH

Post  prani on Wed Aug 13, 2008 8:18 am

its given that the graph has a sink,
agar graph me sink hai to kaam karega......
lol!

prani

Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

@BALLUUUUUUUUUUUUU

Post  mnnit.rahul on Wed Aug 13, 2008 8:40 am

but tumhare algo ke according to kaam kar raha hai
ab sink hai ya nahi ye kaise pata chalega timhare algo mein???

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

Re: Graph Problem

Post  shivang on Wed Aug 13, 2008 9:00 am

ya this algo will work only if der is a sink present in the graph.....
cheers
also giv the worst case....
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

s@shivang

Post  mnnit.rahul on Wed Aug 13, 2008 10:17 am

abe isme to har case mein loop n time hi chalega as either i increases or j so best and worse case should be same

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

Re: Graph Problem

Post  shivang on Wed Aug 13, 2008 12:07 pm

mnnit.rahul wrote:abe isme to har case mein loop n time hi chalega as either i increases or j so best and worse case should be same

Bhai loop n times kyun chalega....the cond is that i and j shud be less than n...so in the worst case the loop can run for 2n times.... cheers Cool
and also we will hav to check whether all other vertices point to that vertex...
so in the worst case the total no of steps wud be 3V...where V=no of vertices cheers I love you
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: Graph Problem

Post  mnnit.rahul on Wed Aug 13, 2008 12:46 pm

haan bhai sahi bol raa hai Shocked

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

Re: Graph Problem

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum