对一个
有向无环图(Directed Acyclic Graph简称
DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若
∈E(G)，则u在线性序列中出现在v之前。
通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。
注意：
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
下面是Java实现：
package zieckey.datastructure.study.graph;
/**
* 有方向图
*
* @author zieckey
*/
public class DirectedGraph
{
private final int MAX_VERTS = 20;
private Vertex[] vertexList; // array of vertices
private int[][] adjMat; // adjacency matrix
private int nVerts; // current number of vertices
private char[] sortedArray; // sorted vert labels
/**
* 默认构造函数 初始化邻接矩阵
*/
public DirectedGraph( )
{
vertexList = new Vertex[MAX_VERTS];
sortedArray = new char[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++ )
{
adjMat[j][k] = 0;
}
}
}
/**
* 对有向图进行拓扑排序
*
* 无后继的顶点优先拓扑排序方法
* 1、思想方法
* 该方法的每一步均是输出当前无后继(即出度为0)的顶点。
* 对于一个DAG，按此方法输出的序列是逆拓扑次序。
* 因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。
* 若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。
* 若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。
*/
public void nonSuccFirstToplogicalSort()
{
int orig_nVerts = nVerts;
while(nVerts>0)
{
int delVertex = getNoSuccessorVertex();
if ( -1 == delVertex )
{
System.out.println("Error: This graph has cycles! It cannot be toplogical sorted.");
return;
}
sortedArray[nVerts-1] = vertexList[delVertex].label;
deleteVertex( delVertex );
}
System.out.print("Topologically sorted order: ");
for(int j=0; j<orig_nVerts; j++)
{
System.out.print( sortedArray[j] );
}
System.out.println("");
}
/**
* 找到没有后继节点的节点
* @return
*/
public int getNoSuccessorVertex()
{
boolean isEdge;
for ( int row = 0; row < nVerts; row++ )
{
isEdge = false;
for ( int column = 0; column < nVerts; column++ )
{
if ( adjMat[row][column]>0 )//大于0，表明有边指向其他点，说明有后继节点
{
isEdge = true;
break; //OK，继续下一个节点
}
}
if ( false == isEdge )//没有边，表明没有后继节点
{
return row;
}
}
return -1;
}
/**
* 删除一个节点
* @param delVertex
*/
public void deleteVertex( int delVertex )
{
if ( delVertex != nVerts-1 )//如果不是最后一个节点
{
//在节点列表中删除这个节点，所有后面的节点前移一格
for ( int i = delVertex; i < nVerts-1; i++ )
{
vertexList[i] = vertexList[i+1];
}
// 删除邻接矩阵的delVertex行和列，即所有后面的行和列都向前移动一格
// 所有delVertex行后的行，向上一个格
for ( int row = delVertex; row < nVerts - 1; row++ )
{
for ( int column = 0; column < nVerts; column++ )
{
adjMat[row][column] = adjMat[row + 1][column];
}
}
// 所有delVertex列后的列，向左一个格
for ( int column = delVertex; column < nVerts; column++ )
{
for ( int row = 0; row < nVerts - 1; row++ )
{
adjMat[row][column] = adjMat[row][column+1];
}
}
}
nVerts--;//减少一个节点
}
/**
* 添加一个节点
*
* @param lab
*/
public void addVertex( char lab ) // argument is label
{
vertexList[nVerts++ ] = new Vertex( lab );
}
/**
* 添加一条边
*
* @param start
* 起始点
* @param end
* 终点
*/
public void addEdge( int start, int end )
{
adjMat[start][end] = 1;
}
/**
* 添加一条边
*
* @param start
* 起始点
* @param end
* 终点
*/
public void addEdge( char startVertex, char endVertex )
{
int start = getIndexByLabel( startVertex );
int end = getIndexByLabel( endVertex );
if ( -1 != start && -1 != end )
{
adjMat[start][end] = 1;
}
}
/**
* 显示一个节点
*
* @param v
*/
public void displayVertex( int v )
{
System.out.print( vertexList[v].label );
}
public int getIndexByLabel( char lable )
{
for ( int i = 0; i < vertexList.length; i++ )
{
if ( lable == vertexList[i].label )
{
return i;
}
}
// 没有这个节点
return -1;
}
}
|
阅读(13082) | 评论(0) | 转发(0) |
