## Chapter Nineteen. Digraphs and DAGs

When we attach significance to the order in which the two vertices are specified in each edge of a graph, we have an entirely different combinatorial object known as a digraph, or directed graph. Figure 19.1 shows a sample digraph. In a digraph, the notation `s-t` describes an edge that goes from `s` to `t` but provides no information about whether or not there is an edge from `t` to `s`. There are four different ways in which two vertices might be related in a digraph: no edge; an edge `s-t` from `s` to `t`; an edge `t-s` from `t` to `s`; or two edges `s-t` and `t-s`, which indicate connections in both directions. The one-way restriction is natural in many applications, easy to enforce in our implementations, and seems innocuous; but ...

Get Algorithms in Java, Third Edition, Part 5: Graph Algorithms now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.