拓扑排序

时间：2011-05-25 来源：brokencode

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。

一个有向无环图的拓扑序列不是唯一的：

进行拓扑排序的算法并不复杂：

1）在有向图中选一个没有前驱（入度为0）的顶点且输出之
2）从图中删除该顶点及它发出的弧（这样就得到了别的入度为0的顶点）。

重复上述2步，直到输出全部顶点。

从描述上可以看出，我们需要记录每个顶点的入度，实现如下：由于没有记录入度这一信息，先要求出一个入度数组，来表示每个顶点的入度，这个入度数组还要动态更新，当一个顶点被删除后，它指向的顶点的入度都要减1.

在邻接表实现的有向图中，拓扑序列生成过程如下：

public Iterator Topo(DirectedGraph g){//返回拓扑排序的队列迭代器
                LinkedQueue queue = new LinkedQueue();
                int[] InDegree = new int[g.size()];//存放每个顶点的入度
                for(int i = 0;i < g.size();i++)//求出每个顶点的入度
                {
                        Edge temp = VNodes[i].getFirst();
                        while(temp != null)
                        {
                                int index = temp.getEnd();
                                InDegree[index]++;
                                temp = temp.getNext();
                        }
                }
                
                for(int i = 0;i < g.size();i++)              //要进行n次循环找出拓扑序列
                {
                        for(int j = 0;j < InDegree.length;j++)
                                if(InDegree[j] == 0 && VNodes[j].getVisited() == false)
                                {
                                        queue.enqueue(VNodes[j]);
                                        VNodes[j].setVisited(true);
                                        Edge temp = VNodes[j].getFirst();
                                        while(temp != null)
                                        {
                                                int index = temp.getEnd();
                                                InDegree[index]--;
                                                temp = temp.getNext();
                                        }
                                }
                }
                
                return queue.iterator();
        }

测试一下，构造下面的有向图：

public static void main(String[] args) {
                // TODO Auto-generated method stub
                
                DirectedGraph g = new DirectedGraph();
                for(int i = 1;i < 7;i++)
                        g.addVNode("V" + i);
                
                g.addEdge(0, 1);
                g.addEdge(0, 2);
                g.addEdge(0, 3);
                g.addEdge(2, 4);
                g.addEdge(2, 1);
                g.addEdge(3, 4);
                g.addEdge(5, 3);
                g.addEdge(5, 4);
                
                System.out.println("输出拓扑序列：\n");
                Iterator it = g.Topo(g);
                while(it.hasNext())
                {
                        VNode node = (VNode) it.next();
                        System.out.print(node.getVNode() + "  ");
                }
}

结果如下：

输出拓扑序列：

V1 V3 V6 V2 V4 V5