0
$\begingroup$

Given an adjacency matrix or other data based on the nodes, there are many algorithms for determining whether the graph is acyclic (e.g. row reduction or leaf trimming).

If I have only a set of edges (e.g. ${(a,b), (b,c), (d,b)}$), I could obviously convert that into an adjacency matrix and proceed from there.

I'm wondering if there is a good algorithm that works directly with the edges.

$\endgroup$

1 Answer 1

2
$\begingroup$

You could use a disjoint set (union-find) data structure and iterate through the edges one by one. For each edge $(u, v)$, if the two vertices already belong to the same subset, then the graph is not acyclic. Otherwise, you merge the subset containing $u$ with the subset containing $v$. If all edges are added successfully, the graph is acyclic.

This runs in $O(E\alpha(V))$, where $V$ is the number of vertices, $E$ is the number of edges and $\alpha$ is the inverse Ackermann function.

In principle, however, I don't think that this is any faster than iterating through the edges to build an adjacency list and then use that for determining if the graph is acyclic.

$\endgroup$
1
  • $\begingroup$ "I don't think that this is any faster than …". Right. Some people have trouble relating algebraic manipulation to "reality". I wanted a graphical rather than an algebraic solution. And this is it. Thanks. $\endgroup$ Mar 10 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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