1.4.2 Topological Sorting

Problem Input | Problem Output 


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 .