Algorithms For Dummies

 

»

Directed: Edges have a single direction and can have these additional 

properties:

• 

Cyclic: The edges form a cycle that take you back to the initial vertex after 

having visited the intermediary vertexes.

• 

A-cyclic: This graph lacks cycles.

 

»

Undirected: Edges connect vertexes in both directions.

---

182

 

   

  PART 3 

 Exploring the World of Graphs

 

»

Weighted: Each edge has a cost associated with it, such as time, money, or 

energy, which you must pay to pass through it.

 

»

Unweighted: All the edges have no cost or the same cost.

 

»

Dense: A graph that has a large number of edges when compared to the 

number of vertexes.

 

»

Sparse: A graph that has a small number of edges when compared to the 

number of vertexes.

Relying on topological sorting

An  important  element  of  DAGs  is  that  you  can  represent  a  myriad  of  activities 

using them. However, some activities require that you approach tasks in a specific 

order. This is where topological sorting comes into play. Topological sorting orders 

all the vertexes of a graph on a line with the direct edges pointing from left to 

right. Arranged in such a fashion, the code can easily traverse the graph and pro-

cess the vertexes one after the other, in order.

When you use topological sorting, you organize the graph so that every graph ver-

tex leads to a later vertex in the sequence. For example, when creating a schedule 

for building a skyscraper, you don’t start at the top and work your way down. You 

begin with the foundation and work your way up. Each floor can represent a mile-

stone. When you complete the second floor, you don’t go to the third and then redo 

the second floor. Instead, you move on from the third floor to the fourth floor, and 

so on. Any sort of scheduling that requires you to move from a specific starting 

point to a specific ending point can rely on a DAG with topological sorting.

Topological sorting can help you determine that your graph has no cycles (because 

otherwise, you can’t order the edges connecting the vertexes from left to right; at 

least one node will refer to a previous node). In addition, topological sorting also 

proves helpful in algorithms that process complex graphs because it shows the 

best order for processing them.

You can obtain topological sorting using the DFS traversal algorithm. Simply note 

the processing order of the vertexes by the algorithm. In the previous example, the 

output appears in this order: A, C, E, F, D, and B. Follow the sequence in Figure 9-1 

and you notice that the topological sorting follows the edges on the external 

perimeter of graph. It then makes a complete tour: After reaching the last node of 

the topological sort, you’re just a step away from A, the start of the sequence.

---

CHAPTER 9