| Directed Acyclic Graph |
Article Index for Directed |
Website Links For Graph |
Information AboutDirected Acyclic Graph |
| CATEGORIES ABOUT DIRECTED ACYCLIC GRAPH | |
| graph families | |
|
In Computer Science and Mathematics , a directed acyclic graph, also called a '''dag''' or '''DAG''', is a Directed Graph with no Directed Cycle s; that is, for any vertex ''v'', there is no nonempty Directed Path starting and ending on ''v''. DAGs appear in models where it doesn't make sense for a vertex to have a path to itself; for example, if an edge ''u''→''v'' indicates that ''v'' is a part of ''u'', such a path would indicate that ''u'' is a part of itself, which is impossible. TERMINOLOGY A ''source'' is a vertex with no incoming edges, while a ''sink'' is a vertex with no outgoing edges. A finite DAG has at least one source and at least one sink. The ''length'' of a finite DAG is the length (number of edges) of a longest directed path. PROPERTIES Every directed acyclic graph has a Topological Sort , an ordering of the vertices such that each vertex comes before all vertices it has edges to. In general, this ordering is not unique. DAGs can be considered to be a generalization of Tree s in which certain subtrees can be shared by different parts of the tree. In a tree with many identical subtrees, this can lead to a drastic decrease in space requirements to store the structure. Conversely, a DAG can be expanded to a forest of rooted trees using this simple algorithm:
If we explore the graph without modifying it or comparing nodes for equality, this forest will appear identical to the original DAG. Some algorithms become simpler when used on DAGs instead of general graphs. For example, search algorithms like Depth-first Search without Iterative Deepening normally must mark vertices they have already visited and not visit them again. If they fail to do this, they may never terminate because they follow a cycle of edges forever. Such cycles do not exist in DAGs. APPLICATIONS Directed acyclic graphs have many important applications in Computer Science , including:
|
|
|