Groups > comp.games.development.programming.algorithms > #106

Skiena, Algorithms:2e-pg148, Graph Traversal - DAG/Topological Sorting

From	Veek M <vek.m1234@gmail.com>
Newsgroups	comp.games.development.programming.algorithms
Subject	Skiena, Algorithms:2e-pg148, Graph Traversal - DAG/Topological Sorting
Date	2015-08-28 14:21 +0530
Organization	Home
Message-ID	<mrp7c4$qnq$1@dont-email.me> (permalink)

Show all headers | View raw

"Directed acyclic graphs are called DAGs. They arise naturally in scheduling
problems, where a directed edge (x, y) indicates that activity x must occur
before y. An operation called topological sorting orders the vertices of a 
DAG to respect these precedence constraints. Topological sorting is 
typically the ?rst step of any algorithm on a DAG, as will be discussed in 
Section 5.10.1 (page 179)."

What does he mean by: 
"topological sorting orders the vertices of a DAG to respect these 
precedence constraints."

A DAG is directed and has no cycles therefore by definition an edge (x,y) is 
from x-to->y so why does he need topo..sort to order the vertices?

Back to comp.games.development.programming.algorithms | Previous | Next | Find similar

Thread

Skiena, Algorithms:2e-pg148, Graph Traversal - DAG/Topological Sorting Veek M <vek.m1234@gmail.com> - 2015-08-28 14:21 +0530

csiph-web