Data Structures and Algorithms with Object-Oriented Design Patterns in C#
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_inline70470 and tex2html_wrap_inline70472, shown in Figure gif. Clearly tex2html_wrap_inline70470 is a tree but tex2html_wrap_inline70472 is not.

   figure48400
Figure: Two directed, acyclic graphs.


next up previous contents index

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