Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Directed Acyclic Graphs

For certain applications it is convenient to deal with graphs that contain no cycles. For example, a tree (see Chapter gif) is a special kind of graph that contains no cycles.

Definition (Directed Acyclic Graph (DAG)) 

A directed, acyclic graph    is a directed graph that contains no cycles.

Obviously, all trees are DAGs. However, not all DAGs are trees. For example consider the two directed, acyclic graphs, tex2html_wrap_inline70215 and tex2html_wrap_inline70217, shown in Figure gif. Clearly tex2html_wrap_inline70215 is a tree but tex2html_wrap_inline70217 is not.

   figure48212
Figure: Two directed, acyclic graphs.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.