# Is there an algorithm to test for an acyclic undirected graph, using edge data, not node data (e.g. adjacency matrix)

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.