CODEWITHSUNDEEP
algorithmgraphsink-vertex
Rohan Monga
Rohan Monga

Reputation: 1777

Detecting the sink in a directed acyclic graph

Let's say that there is one vertex with the following property in a DAG:

  1. All vertices are connected to it

  2. It is not connected to any vertex

This is usually called a sink vertex.

Is it possible to detect this vertex in O(n), where n is number of vertices in graph?

Upvotes: 5

Views: 7328

Answers (3)

Dr. belisarius
Dr. belisarius

Reputation: 61016

As there are no cycles in the graph, and all vertex connect with the sink, just select any starting node and start walking randomly. When you can't continue walking, you are at the sink, in at most n steps.

Once you walked n steps (or less and you can't continue), as the problem does not guarantee that there is a sink, you should check if you are at one. That adds another O(n). So the problem is O(2 n) = O(n)

Upvotes: 5

Heatsink
Heatsink

Reputation: 504

Provided you can count the number of edges in/out of a node in linear time, it's possible. First, find the vertices that have no outgoing edges (O(n) to scan all nodes). Your conditions are satisfied only if there's exactly one such vertex. Then, count its incoming edges (O(n) to scan all input edges). Your conditions are satisfied if there are exactly n-1 incoming edges. If either test fails, there's no sink vertex.

I'm assuming by "connected" you mean "connected by an edge", not "reachable by a path".

Upvotes: 0

jason
jason

Reputation: 241583

The best I can think of is O(n + m) which is O(n) if m is O(n).

Assuming a sink exists, do a topological sort of the graph. The minimal node in the sort is a sink. Note that topological sort is O(n + m).

I have previously provided an implementation here which can easily be modified for this problem.

Upvotes: 2

Related Questions