构建图定义

变量 说明
LinkID 有向边索引
SourceID 有向边的起始顶点索引
DestinationID 有向边的终止顶点索引
Cost 有向边权重

上图的信息表示为

0,0,1,1
1,0,2,2
2,0,3,1
3,2,1,3
4,3,1,1
5,2,3,1
6,3,2,1

拓扑排序

拓扑排序,其实就是寻找一个输入为0的顶点,该顶点是拓扑排序的第一个顶点。然后,将该顶点标记为删除;然后将与之相邻的顶点的入度减1,再继续寻找入度为0的顶点,直至所有的顶点都已经标记为删除或图中有环为止。

一种方式是遍历整个图中的顶点,寻找入度为0的顶点,然后将其删除,并更新相关顶点的入度。因此时间复杂度为o(v^2)

由于删除入度为0的顶点,只会更新与它相邻的顶点的入度,因此改进的方式是,先将入度为0的顶点放在栈或队列中。当队列不为空时,删除一个顶点,并更新与之相邻的顶点的入度。如果有一个顶点入度将为0,则将其加入队列。此时,拓扑排序的顺序就是顶点出列的顺序。时间复杂度为O(V+E)

拓扑排序实现

第1步,遍历图中的所有顶点,将入度为0的顶点加入队列;

第2步,从队列中删除一个顶点,打印顶点,并更新该顶点的邻接点的入度;如果邻接点的入度减1变为0,则加入队列

第3步,执行第2步,直到队列为空

public void topoSort() throws Exception{
        int count = 0;//判断是否所有的顶点都出队了,若有顶点未入队(组成环的顶点),则这些顶点肯定不会出队

        Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.
        //扫描所有的顶点,将入度为0的顶点入队列
        Collection<Vertex> vertexs = directedGraph.values();
        for (Vertex vertex : vertexs)
            if(vertex.inDegree == 0)
                queue.offer(vertex);

        //度为0的顶点出队列并且更新它的邻接点的入度
        while(!queue.isEmpty()){
            Vertex v = queue.poll();
            System.out.print(v.vertexLabel + " ");//输出拓扑排序的顺序
            count++;
            for (Edge e : v.adjEdges) 
                if(--e.endVertex.inDegree == 0)
                    queue.offer(e.endVertex);
        }
        if(count != directedGraph.size())
            throw new Exception("Graph has circle");
    }

results matching ""

    No results matching ""