Acyclic

What Does Acyclic Mean?

Acyclic is an adjective used to describe a graph in which there is no cycle, or closed path. In other words, it is a path with no repeated vertices (nodes that form the graph, or links between vertices), excluding the starting and ending vertices.

Advertisements

In computer science, it is used in the phrase “directed acyclic graph” (DAG). Technically, DAG is a graph formed by connecting different vertices with edges that are directed in a manner that does not allow navigating through a sequence that can have a vertex passing through it more than twice; therefore, there is no closed path.

Techopedia Explains Acyclic

The concept of DAG is used to design word games like Scrabble and scientific research applications based on biology and genetics. DAG is also used in building models in mathematics, computer science, electronic circuits, compile operations, computing related values on forms, etc. DAGs are used in models to illustrate the flow of information through a system. DAG is a better alternative to other techniques in data structures by providing memory use optimization and an improvement in performance.

A cycle is a path traversed through a sequence of vertices, such that both the start and end vertices are the same point. If a graph has no such cycles, then it is referred to as acyclic. For example, consider the three vertices, X, Y and Z linked in a graph. While traversing from any of the three vertices through its structure in different possible ways, if one cannot return back to the same starting vertex without visiting any vertex (excluding the starting vertex or point) twice, then it is an Acyclic graph.

The length of the shortest cycle and the circumference of an acyclic graph is defined to be infinity. Examples of acyclic graphs are Trees and Forests. An acyclic and undirected graph with any two vertices connected by only one path is called a tree. A family tree is a good example of the concept of a directed acyclic tree. A forest is an undirected graph whose subsets are trees.

Advertisements

Related Terms

Margaret Rouse
Technology Expert

Margaret is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical business audience. Over the past twenty years, her IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages.