Acyclic graphs are graphs that do not contain a graph cycle. This means that as you traverse the graph, once you leave a node, there is no path back to that node. Let’s take a closer look at acyclic graphs using an example.
Consider the following sequence of events: You are presented with the options for getting to work:
- Taking the bus
Either way, you’ll end up at the office. Once at work, you can’t undo the schedule of events and decide to take the car. In an acyclic graph, once a decision to traverse down a path is made, the decision cannot be undone since there is no path back to the previous node.
Let’s take this knowledge and build an acyclic graph!
We’ll begin by defining the sequence of events using
Create a node for the following events:
Name these nodes
If you take the car, you need to stop and get gas. If you take the bus, you’ll need to get to the bus stop before heading to work. Create two new nodes with data “Gas Station”, “Bus Stop”, named
No matter which method of transportation you take, you’ll end up at the office. Create one more node with data “Work” named
Create a constant
graph of type
Graph with all of the nodes defined above.
Lastly, we’ll combine the nodes using
addEdge(from:to:) for each pair of nodes:
"Car" -> "Gas Station" -> "Work"
"Bus" -> "Bus Stop" -> "Work"
Print the graph using the
printGraph() function to see the structure.