Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Given a directed acyclic graph $D = (V,A)$, a vertex $v \in V$ is a source if its indegree is zero, meaning that it has only outgoing arcs.

Does there exist a linear time algorithm to find a source in a given directed acyclic graph?

Follow-up question: Can one in linear time find all sources?

share|improve this question
2  
By root, do you mean a node which has all outgoing edges and no incoming edges? If so, there may be more than one roots. –  Paresh Jan 24 '13 at 18:25
    
Yes, you are right. That is why I say "a root" but not "the root". –  breezeintopl Jan 24 '13 at 18:41
2  
In that case, isn't the definition sufficient for a linear time algorithm? –  Paresh Jan 24 '13 at 18:43
3  
What is the data structure? Are you given an adjacency matrix, neighborhood lists, adjacency list or what? Can you check the (incoming) neighborhood of a vertex in time proportional to its size? –  Pål GD Jan 24 '13 at 19:52
5  
If you mean linear in the number of vertices, you should indicate that. Also, adjacency lists are ambiguous for directed graphs - are you listing incoming edges, outgoing edges, both in separate lists, or both together? –  Yuval Filmus Jan 25 '13 at 4:18
show 4 more comments

2 Answers 2

As Yuval mentions, the datastructure is important here. I'll try to give a solution for some of the types of adjacency lists:

  1. Incoming edge list: For each node, there is a list of vertices from which there is an incoming edge to this node. You can simply scan all vertices and check if the size of their adjacency list is $0$ or not. A size $0$ list means no incoming edges, so the node is either a source or disconnected. Assuming a connected graph, this scan of each vertex will give you a list of all sources (or you can stop after finding one) in $O(|V|)$ time - linear in the number of vertices.
  2. Outgoing edge list: For each node, there is a list of vertices to which there is a directed edge from this node. Keep a bit-string with each bit representing a vertex, initialized to 0. Starting from the first node, start scanning its list for vertices to which there is an outgoing edge from this. Every such node (neighbour) cannot be a source, so keep setting their corresponding bit in the bit-string. At the end, all vertices whose corresponding bits are still unset, are the source vertices. You can do this in time linear in the size of the graph - $O(|V| + |E|)$.
  3. Both lists together: For each vertex, there is a mixed list of vertices which have an edge to or from this vertex, with some other attribute indicating which of the two is actually the case. The approach is similar to 2 above, with the addition that any incoming edge immediately rules out the current vertex (and you can mark its bit set). Unlike in point 2 where you need to go through all vertices, here, you might find some source sooner. If you don't stop, you will have all sources. For both cases, time is again linear in the size of the graph - $O(|V| + |E|)$.
  4. Both lists separately: Just pick the incoming edge list and follow 1.

As a side note, if choosing the datastructure is in your hands, you might want to analyze what all operations you intend to perform, and how frequently, and choose an appropriate datastructure.

Edit: For case 1, if you have a dag where the number of sources is very small as compared to $|V|$ (eg, in a tree with one source), and where the average distance from any vertex to a source is small as compared to $|V|$ and you only want any one source, you can use a faster on average algorithm (although worst case asymptotic complexity will be the same). Select any vertex at random, and go to any of its parent (from the incoming edge list), and on to its parent and so on, till you reach a node which has no parent - a source. This small gain of efficiency is for very limited types of graphs with a slightly more complex algorithm.

share|improve this answer
1  
For incoming edge lists, in case you only need to find a single source, wouldn't it be faster to just follow an arbitrary edge to get the predecessor, until you reach a source? Especially if the graph is flat, i.e the average distance to every source of every vertex is much smaller than $|V|$. –  Simon S Jan 25 '13 at 15:37
    
@SimonS Even though the worst case complexity is the same (eg., a linear chain), you might make it faster if the graph has very few sources (in comparison to $|V|$) and average distance from any vertex to a source is very small - eg. a star graph with the center as the source. Only having the condition that you mention is not sufficient - eg 1->2, 1->3, 4->2, 4->3 - (you can have a graph with avg distance 0.5 and |V|/2 sources) average distance is small, but both algorithms will give same/similar expected time. I'll add it to my answer though. –  Paresh Jan 26 '13 at 14:22
    
Thank you for your answer! I think what I mean is the second case, outgoing list. BTW, why it is O(|V|+|E|)? I know |E|, because you have to scan all the edges, but where the |V| from? Thank you! –  breezeintopl Jan 26 '13 at 14:31
    
@breezeintopl It is a way of representation. You check each edge once and each vertex a constant number of times too. At the very least, in the end you have to scan all vertices once to see which bits are unset. Another way to look at it is that an adjacency list uses $\Theta(|V| + |E|)$ space - store a vertex and its list of edges. And you are traversing through the whole list. Of course, since $|E|$ can range from $O(|V|)$ to $O(|V|^2)$, you could just skip the $|V|$ part. See an example for BFS. –  Paresh Jan 26 '13 at 15:20
add comment

Let's consider a simpler question. Suppose that you know your graph is a tree. Then you can find the source node in linear time. Just select a random node, if it is the root then you have your answer, if not it should be a child or parent then traverse back until you reach the root. This can be done in $O(|V|-1)$.

share|improve this answer
2  
If your data structure doesn't include a list of in-edges for a node, then finding the parent already takes O(m) (in trees hence O(n) time. Since the path to the root of the tree can be linearly long, this is only a quadratic solution. But if you have in-edges, then finding some node with 0 in edges is trivial. –  adrianN Jan 25 '13 at 10:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.