##
1.4.2 Topological Sorting

##
INPUT OUTPUT

**
Input Description:
**
A directed, acyclic graph
*
G=(V,E)
*
(also known as a partial order or
poset).
**
Problem:
**
Find a linear ordering of the vertices of
*
V
*
such that for
each edge
*
(i,j) \in E
*
, vertex
*
i
*
is to the left of vertex
*
j
*
.

##
Implementations

LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)

Combinatorica (Mathematica) (rating 3)

The Stanford GraphBase (C) (rating 3)

Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)

Algorithms in C++ -- Sedgewick (C++) (rating 3)

Xtango and Polka Algorithm Animation Systems (C++) (rating 2)

##
Related Problems

Bandwidth Reduction

Feedback Edge/Vertex Set

Job Scheduling

Sorting

Go to the corresponding chapter in the book

About the Book

Send us Mail

Go to Main Page

This page last modified on Tue Jun 03, 1997
.