数据结构——有向图（拓扑排序算法）

zieckey

    　对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若           
                ∈E(G)，则u在线性序列中出现在v之前。
         
                  　通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。
         
                        
[color="#ff0000"]注意：
        
                  　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
                  　②若图中存在有向环，则不可能使顶点满足拓扑次序。

                  　③一个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; jorig_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 = 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.label )
            {
                return i;
            }
        }
        // 没有这个节点
        return -1;
    }
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/16292/showart_528883.html