纸上谈兵: 拓扑排序

《文明》是一款风靡20多年的回合制策略游戏,由Sid Meier开发。《文明》结构宏大,内容丰富,玩法多样,游戏性强,称得上是历史上最伟大的游戏。在文明中,你可以选择某个文明的,从部落开始发展,在接下来的几千年的历史中,发展科技、开荒拓野、发动战争等等。游戏在保持自由度的前提下,对各个社会文明的发展顺序有很好的仿真性,让玩家仿佛置身于历史长河,坐观文明的起落。美国的一些大学的历史系甚至于使用该游戏作为教学工具。

(作为《文明》的忠实爱好者,多少个昼夜耗费在一张张地图上啊。好吧,是为了学习历史。)

“科技树”

《文明》中的科技树

游戏有一个“科技树”系统,即你可以按照该图所示的顺序来发展科技。“科技树”是这样一个概念: 为了研发某个科技,我们必须已经掌握了该科技的所有前提科技(prerequisite)。科技树中有一些箭头,从A科技指向B科技,那么A就是B的前提科技。比如,根据上面的科技树,为了研发物理(Physics),我们必须已经掌握了化学(Chemistry)和天文学(Astronomy)。而为了研发化学(Chemistry),我们又必须掌握了火药(Gunpowder)。如果一个科技没有其它科技指向,那么就不需要任何前提科技就可以研发,比如图中的封建主义(Feudalism)。如果同一时间只能研发一项科技,那么玩家的科技研发就是一个序列,比如封建主义,工程(Engineering),发明(Invention),火药,一神教(monotheism),骑士制度(Chivalry)…… 有些序列是不合法的,比如工程,发明,火药……,在研发的“发明”时,并没有满足“封建主义”的前提条件。

一个有趣的问题是,如何找到合法的序列呢?当我们在设计计算机玩家时,很可能需要解决这样一个问题。

图(graph)中的拓扑排序算法(Topological Sort)可以给出一个合法序列。虽然在游戏中被称为“科技树”,但“科技树”并不符合数据结构中的树结构。在数据结构中,树的每个节点只能由一个父节点,整个树只有一个根节点。因此,“科技树”是一个不折不扣的图结构。此外,该树是一个有向的无环(acyclic)图。图中不存在环 (cycle, 环是一个长度大于0的路径,其两端为同一节点)。

拓扑排序

拓扑排序利用了一个事实,即在一个无环网络中,有一些节点是没有箭头指入的,比如科技树中的一神教、封建主义、工程。它们可以作为序列的起点。

  • 选择没有箭头指入的节点中的任一个,可以作为合法序列的起点,放入序列。
  • 当我们将某个节点放入序列后,去掉该节点以及从该节点指出的所有箭头。在新的图中,选择没有箭头指向的节点,作为序列中的下一个点。
  • 重复上面的过程,直到所有的节点都被放入序列。

对于每个节点,我们可以使用一个量入度(indegree),用来表示有多少个箭头指入该节点。当某个节点被删除时,图发生变化,我们需要更新图中节点的入度。

为了方便,我将“科技树”中的节点编号,为了符合C语言中的传统,编号从0开始。下面是对应关系:

0

1

2

3

4

5

6

7

8

9

一神教

神学

印刷术

民主

自由艺术

骑士制度

音乐理论

银行

经济学

封建主义

10

11

12

13

14

15

16

17

18

19

教育

天文学

航海术

物理

重力理论

发明

火药

化学

磁学

工程

20

21

冶金

军事传统

我们根据编号,绘制上述图(graph)。我同时用三种颜色,来表示不同点的入度(indegree):

我们使用邻接表的数据结构(参考纸上谈兵: 图),来实现图。构建代码如下:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 22

typedef struct node *position;

/* node */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int);
void print_graph(position graph, int nv);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    int i;

    // initialize the vertices
    for(i=0; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
    }

    // insert edges
    insert_edge(graph,0,1);
    insert_edge(graph,0,5);
    insert_edge(graph,1,2);
    insert_edge(graph,1,10);
    insert_edge(graph,2,3);
    insert_edge(graph,3,4);
    insert_edge(graph,7,8);
    insert_edge(graph,9,5);
    insert_edge(graph,9,15);
    insert_edge(graph,10,6);
    insert_edge(graph,10,7);
    insert_edge(graph,10,11);
    insert_edge(graph,11,12);
    insert_edge(graph,11,13);
    insert_edge(graph,13,14);
    insert_edge(graph,13,18);
    insert_edge(graph,15,16);
    insert_edge(graph,16,17);
    insert_edge(graph,17,13);
    insert_edge(graph,17,20);
    insert_edge(graph,19,15);
    insert_edge(graph,20,21);

    print_graph(graph,NUM_V);
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%d->%d; ", i, p->element);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * insert an edge
 */
void insert_edge(position graph,int from, int to)
{
    position np;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    np->next = nodeAddr;
}

我们可以根据上面建立的图,来获得各个节点的入度。使用一个数组indeg来储存各个节点的入度,即indeg[i] = indgree of ith node。下面的init_indeg()用于初始化各节点的入度:

// according to the graph, initialize the indegree at each vertice
void init_indeg(position graph, int nv, int indeg[]) {
    int i;
    position p;

    // initialize
    for(i=0; i<nv; i++) {
        indeg[i] = 0;
    }

    // assimilate the graph
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        while(p != NULL) {
            (indeg[p->element])++;
            p = p->next;
        }
    }   
}

正如我们之前叙述的,我们需要找到入度为0的节点,并将这些节点放入序列。find_next()就是用于寻找下一个入度为0的节点。找到对应节点后,返回该节点,并将该节点的入度更新为-1:

/* find the vertice with 0 indegree*/
int find_next(int indeg[], int nv) {
    int next;
    int i;
    for(i=0; i<nv; i++) {
        if(indeg[i] == 0) break;
    }
    indeg[i] = -1;

    return i;
}

当我们取出一个节点放入序列时,从该节点出发,指向的节点的入度会减1,我们用update_indeg()表示该操作:

// update indeg when ver is removed
void update_indeg(position graph, int nv, int indeg[], int ver) {
    position p;
    p = (graph + ver)->next;
    while(p != NULL) {
        (indeg[p->element])--;
        p = p->next;
    }
}

有了上面的准备,我们可以寻找序列。使用数组seq来记录序列中的节点。下面的get_seq()用于获得拓扑排序序列:

// return the sequence
void get_seq(position graph, int nv, int indeg[], int seq[]){
    int i;
    int ver;
    for(i = 0; i<nv; i++) {
        ver = find_next(indeg, nv);
        seq[i] = ver;
        update_indeg(graph, nv, indeg, ver);
    }
}

综合上面的叙述,我们可以使用下面代码,来实现拓扑排序:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 22

typedef struct node *position;

/* node */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int);
void print_graph(position, int);
void init_indeg(position, int , int *);
void update_indeg(position, int, int *, int);
void get_seq(position, int, int *, int *);
int find_next(int *, int);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    int indeg[NUM_V];
    int seq[NUM_V];
    int i;
    
    // initialize the graph
    for(i=0; i<NUM_V; i++) {
        (graph+i)->element = i; 
        (graph+i)->next    = NULL;
    }

    
    insert_edge(graph,0,1);
    insert_edge(graph,0,5);
    insert_edge(graph,1,2);
    insert_edge(graph,1,10);
    insert_edge(graph,2,3);
    insert_edge(graph,3,4);
    insert_edge(graph,7,8);
    insert_edge(graph,9,5);
    insert_edge(graph,9,15);
    insert_edge(graph,10,6);
    insert_edge(graph,10,7);
    insert_edge(graph,10,11);
    insert_edge(graph,11,12);
    insert_edge(graph,11,13);
    insert_edge(graph,13,14);
    insert_edge(graph,13,18);
    insert_edge(graph,15,16);
    insert_edge(graph,16,17);
    insert_edge(graph,17,13);
    insert_edge(graph,17,20);
    insert_edge(graph,19,15);
    insert_edge(graph,20,21);

    print_graph(graph,NUM_V);
    
    init_indeg(graph,NUM_V,indeg);
    get_seq(graph, NUM_V, indeg, seq);
    for (i=0; i<NUM_V; i++) {
        printf("%d,", seq[i]);
    }
}

void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
    printf("From %3d: ", i);
    while(p != NULL) {
        printf("%d->%d; ", i, p->element);
        p = p->next;
    }
    printf("\n");
    }
}
/*
 * insert an edge
 */
void insert_edge(position graph,int from, int to) 
{
    position np;
    position nodeAddr;
    
    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    np->next = nodeAddr;    
}

void init_indeg(position graph, int nv, int indeg[]) {
    int i;
    position p;

    // initialize
    for(i=0; i<nv; i++) {
        indeg[i] = 0;
    }

    // update
    for(i=0; i<nv; i++) {
        p = (graph + i)->next;
        while(p != NULL) {
            (indeg[p->element])++;
            p = p->next;
        }
    }  
}

// update indeg when ver is removed
void update_indeg(position graph, int nv, int indeg[], int ver) {
    position p;
    p = (graph + ver)->next;
    while(p != NULL) {
        (indeg[p->element])--;
        p = p->next;
    }
}

/* find the vertice with 0 indegree*/
int find_next(int indeg[], int nv) {
    int next;
    int i;
    for(i=0; i<nv; i++) {
        if(indeg[i] == 0) break;
    }
    indeg[i] = -1;

    return i;
}

// return the sequence
void get_seq(position graph, int nv, int indeg[], int seq[]){
    int i;
    int ver;
    for(i = 0; i<nv; i++) {
        ver = find_next(indeg, nv);
        seq[i] = ver;
        update_indeg(graph, nv, indeg, ver);
    }
}

上面算法中有一个遍历所有节点的for循环,而循环中的find_next()函数也会遍历所有的节点。因此,算法复杂度为[$O(|V|^2)$]。

在find_next()中,我们将放入序列的节点入度记为-1。find_next()每次会遍历所有的节点,没有必要遍历入度为-1的节点。为了改善算法复杂度,我们可以使用一个队列(或者栈)来记录入度为0的元素。我们每次从队列中取出一个元素放入拓扑序列,并更新相邻元素的入度。如果该元素的相邻元素的入度变为0,那么将它们放入队列中。可以证明,这样的改造后,算法复杂度为[$O(|V|+|E|)$]

问题拓展

通过上面的算法,我们可以获得一个合法的科技发展序列。我随后想到一个问题,如何输出所有的科技发展序列呢?

这个问题的关键在于,某个时刻,可能同时有多个节点的入度同时为0。它们中的任何一个都可以成为下一个元素。为此,我们需要记录所有的可能性。

(我想到的,是复制入度数组和序列数组,以储存不同的可能性。不知道大家有什么更好的想法呢?)

总结

图,拓扑排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

非主流自然语言处理:大规模语料词库自动生成

一、前言   写这篇文时,突然想到一个问题,大家的词库都是从哪来的?   之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博...

62012
来自专栏C语言及其他语言

[每日一题]问题 1454[蓝桥杯][历届试题]蚂蚁感冒

每日一题 题目描述 长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。 每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。 当两只蚂蚁碰...

36311
来自专栏程序员的知识天地

Python入门操作-时间序列分析

时间序列(或称动态数列)是指将同一统计指标的数值按其发生的时间先后顺序排列而成的数列。时间序列分析的主要目的是根据已有的历史数据对未来进行预测。本文我们会分享如...

2052
来自专栏ml

最小公倍数

最小公倍数 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致...

34610
来自专栏数据结构与算法

P1514 引水入城

题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代...

3006
来自专栏take time, save time

编程一样可以很带感--1+1不一定等于“2”

刚玩了两把flash小游戏,我也不知道为什么我从小就喜欢玩这个东西,想当初我上大学选软件的目的就是为了学会做flash,那时目的单纯吧?哈哈,初中的时候看的...

3676
来自专栏C/C++基础

P问题、NP问题、NPC问题(NP完全问题)、NPH问题和多项式时间复杂度

多项式关系形如O(nk)O(n^k),k为某个常数,n是问题的输入规模。例如,时间复杂度为O(nlog(n))、O(n^3)都是多项式时间复杂度。时间复杂度为O...

1801
来自专栏小红豆的数据分析

小蛇学python(2)两百行代码实现旅游中国34座大城市最短路径

直接说基础语法,也许大家不会感兴趣。前言之后的这一章,给大家介绍一下我最近写出来的一个小功能。用python语言实现GA算法来解决TSP问题,希望以此来激发大家...

2644
来自专栏一个会写诗的程序员的博客

函数式编程与面向对象编程[3]:Scala的OOP-FP混合式编程与抽象代数理论

Scala是纯种的面向对象的语言。从概念上讲,每一个值都是一个对象,每一个操作都是一个方法调用。语言支持通过类和特征的高级组件架构。

1212
来自专栏专知

关小刷刷题02——Leetcode 169. Majority Element 方法2和3

题目 169. Majority Element Given an array of size n, find the majority element. Th...

3407

扫码关注云+社区

领取腾讯云代金券