# 4Topological Sort and Graph Traversals

The main theme of this chapter is acyclicity. A connected graph with no cycle is a tree. There are several ways to visit the vertices of a tree. More generally, if a digraph has no cycle, then its vertices may be ordered in such a way that if (*a, b*) is an edge, then the index associated with *a* is less than the one associated with *b*. This ordering is called a topological sort.

## 4.1. Trees

In this section, we consider only unoriented graphs. Directed trees will only be considered in section 8.6. Trees are ubiquitous in computer science to manipulate various forms of data. As an example, when considering formal grammar, we associate with a string, a parse tree (or derivation tree) according to the rules of the grammar used to build the string.

The tree depicted in Figure 4.1 permits one to associate a value with an expression to be computed. To that end, we have to properly traverse the tree (see postorder traversal below).

DEFINITION 4.1 (Tree).– *A* tree *is a simple connected acyclic graph. A* *simple graph whose connected components are trees ^{1} is a* forest.

*A*(

**rooted tree**is a pair*G, v*

_{0})

*where G is a tree and v*

_{0}

*is a vertex of G. In that case, a vertex u has*level (

*or*height)

*k when*d(

*v*

_{0},

*u*) =

*k. This naturally induces an orientation of the edges from vertices of level*ℓ

*to adjacent vertices ...*

Get *Advanced Graph Theory and Combinatorics* now with O’Reilly online learning.

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