数据结构什锦（六）——走近图论

序言

让我们从一个题目开始图的学习。

哥尼斯堡桥问题

18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如概述图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。

大数学家欧拉把它转化成一个几何问题——一笔画问题。他用顶点来表示各个陆地区域，用边表示桥，并以此建模画出了一个图。他不仅解决了此问题，且给出了连通图可以一笔画的充要条件是：奇点的数目不是0个就是2个（连到一点的数目如果是奇数条，就称为奇点；如果是偶数条，就称为偶点。要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端。因此任何图能一笔画成，奇点要么没有，要么在两端）

由此，图论和几何拓扑正式诞生了。

图的定义

一个图由非空的顶点集合V和一个描述顶点之间关系（边或弧）的集合VR组成。

如G＝(V,VR)，V=(v1,v2,v3,v4,v5)，VR=((v1,v2),(v3,v4),(v5,v1))。

图又分为有向图和无向图，简单的来说就是边是否有向。是只能由一个顶点单向到达另一个顶点，还是两边都可以到达对方。一般用箭头和直线来加以区分，在VR中则分别用括号（有向）和尖括号<无向>来加以区分。完全有向图和完全无向图指的是任意一点都有一条路径到达图上其他任意一点的图。

顶点又有度，入度，和出度的概念。与一个顶点相关联的边的数目叫做度，，以该起点为终点的边到的数目叫做入度，以该顶点为起点的边的数目叫做出度。

路径与路径长度的定义和树相同。若一条路径的起点和终点都是同一个点，就称为回路。如果路径中的顶点不重复出现，就叫做简单路径。如果除了起点和终点相同外其余顶点不重复，就是简单回路。

如果一个图的顶点和对应关系都是另一个图对应的子集，那么这个图就是另一个图的子图。

若图中有一条路径是独立的，无法通过另一部分路径到达，就说它不连通，否则就是连通图。无向图的极大连通子图称为的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量

生成树是指连通图G包含全部n个顶点的一个极小连通子图。对于该生成树任意加上一条原图的边则必然出现回路，任意减少一条边则必定非连通。

图的储存方式

图的储存方式有几种。这里将重点介绍邻接矩阵，邻接表两种方法。十字链表法和邻接多重表则只作为拓展了解即可。

在开始之前我们先强调一点。任何数据结构的意义都在于“快”，也就是将其运用于实际生产中追求计算机处理效率最大化。而我们程序员所需要的处理操作无非也就四种：增、删、查、改。我们讨论的任何优缺点都是基于这四种操作之上的情况的。

那么话不多说正式开始吧。

领接矩阵

现在假设有顶点i与j，我们定义一个矩阵A来储存图。当两个顶点i、j是连通的，就定义A[i][j]=1；否则定义此处为0。如果是无向图，那么也有A[j][i]=1。一般为了节省储存空间，我们只操作一半的矩阵就好。如果是带权图，就把1修改为权重w_ij。

我们定义邻接矩阵的结构如下。

struct Graph{
    int V;//顶点 Vertices
    int E;//边 Edges
    int **Adj;//表示二维矩阵
};

再考虑一下实现方式，为了方便起见，我们可以先读入顶点的名称，然后再读取顶点对的名字（也就是边）。下面是实现的代码。

struct Graph*adjMatrixOfGraph(){
    //读取无向图的领接矩阵
    int i,u,v;
    struct Graph*G= (struct Graph*)malloc(sizeof (struct Graph));

    if(!G){
        printf("Memory Error!\n");
        exit(-1);
    }
    scanf("Number of Vertices:%d, Number of Edges:%d",&G->V,&G->E);//输入顶点数和边数
    G->Adj= malloc(sizeof (int)*G->V*G->V);//创建矩阵

    for (u = 0; u < G->V; ++u) {
        for (v = 0; v < G->V; ++v) {
            G->Adj[u][v]=0;
        }
    }//初始化矩阵

    for (i = 0; i < G->E; ++i) {
        scanf("Reading Edges:%d %d",&u,&v);
        G->Adj[u][v]=1;
        G->Adj[v][u]=1;
    }//读取边的信息
    return G;
}

领接矩阵的优点是在判断顶点间的关系时可以实现随机读取，时间复杂度为O(1)。但缺点是如果要确定边和点的数目，就必须要遍历完整个矩阵。除此之外，还有储存空间开销大，删除顶点、边不方便等问题。

邻接表

邻接表是一个链式储存结构。在邻接表中，每一个顶点都建立一个链表，第i个单链表中的节点表示依附于顶点v_i的所有边。

我们给出邻接表的定义。

struct ListNode{
    int vertexNumber;//储存节点的名字
    struct ListNode*next;//指向它连接的顶点表示边
    //OtherInfo info;  //和边相关的信息，权重啥的
};

struct Graph{
    int V;//顶点的数目，用于创建单链表计数
    int E;//边的数目，用于读入数据计数
    struct ListNode*Adj;//指向链表的头指针
};

基本上就是给定了一个图，包含顶点和边的数量以及依据这两个数据指向的一个邻接表，表的节点则储存顶点本身的信息以及指向它所连接的另一个顶点（也是一个节点结构）。邻接表中单链表的最后一个节点总是指向该顶点的邻接表本身。如果该顶点仅有头节点，也就是不与任何其他顶点连接，那么此时该节点的指针指向自己。

下面给出生成邻接表具体的代码实现。

struct Graph* adjListOfGraph(void) {
    int i, x, y;
    struct ListNode* temp;
    struct Graph* G = (struct Graph*)malloc(sizeof(struct Graph));

    if (!G) {
        printf("Memory Error.\n");
        exit(-1);
    }
    printf("Number of Vertices:\n");
    scanf("%d", &G->V);
    while (getchar() != '\n');
    printf("Number of Edges:\n");
    scanf("%d", &G->E);
    while (getchar() != '\n');
    G->Adj = malloc(sizeof(struct ListNode) * G->V);

    for (i = 0; i < G->V; ++i) {
        //初始化邻接表
        //G->Adj[i]= (struct ListNode*)malloc(sizeof (struct ListNode));
        G->Adj[i].vertexNumber = i;
        G->Adj[i].next = &(G->Adj[i]);
        printf("第%d个顶点的名称为：\n",i+1);
        scanf("%s",G->Adj[i].name);
    }
    for (i = 0; i < G->E; ++i) {
        int weight;
        printf("Reading Edges:\n");
        scanf("%d %d", &x, &y);
        while (getchar() != '\n');
        printf("Reading Weight:\n");
        scanf("%d", &weight);
        while (getchar() != '\n');

        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->vertexNumber = y;
        temp->next = (G->Adj[x].next);//临时节点指向第x条单链表，也就是第x个顶点，且采用头插法
        temp->dis = weight;//写入权重
        G->Adj[x].next = temp;//指向临时节点

        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->vertexNumber = x;
        temp->next = (G->Adj[y].next);
        temp->dis = weight;
        G->Adj[y].next = temp;
        //最后的效果就是x单链表指向y，y单链表指向x
        //也就是说，这是个无向图，如果有向，把第二部分去掉就好
        //本题要求有向，故删去第二部分
    }

    return G;
}

最后实现的效果如图所示。

虽然储存空间相对邻接矩阵已经小了很多，计算图的度也十分方便，即便如此邻接表也是有缺陷的。比如我们要实现删除一个节点的功能，虽然直接删除掉该节点对应的单链表很简单，但是还需要修改其他顶点的链表删除和指定节点的连接。这种操作带来的麻烦与风险性不言而喻。

十字链表

回忆邻接矩阵与邻接表的存储结构，它们都不便于求顶点的出度与入度（对于每个顶点而言，欲求其出入度，邻接矩阵需要扫描2*n次，而邻接表只易在求解其出度，欲求入度还需重新扫面整张图）。为了解决上述两者求出入度的局限性，在此引入十字链表，它可以看成邻接表与逆邻接表的结合，方便求解顶点出入度与获取顶点的出入度边。

十字链表和邻接表还是有点区别的，实际上是邻接表和逆邻接表的结合。

十字链表的存储结构包含表头结点表与弧表，与邻接表类似，是一种顺序结合链式的存储结构，因此需要有两个指针域分别指向以顶点为弧尾和以顶点为弧头的弧结点。

表头结点表是一个顺序存储结构的数组，其结点数据类型如下图所示：

它的顶点节点拥有一个data域储存和顶点相关的信息以及两条链域，分别指向以该顶点为弧头或弧尾的第一个弧节点。

弧结点的数据类型如下图所示：

弧尾结点存储该弧尾结点所在图中的位置，弧头结点同理；弧上信息指示权值等弧数据；hlink指向与该弧有相同弧头的弧结点，tlink指向与该弧有相同弧尾的弧结点

结合这些给出十字链表的示意图：

更多资料可以参考：图的存储结构-十字链表_老攀呀的博客-CSDN博客。

邻接多重表

邻接多重表是无向图的一种存储结构。如果在无向图中我们的侧重点在顶点上，那么使用邻接表是很合适的，然而之前我们讨论过，当我们的侧重点在边上，也就是需要对边增删查改的时候，用邻接多重表就更加合适了。

与十字链表一样，邻接多重表是由顶点集合和边集合构成的。但又与十字链表不同的是，邻接多重表是无向图的存储结构，而十字链表是针对有向图的。因为不考虑边的方向，所以和十字链表相比较，顶点结点只需要一个指针域指向所连接的边结点即可。

顶点集VexNode由顶点的数据域data和指向顶点所连接的边节点的指针firstEdge构成。

而在边集中对于一条边来说，iVex和jVex是这一条边的连接的两个节点（Vi，Vj）在顶点集中的下标，headEdge和tailEdge分别是指向有着相同头、尾节点的边节点的指针。

更多资料可以参考：【数据结构】邻接多重表_数据结构邻接多重表-CSDN博客。

图的遍历

从图中任意一个顶点出发访问图的其他所有顶点且仅访问一次，这种行为就是图的遍历。

图的遍历通常有两种算法：

1. 深度优先搜索
2. 广度优先搜索

这两种算法都相当经典，值得深入学习。

深度优先搜索/Depth First Search, DFS

深度优先搜索（Depth-First Search，DFS）是十分常见的图搜索方法之一。深度优先搜索会沿着一条路径一直搜索下去。首先选取一个顶点作为起点，然后尝试访问连接的其他顶点。如果该节点没有被访问，就选取该节点继续重复上述过程，也就是成为一个新起点。如果该节点已经被访问过，就回退到之前的顶点。如果遇到“死胡同”，也就是在无法搜索时，那么就回退到刚刚访问过的节点，这个过程叫做回溯。当回溯到开始的顶点时，该过程终止。深度优先遍历按照深度优先搜索的方式对图进行遍历。并且每个节点只能访问一次。

深搜优先搜索的本质上就是持续搜索，遍历了所有可能的情况，必然能得到解。DFS搜索的流程是一个树的形式，每次一条路走到黑。

一般采用栈结构来辅助DFS的实现，但因为递归时利用的也是栈，所以一般用递归来实现DFS算法。将DFS用于二叉树，等价于使用前中后序遍历。

基于此机制的算法实现如下：假设Visited是一个全局数组，用于记录顶点是否已经被访问过。

//注：此处算法代码实现存疑，仅供参考
int Visited[G->V];

void DFS(struct Graph*G,int u){
    /*如果用邻接矩阵的方法来表示图，那么该节点没有被访问过的条件是：
     if(!Visited[v]&&G->Adj[u][v])*/
    Visited[u];

    for (int v = 0; v < G->V; ++v) {
        对u的每个尚未被访问过的邻接节点v//也就是判断条件，这里未给出
        {
            DFS(G,v);
        }
    }
}

void DFSTraversal(struct Graph*G){
    for (int i = 0; i < G->V; ++i) {
        Visited[i]=0;//把所有数组全部置零

        //如果图有不止一个连通分量，那么这个循环就是需要的
        for (int i = 0; i < G->V; ++i) {
            if(!Visited[i])
                DFS(G,i);
        }
    }
}

其中第二个算法用于处理非连通图的情况。

需要强调的是，DFS算法并非是一种具体的算法，而是一种算法的思想，即通过设置一个判定条件以“不撞南墙不回头”的方式对图或者树进行搜索的方式。

广度优先搜索算法/Breadth First Search, BFS

也就是层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

一般用队列来实现BFS。将BFS用于二叉树，等价于使用层次遍历。或者说，层次遍历本就是借鉴了BFS算法。

我们令开始的顶点层数为0，BFS算法先访问最开始的顶点，然后访问第一层的所有顶点，即与开始的顶点距离为1的顶点。随后，再访问第二层的所有顶点。以此类推，直到所有的顶点都被访问。通常使用队列来储存每一层的顶点。

和DFS一样，我们使用一个全局数组来保存所有的顶点并预设为未访问，每个顶点被访问后就设为访问过。

具体的代码实现如下所示。

void BFS(struct Graph*G,int u){
    int v;
    struct Queue*Q = CreateQueue();
    EnQueue(Q,u);
    
    while(!IsEmptyQueue(Q)){
        u=DeQueue(Q);
        Process u;//操作，例如打印等
        Visited[s]=1;
        /*如果用邻接矩阵的方法来表示图，那么该节点没有被访问过的条件是：
     if(!Visited[v]&&G->Adj[u][v])*/
        对u的每个尚未被访问过的邻接节点v//也就是判断条件，这里未给出
        {
            EnQueue(Q,v);
        }
    }
}

void BFSTraversal(struct Graph *G){
    for (int i=0;i<G->V;i++)
        Visited[i]=0;
    //如果图有不止一个连通分量，那么这个循环就是需要的
    for (int i = 0; i < G->V; ++i) {
        if(!Visited[i])
            BFS(G,i);
    }
}

和DFS一样，BFS也是一种算法思想，并没有特定的模板。树的层次遍历就是BFS算法思想最好的具现化。

图的算法问题集

连通性问题

连通性问题，也就是找出一个图的生成树/极小连通子图。大致思想就是通过DFS或者BFS来遍历子图，然后再从一个未被访问的顶点继续遍历下一个连通分量，与图的遍历做法几乎相同。

通过图的遍历可以得到图的一棵或者多棵生成树。由深度优先搜索生成的树称为深度优先搜索树，广度优先搜索生成的树称为广度优先搜索树。

因为一个连通图对应的生成树不唯一，我们把生成树中所有边的权值之和称为代价，代价最小的生成树称为最小生成树。

比如我们要在n个城市间修建n-1条路线，如何在最节省经费的条件下建立这个通道？这个问题等价于在e条带权边选取n-1条边（不构成回路）来使权值最小。

那么如何构造最小生成树呢？我们引入两种算法。

普里姆/Prim算法

我这本参考书上实现Prim算法使用了优先队列，但是我还没有学习相关的数据结构，所以暂时用其他博客文章来代替理解。

可以参考这篇文章：最小生成树——Prim算法（详细图解）_prim最小生成树_skynesser的博客-CSDN博客。

有一种实现方法是分别储存所有顶点node、是否被访问selected、权值minDist、父母顶点parent。

首先将所有顶点的selected栏设为False，所有顶点的minDist为inf，parent为-1。然后初始化第一个顶点selected状态为True，minDist为空，parent仍为-1。

接下来开始进行遍历操作，分为三步：更新Update、扫描Scan、添加Add。每次访问（这里还没有更新状态）与已有顶点相连接的其他顶点时，都更新顶点的权值以及父母顶点。随后扫描到最小的权值，将该两个顶点连接并将更新selected状态。重复上述步骤直到所有的顶点都被访问，此时selected都为True且minDist均为 - ，最小生成树储存在parent中（对应点和点之间的连接关系）。

克鲁斯卡尔/Kruskal算法

该算法的思想比较简单。首先将连通图的所有边按照权重从小到大排序放入一个列表中，然后依次向图中加入边。每次添加一条边都要进行一次判断：添加边后该图是否形成环？若没有，则边成功添加入图，边数加一；若形成环，则丢弃这条边，边数不变。当边数达到n-1时（假设该图一共有n个顶点），说明找到了最小生成树，算法结束。

这里也借鉴其他人的博客Kruskal算法简易教程（附最全注释代码实现）-CSDN博客。就不详细写出算法实现了（参考书中利用了不相交集和优先队列实现）。

该算法的关键问题是如何判断图形成了环。

最短路径问题

最短路径问题一般是给定一个图G=(V,E)和一个顶点s，需要求出顶点s到达其余每个顶点的最短路径。采用何种最短路径算法依赖于图的类型。我将最短路径算法和图的类型进行的简单的归纳。

图的类型	算法
无权图的最短路径	“朴素算法”
有权图的最短路径	迪杰斯特拉算法/Dijkstra算法
具有负权重边的最短路径	贝尔曼福特算法/Bellman-Ford算法

下面我们依次来介绍这些情况。

“朴素算法”

这个算法是我自己命名的。无权图的最短路径其实可以视为权重均为1的有权图，是一种有权图的特殊情况。由于实际情况中应用较少，且完全可以用处理有权图的迪杰斯特拉算法兼容，我们这里先暂时跳过介绍该算法。（兴许以后有时间会补上）

迪杰斯特拉/Dijkstra算法

迪杰斯塔拉算法是一个经典而伟大的算法，经过一个星期的咀嚼我觉得已经悟的差不多了。传统的BFS算法无法解决最短路径问题，因为它无法保证队列前面的顶点是最接近源点s的顶点。因此，应用这个算法我们还需要两种辅助的数据结构。

• 具有三列（每行对应一个顶点）的一个距离表
  • 顶点的序号/名称
  • 距离源顶点的距离Distance[v]。源点到自身的距离为0，其余顶点在距离表中的距离被初始化为-1。
  • 路径Path[v]——包含抵达该顶点的前驱顶点的名称，通过该顶点我们可以得到最短距离。
• 优先队列。使用优先队列来储存尚未被处理的顶点，并始终弹出距离源顶点最短距离的顶点先处理，符合贪心原则。这里我们采用的是基于二项堆实现的优先队列。

算法结束时，距离表中将储存所有顶点到达源顶点的最短距离。同时我们可以根据距离表中每个顶点对应的前驱顶点往前追溯直到回到源点为止，这个过程所经过的路径实际上就是源点到达该点的最短路径（由于我们是从终点向起点追溯，你也可以称为是选定顶点到源点的最短路径）。

关于迪杰斯特拉算法有以下三点需要特别注意：

• 它使用了贪婪法：总是选择下一个距离源点最近的顶点。
• 利用优先队列来实现贪婪，按照当前距离s的距离大小来储存还未确定最短路径的节点。
• 迪杰斯特拉算法不适用于处理带有负权重的有权图。

接下来我们给出迪杰斯特拉算法的伪代码实现（因为表示图的方法不同，所以只好用伪代码表示）。

void Dijkstra(struct Graph*G,int s){
    struct PriorityQueue*PQ=CreatPriorityQueue();
    int v,w;

    EnQueue(PQ,s);
    for (int i = 0; i < G->V; ++i) {
        Distance[i]=-1;
    }
    Distance[s]=0;

    while (!IsEmptyQueue(PQ)){
        v=DeleteMin(PQ);
        对于顶点v的所有邻接顶点w{
            计算新距离d=Distance[v]+weight[v][w];
            if(Distance[w]==-1){//说明该邻接顶点还未确定最短路径
                Distance[w]=new distance d;
                将具有优先级d的顶点w插入优先队列中
                Path[w]=v;
            }
            if(Distance[w]>new distance d){//说明经过该邻接顶点的路径比之前已经确定的最短路径更优
                Distance[w]=new distance d;
                将w的优先级更新为d;
                Path[w]=v
            }
        }
    }
}

更详细的解释

我对于迪杰斯特拉算法的理解，其实就是贪心+层次遍历/BFS。该算法利用BFS将顶点全部存入队列中遍历处理，但是由于贪心的需要所以采用优先队列保证每次先处理距离源点最近的顶点，计算其距离看是否会得到更小的距离。如果该顶点还未确认最短路径（Distance[w]==-1）就暂且默认该路径为最短路径，更新距离表；如果能使得路径更短（Distance[w]>new distance d），说明经过该邻接顶点的路径比之前已经确定的最短路径更优，就重置节点优先级（更新优先队列）并更新距离表。这样最后距离表就能得到源顶点到其他所有顶点的最短路径。

这里我按照邻接表的结构完善了伪代码，这里放出来仅供参考。

void Dijkstra(struct Graph* G, int s, struct DistanceMap* map) {//传入图和距离表
    struct Heap* h = CreatHeap(G->V, MIN_HEAP);//创建堆作为优先队列辅助
    struct ListNode* temp;//建立临时节点来储存邻接顶点
    int v, w, d;//分别表示当前顶点，当前顶点的邻接顶点，两者的距离

    for (int i = 0; i < G->V; ++i) {//初始化距离表
        map[i].vertexNumber = i;
        map[i].Distance = -1;
    }
    map[s].Distance = 0;//设置源顶点距离为0
    map[s].Path = s;//默认源顶点的路径为其本身
    Insert(h, s, map);//将源顶点插入优先队列中

    while (!IsEmptyHeap(h)) {
        v = DeleteElement(h, map);//弹出最小距离的顶点，开始贪心
        temp = &G->Adj[v];
        while (temp->next->vertexNumber != v) {
            temp = temp->next;//temp储存邻接顶点
            w = temp->vertexNumber;//w表示邻接顶点的顶点序号
            d = map[v].Distance + temp->dis;//邻接顶点到源点的距离计算为v顶点到源点的距离加上邻接顶点w到v顶点的距离
            if (map[w].Distance == -1) {//邻接顶点未确定最短路径的情况
                map[w].Distance = d;
                Insert(h, w, map);
                map[w].Path = v;
            }
            if (map[w].Distance > d) {//邻接顶点已经确认最短路径但是出现了更优路径都是情况
                map[w].Distance = d;
                PercolateDown(h, 0, map);//更新优先队列
                map[w].Path = v;
            }
        }
    }
    DestroyHeap(h);//销毁优先队列
}

不足之处

迪杰斯特拉算法主要有以下两个问题。

• 该算法本质上是基于贪心的盲目搜索，会浪费时间和必要的资源。
• 该算法不能处理负权重的边，这种情况下要采用贝尔曼-福特/Bellman-Ford算法。

贝尔曼-福特/Bellman-Ford算法

关于这一部分，我这本书上讲的不是一般的烂，给出的算法无法处理负权环，所以暂时就先跳过这一部分（再次给朋友们避雷这个叫纳拉辛哈·卡路曼希的印度人写的C语言数据结构书）。

这里放出WAHAHA佬对于Bellman-Ford算法的博客，可以先用这篇文章作为代餐：Bellman-Ford算法 | WAHAHA’s blog (gngtwhh.github.io)。

拓扑排序

拓扑排序是个很有趣的东西。比起一般的图结构和排序，它特殊在是用边来表示信息的。

给定一个有向无环图（DAG）。

我们假设这是大学的课程先决条件，其中的有向边(v,w)表示必须要先完成课程v才能学习课程w。在这种情况下，拓扑排序就是不违背先决条件的课程学习顺序。每个DAG可能有一个或者多个拓扑排序序列，比如对于上图A->B->D->C和A->C->B->D都是合理的拓扑排序。前提是该图不能存在回路，否则拓扑排序将不存在，因为此时v将先于w同时w也会先于v。

拓扑排序还有一个有趣的性质，如果排序中所有连续的顶点构成的顶点对之间都通过边来联系，那么这些边构成DAG中一个有向的哈密尔顿路径，此时拓扑排序唯一。（哈密尔顿路径后续随缘更新……）

那么我们如何实现拓扑排序的算法呢？以下是我的一些思路。首先对于所有顶点计算其入度，然后从入度为0的点开始处理。这意味着拓扑排序将从没有先决条件的顶点开始。为了跟踪这些顶点，我们用队列来储存这些顶点。

入度为0的顶点都存入队列中，当队列不为空时，队首顶点v出列，并且由v发出的边到达的所有邻接顶点入度全部减1.如果有顶点因此入度减小到了0（说明先决条件全部被满足），该顶点就被存入队列中。拓扑排序就是顶点的出队顺序。

以下给出拓扑排序的伪代码实现。

void TopologicalSort(struct Graph*G){
    struct Queue*Q;
    int counter;
    int v,m;
    Q=CreatQueue();
    counter=0;
    for (int v = 0; v < G->V; ++v) {
        if (indegree[v] == 0)
            EnQueue(Q, v);
    }
        while (!IsEmptyQueue(Q)){
            v=DeQueue(Q);
            topologicalOrder[v]=++counter;//出队顺序序号
            对于邻接v的每个w{
                if(--indegree[w]==0)
                    EnQueue(Q,w);
            };
        }
    if(counter!=G->V)
        printf("Graph has circle!\n");
    DeleteQueue(Q);
}

---

（待更新……）