数据结构与算法——拓扑排序(引例、拓扑排序、伪代码、代码、关键路径问题)

简介: 数据结构与算法——拓扑排序(引例、拓扑排序、伪代码、代码、关键路径问题)

引例

以一个例子开始引进拓扑排序 image.png

根据这个表,我们可以每个课程表示为图的顶点,<V,W>表示边,V为W的预修课程,画出图:

这样就构成了一个 AOV网络,即Activity On Vertex 网络

给每个学期排课,根据这个图排成的序列成为拓扑序:

拓扑排序

  • 如果图中从V到W有一条有向路径,则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序
  • 获得一个拓扑序的过程就是拓扑排序
  • AOV如果有合理的拓扑序,则必定是有向无环图(Directed Acyclic Graph,DAG

算法伪代码

void TopSort()
{
    for(each vertex V in the graph)
    {
        if(Indegree[V] == 0)  //这里把所有入度为0的顶点入队
            Enqueue(V, Q);
    }
 
    while(!IsEmpty(Q))
    {
        V = Dequeue(Q);    //从队列中取出顶点,该顶点的入度一定为0
        输出(V); // 输出V,或者记录V的输出序号
        cnt++;   //记录输出的顶点的个数,用于判断图中是否有回路
 
        for(each adjacent vertex W of V)  //把V的所有邻接点的入度都减1
        {
            if(--Indegree[W] == 0)
                Enqueue(W, Q);
        }
    }
 
    if(cnt != number of vertices in the graph)  //判断输出顶点的个数(即入度为0的顶点个数)是否与图中的顶点数量相等,如果不相等,则说明图中有回路
        Error("The graph contains a cycle");
}

时间复杂度

稀疏图:

稠密图:

此算法可以用来检测有向图是否DAG。

代码(C语言)

/* 邻接表存储 - 拓扑排序算法 */
 
bool TopSort( LGraph Graph, Vertex TopOrder[] )
{ /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int Indegree[MaxVertexNum], cnt;
    Vertex V;
    PtrToAdjVNode W;
       Queue Q = CreateQueue( Graph->Nv );
 
    /* 初始化Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        Indegree[V] = 0;
        
    /* 遍历图,得到Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        for (W=Graph->G[V].FirstEdge; W; W=W->Next)
            Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */
            
    /* 将所有入度为0的顶点入列 */
    for (V=0; V<Graph->Nv; V++)
        if ( Indegree[V]==0 )
            AddQ(Q, V);
            
    /* 下面进入拓扑排序 */ 
    cnt = 0; 
    while( !IsEmpty(Q) ){
        V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */
        TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */
        /* 对V的每个邻接点W->AdjV */
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
            if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */
                AddQ(Q, W->AdjV); /* 则该顶点入列 */ 
    } /* while结束*/
    
    if ( cnt != Graph->Nv )
        return false; /* 说明图中有回路, 返回不成功标志 */ 
    else
        return true;
}

关键路径问题

关键路径问题是拓扑排序的一个应用,用到了另外一种网络。

AOE(Activity On Edge)网络,一般用于安排项目的工序。

关键路径:由绝对不允许延误的活动组成的路径。

以下就是一个比较典型的AOE网络图:

画出了这个图,我们就可以知道:

  1. 整个工程的工期为18(Earliest[ 8 ] = 18
  2. 哪个组有机动时间(D<i,j> = Latest[ j ] - Earliest[ i ] - C<i,j>)
目录
相关文章
|
4天前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
|
4天前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
4天前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
28天前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
TU^
|
1月前
|
搜索推荐 算法 测试技术
数据结构~~排序
数据结构~~排序
TU^
17 1
|
1月前
|
搜索推荐 算法 测试技术
数据结构——排序
数据结构——排序
13 1
|
19天前
|
算法 Java 调度
Java数据结构与算法:拓扑排序
Java数据结构与算法:拓扑排序
|
1月前
|
搜索推荐 算法 Shell
数据结构和算法——排序算法的比较和排序综测测验
数据结构和算法——排序算法的比较和排序综测测验
11 0
|
1月前
|
算法 C语言
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
15 0
|
25天前
|
算法 C++ Python
数据结构与算法===贪心算法
数据结构与算法===贪心算法