Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
