Definition
Topological sorting is useful in situations in which items or events must be arranged in a specific order. For example, topological sorting can model job scheduling.Modeling job schedules with graphs is called critical
path analysis(关键路线分析CPI).
The above figure adjacent matrix:
For a directed graph, the method that adds an edge thus needs only a single statement,
public void addEdge(int start, int end) // directed graph
{
adjMat[start][end] = 1;
}
The topological sorting algorithm
The idea behind the topological sorting algorithm is unusual but simple. Three steps are necessary:
1) Find a vertex that has no successors.
The successors to a vertex are those vertices that are directly “downstream” from it—that is, connected to it by an edge that points in their direction. If there is an edge pointing from A to B, then B is a successor to A.
2) Delete this vertex from the graph, and insert its label at the end of a list.
3) Step1 and step2 are repeated until all the vertices are gone. At this point, the list shows the vertices arranged in topological order.
Deleting is the heart of the algorithm. The algorithm works because if a vertex has no successors, it must be the last one in the topological ordering.
The topological sorting algorithm works on unconnected graphs(非连通图) as well as connected graphs（连通图）. One kind of graph the topological-sort algorithm cannot handle is a graph with cycles.A
topological sort must be carried out on a directed graph with no cycles. Such a graph is called a directed acyclic graph, often abbreviated DAG.
Java implement
Here are the steps involved:
1. Call noSuccessors() to find any vertex with no successors.
2. If such a vertex is found, put the vertex label at the end of sortedArray[] and
delete the vertex from graph.
3. If an appropriate vertex isn’t found, the graph must have a cycle.
public void topo() // toplogical sort
{
int orig_nVerts = nVerts; // remember how many verts
while(nVerts > 0) // while vertices remain,
{
// get a vertex with no successors, or -1
int currentVertex = noSuccessors();
if(currentVertex == -1) // must be a cycle
{
System.out.println("ERROR: Graph has cycles");
return;
}
// insert vertex label in sorted array (start at end)
sortedArray[nVerts-1] = vertexList[currentVertex].label;
deleteVertex(currentVertex); // delete vertex
} // end while
// vertices all gone; display sortedArray
System.out.print("Topologically sorted order: ");
for(int j=0; j<orig_nVerts; j++)
System.out.print( sortedArray[j] );
System.out.println("");
} // end topo
The noSuccessors() method uses the adjacency matrix to find a vertex with no successors. In the outer for loop, it goes down the rows, looking at each vertex. For each vertex, it scans across the columns in the inner for loop, looking
for a 1. If it finds one, it knows that that vertex has a successor, because there’s an edge from that vertex to another one. When it finds a 1, it bails out of the inner loop so that the next vertex can be investigated.
Only if an entire row is found with no 1s do we know we have a vertex with no successors; in this case, its row number is returned. If no such vertex is found, –1 is returned. Here’s the noSuccessors() method:
public int noSuccessors() // returns vert with no successors
{ // (or -1 if no such verts)
boolean isEdge; // edge from row to column in adjMat
for(int row=0; row<nVerts; row++) // for each vertex,
{
isEdge = false; // check edges
for(int col=0; col<nVerts; col++)
{
if( adjMat[row][col] > 0 ) // if edge to
{ // another,
isEdge = true;
break; // this vertex
} // has a successor
} // try another
if( !isEdge ) // if no edges,
return row; // has no successors
}
return -1; // no such vertex
} // end noSuccessors()
// --------------------------------------
Deleting a vertex is straightforward except for a few details. The vertex is removed from the vertexList[] array, and the vertices above it are moved down to fill up the vacant position. Likewise, the row and column for the vertex
are removed from the adjacency matrix, and the rows and columns above and to the right are moved down and to the left to fill the vacancies. These tasks are carried out by the deleteVertex(), moveRowUp(), and moveColLeft() methods, which you can examine in thetopo.java
. It’s actually more efficient to use the adjacency-list representation of the graph for this algorithm, but that would take us too far afield.
topo.java
// topo.java
// demonstrates topological sorting
// to run this program: C>java TopoApp
////////////////////////////////////////////////////////////////
class Vertex
{
public char label; // label (e.g. 'A')
// -------------------------------------------------------------
public Vertex(char lab) // constructor
{ label = lab; }
} // end class Vertex
////////////////////////////////////////////////////////////////
class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private char sortedArray[];
// -------------------------------------------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix to 0
adjMat[j][k] = 0;
sortedArray = new char[MAX_VERTS]; // sorted vert labels
} // end constructor
// -------------------------------------------------------------
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------------------------------------------
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
}
// -------------------------------------------------------------
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
// -------------------------------------------------------------
public void topo() // toplogical sort
{
int orig_nVerts = nVerts; // remember how many verts
while(nVerts > 0) // while vertices remain,
{
// get a vertex with no successors, or -1
int currentVertex = noSuccessors();
if(currentVertex == -1) // must be a cycle
{
System.out.println("ERROR: Graph has cycles");
return;
}
// insert vertex label in sorted array (start at end)
sortedArray[nVerts-1] = vertexList[currentVertex].label;
deleteVertex(currentVertex); // delete vertex
} // end while
// vertices all gone; display sortedArray
System.out.print("Topologically sorted order: ");
for(int j=0; j<orig_nVerts; j++)
System.out.print( sortedArray[j] );
System.out.println("");
} // end topo
// -------------------------------------------------------------
public int noSuccessors() // returns vert with no successors
{ // (or -1 if no such verts)
boolean isEdge; // edge from row to column in adjMat
for(int row=0; row<nVerts; row++) // for each vertex,
{
isEdge = false; // check edges
for(int col=0; col<nVerts; col++)
{
if( adjMat[row][col] > 0 ) // if edge to
{ // another,
isEdge = true;
break; // this vertex
} // has a successor
} // try another
if( !isEdge ) // if no edges,
return row; // has no successors
}
return -1; // no such vertex
} // end noSuccessors()
// -------------------------------------------------------------
public void deleteVertex(int delVert)
{
if(delVert != nVerts-1) // if not last vertex,
{ // delete from vertexList
for(int j=delVert; j<nVerts-1; j++)
vertexList[j] = vertexList[j+1];
// delete row from adjMat
for(int row=delVert; row<nVerts-1; row++)
moveRowUp(row, nVerts);
// delete col from adjMat
for(int col=delVert; col<nVerts-1; col++)
moveColLeft(col, nVerts-1);
}
nVerts--; // one less vertex
} // end deleteVertex
// -------------------------------------------------------------
private void moveRowUp(int row, int length)
{
for(int col=0; col<length; col++)
adjMat[row][col] = adjMat[row+1][col];
}
// -------------------------------------------------------------
private void moveColLeft(int col, int length)
{
for(int row=0; row<length; row++)
adjMat[row][col] = adjMat[row][col+1];
}
// -------------------------------------------------------------
} // end class Graph
////////////////////////////////////////////////////////////////
class TopoApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addVertex('G'); // 6
theGraph.addVertex('H'); // 7
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(0, 4); // AE
theGraph.addEdge(1, 4); // BE
theGraph.addEdge(2, 5); // CF
theGraph.addEdge(3, 6); // DG
theGraph.addEdge(4, 6); // EG
theGraph.addEdge(5, 7); // FH
theGraph.addEdge(6, 7); // GH
theGraph.topo(); // do the sort
} // end main()
} // end class TopoApp
////////////////////////////////////////////////////////////////
Reference:
Data Structure & Algorithm in JAVA.