Computer Club MNNIT
Would you like to react to this message? Create an account in a few clicks or log in to continue.

Graph Problem

4 posters

Go down

Graph Problem Empty Graph Problem

Post  shivang 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
shivang
shivang

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

Back to top Go down

Graph Problem Empty this should work....

Post  prani 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

Back to top Go down

Graph Problem Empty @BALLU

Post  mnnit.rahul 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

Back to top Go down

Graph Problem Empty ha ha

Post  Dee2306 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!
Dee2306
Dee2306

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

Back to top Go down

Graph Problem Empty @ETAWAH

Post  prani 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

Back to top Go down

Graph Problem Empty @BALLUUUUUUUUUUUUU

Post  mnnit.rahul 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

Back to top Go down

Graph Problem Empty Re: Graph Problem

Post  shivang 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....
shivang
shivang

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

Back to top Go down

Graph Problem Empty s@shivang

Post  mnnit.rahul 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

Back to top Go down

Graph Problem Empty Re: Graph Problem

Post  shivang 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
shivang
shivang

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

Back to top Go down

Graph Problem Empty Re: Graph Problem

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

haan bhai sahi bol raa hai Shocked

mnnit.rahul

Posts : 16
Join date : 2008-08-10

Back to top Go down

Graph Problem Empty 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