Menu
Let's say that there is one vertex with the following property in a DAG:
All vertices are connected to it
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?
442
In a DAG, a source is a vertex without incoming edges; a sink is a vertex without outgoing edges.
A local sink is a node of a directed graph with no exiting edges, also called a terminal (Borowski and Borwein 1991, p. 401; left figure). A global sink (often simply called a sink) is a node in a directed graph which is reached by all directed edges (Harary 1994, p. 201; right figure).
(A) Every DAG G has at least one source and at least one sink.
To eliminate vertices, we check whether a particular index (A[i][j]) in the adjacency matrix is a 1 or a 0. If it is a 0, it means that the vertex corresponding to index j cannot be a sink. If the index is a 1, it means the vertex corresponding to i cannot be a sink.
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)
81
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
