Algorithms For Dummies

Working on Directed Acyclic Graphs (DAGs)

DAGs are one of the most important kinds of graphs because they see so many 

practical uses. The basic principles of DAGs are that they

 

»

Follow a particular order so that you can’t get from one vertex to another and 

back to the beginning vertex using any route.

 

»

Provide a specific path from one vertex to another so that you can create a 

predictable set of routes.

You see DAGs used for many organizational needs. For example, a family tree is an 

example of a DAG. Even when the activity doesn’t follow a chronological or other 

overriding order, the DAG enables you to create predictable routes, which makes 

DAGs easier to process than many other kinds of graphs you work with.

However, DAGs can use optional routes. Imagine that you’re building a burger. 

The menu system starts with a bun bottom. You can optionally add condiments to 

the bun bottom, or you can move directly to the burger on the bun. The route 

always ends up with a burger, but you have multiple paths for getting to the 

burger. After you have the burger in place, you can choose to add cheese or bacon 

before adding the bun top. The point is that you take a specific path, but each path 

can connect to the next level in several different ways.

So  far,  the  chapter  has  shown  you  a  few  different  kinds  of  graph  configura-

tions,  some  of  which  can  appear  in  combination,  such  as  a  directed,  weighted, 

dense graph: