Next: 7.5.1 Test for Acyclicity
Up: 7. Directed Graphs
Previous: 7.4.1 Breadth First Search
- Digraph without any cycles.
- More general than trees
- See Figure 7.12 for some examples
- Useful in many applications, such as
- 1.
- Representing syntactic structure of arithmetic expressions
- 2.
- Representing task graphs
- 3.
- Precedence relations in many scheduling applications
Figure 7.12:
Examples of directed acyclic graphs
 |
Figure 7.13:
A cycle in a digraph
 |
eEL,CSA_Dept,IISc,Bangalore