Graph Problem
4 posters
Page 1 of 1
Graph Problem
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...
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...
shivang- Posts : 22
Join date : 2008-08-11
Age : 35
Location : Tondon 174
this should work....
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..
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
@BALLU
..........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
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
mnnit.rahul- Posts : 16
Join date : 2008-08-10
ha ha
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..
So, how come b be a SINK..
But the ALGO above still proves it a SINK..
Dee2306- Posts : 7
Join date : 2008-08-12
Age : 35
@ETAWAH
its given that the graph has a sink,
agar graph me sink hai to kaam karega......
agar graph me sink hai to kaam karega......
prani- Posts : 15
Join date : 2008-08-12
@BALLUUUUUUUUUUUUU
but tumhare algo ke according to kaam kar raha hai
ab sink hai ya nahi ye kaise pata chalega timhare algo mein???
ab sink hai ya nahi ye kaise pata chalega timhare algo mein???
mnnit.rahul- Posts : 16
Join date : 2008-08-10
Re: Graph Problem
ya this algo will work only if der is a sink present in the graph.....
also giv the worst case....
also giv the worst case....
shivang- Posts : 22
Join date : 2008-08-11
Age : 35
Location : Tondon 174
s@shivang
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
Re: Graph Problem
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....
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
shivang- Posts : 22
Join date : 2008-08-11
Age : 35
Location : Tondon 174
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum