8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Paresh Jan 24 '13 at 18:25
  • $\begingroup$ Yes, you are right. That is why I say "a root" but not "the root". $\endgroup$ – breezeintopl Jan 24 '13 at 18:41
  • 2
    $\begingroup$ In that case, isn't the definition sufficient for a linear time algorithm? $\endgroup$ – Paresh Jan 24 '13 at 18:43
  • 3
    $\begingroup$ 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? $\endgroup$ – Pål GD Jan 24 '13 at 19:52
  • 5
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jan 25 '13 at 4:18
19
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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|$. $\endgroup$ – Simon S Jan 25 '13 at 15:37
  • $\begingroup$ @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. $\endgroup$ – Paresh Jan 26 '13 at 14:22
  • $\begingroup$ 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! $\endgroup$ – breezeintopl Jan 26 '13 at 14:31
  • $\begingroup$ @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. $\endgroup$ – Paresh Jan 26 '13 at 15:20
0
$\begingroup$

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)$.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – adrianN Jan 25 '13 at 10:42
-1
$\begingroup$

Assuming you have a graph G=(V, E) given in adjacency list format. (to be clear here the list contains all outgoing edges from the source). You can construct the inverse of the graph G in linear time. Then you can iterate over the inverse graph and collect all vertices that have empty adjacency list. These vertices have no outgoing edge in the inverse graph which means they have no incoming edges in the original graph, therefore, these are your source vertices.

The running time is linear. Constructing the inverse of the graph takes a max of O(|V|+|E|) time. Iterating over the inverse of the graph takes O(|V|) time.

$\endgroup$
  • 1
    $\begingroup$ Honestly, computing the graph inverse sounds like a harder problem than finding the sources. I doubt that somebody who can't figure out how to get the sources could figure out how to reverse all the edges. $\endgroup$ – David Richerby Apr 27 '18 at 13:16
  • $\begingroup$ @DavidRicherby you said computing the graph inverse is harder. How do you define harder? If it is the time complexity it can be done in linear time. you can look the solution here [link ](stackoverflow.com/questions/40378152/…). The question is about a linear time solution that finds the source of a graph and my proposed solution does that. If you think it does not can you be specific and tell me how my algorithm does not satisfy the linear time requirement? $\endgroup$ – MGB Apr 28 '18 at 15:58
  • $\begingroup$ I mean conceptually harder. You’re saying that, to solve this exercise, the asker just needs to solve some other exercise, but that other exercise seems more difficult than the first one. $\endgroup$ – David Richerby Apr 28 '18 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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