com.mhhe.clrs2e
Class TopoSort

java.lang.Object
  |
  +--com.mhhe.clrs2e.TopoSort

public class TopoSort

extends java.lang.Object

Class that topologically sorts a DAG. Based on the Topological-Sort procedure on page 550 of Introduction to Algorithms, Second edition.

Nested Class Summary

private class

TopoSort.TopoSortDFS Inner class to do DFS but with inserting finished vertices onto the front of the linked list.

Field Summary

private com.mhhe.clrs2e.SentinelDLL

list A linked list of vertices.

Constructor Summary

TopoSort()

Method Summary

com.mhhe.clrs2e.Vertex[]

topologicalSort(com.mhhe.clrs2e.AdjacencyListGraph g) Performs a topological sort on a graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

list

private com.mhhe.clrs2e.SentinelDLL list

A linked list of vertices.

Constructor Detail

TopoSort

public TopoSort()

Method Detail

topologicalSort

public com.mhhe.clrs2e.Vertex[] topologicalSort(com.mhhe.clrs2e.AdjacencyListGraph g)

Performs a topological sort on a graph.

Parameters:

g - The graph.

Returns:

An array of the vertices of g in which the vertices appear in the array in topologically sorted order.