图论在单词接龙中的应用

2005年9月

第19卷第3期总61期北京联合大学学报(自然科学版)

Journal of Beijing Union University (Natural Sciences ) Sep . 2005

Vol . 19No . 3Sum No . 61

图论在单词接龙中的应用

孙君意

(华中师范大学信息技术系, 武汉　430079)

[摘　要]　讨论了“单词接龙”的求解问题。运用图论中的欧拉定理建立了数学模型, 并且设计

了比较优化的算法, 编制了程序。对任意一组单词, 该程序可以判断出它们能否完成接龙。经测试, 该算法较之传统的穷举法明显地降低了复杂度。

[关键词]　图论; 欧拉路; 单词接龙; 图算法[中图分类号]　O 157. 5　　[文献标识码]　A 　　[文章编号]　1005-0310(2005) 03-0030-04　　有这样一个古老的数学问题。假设有许多张卡片, 每张卡片上都写着一个英文单词, 现在要把这些卡片按照一定的顺序连成串。这个顺序要求每张卡片(第一张卡片可以除外) 上的单词的首字母恰好是前一张卡片上的单词的尾字母, 并且要求每张卡片只能用一次, 简单地说就是“单词接[1]

龙”。有一些单词组通过适当的组合是可以完成接龙的, 例如, “teach ”,“teeth ”, “yet ”,“happy ”。但是某些单词组却不具备这样的性质, 比如“ok ”, “old ”, “deep ”, “king ”。问题的关键是能否找出一种科学的方法快速、准确地判断一组单词是否可以按照上述规则完成接龙呢? 笔者运用图论中的欧拉定理建立了数学模型, 并且设计了比较优化的算法, 编制了程序来求解该问题。对任意一组单词, 该程序可以判断出它们能否完成接龙。

图。

2) 定理1　无向连通图G 是欧拉图 G 不含奇数度的结点(即G 的所有结点的度均为偶数) 。

3) 定理2　一个连通(弱连通) 有向图具有欧拉回路的充要条件是G 的每一个结点的入度和出度相等。具有欧拉路的充要条件是除两个结点外, 每个结点的入度等于出度。对于这两个结点, 一个结点的出度比入度多1, 另一个结点的出度比入度少1。

运用这些定理, 可以判断如图1所示的4个图形中, 右边的2个图形是可以一笔画出的, 因为这2个图形分别存在着欧拉回路和欧拉路, 而左边的2个图形则不行, 因为它们不满足上述任何一条定理的条件。

[2]

1　相关图论知识

图论是离散数学的一个分支, 它以图为研究对象, 研究节点和边组成的图形的数学理论和方法。

关于欧拉回路和欧拉路, 简单地说欧拉回路要求边不能重复, 结点可以重复。笔不离开纸, 不重复地走完所有的边, 回到原处, 就是所谓的一笔画。欧拉路与欧拉回路不同之处是它不要求回到原处。这些名字中的“欧拉”是因为欧拉解决了七桥问题, 并发现了一笔画所需的性质。

下面列出一些定义和定理:1) 定义　通过图G 的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图, 称为欧拉

[收稿日期]　2005-04-06

[作者简介]　孙君意(1984—), 男, 湖北十堰人, 华中师范大学电子信息工程专业、华中科技大学计算机科学专业(双学

位) 在读学生, 软件设计师, 研究方向为数据通信与移动开发。

　　　

图1　这4个图形可否一笔划出

第19卷第3期孙君意:图论在单词接龙中的应用

31

2　数学模型的建立

对于单词接龙的求解, 最易想出的方法莫过于穷举法, 在这些单词的全排列中若能找出一组满足接龙条件的组合即有解。然而, 如果用穷举法, N

个单词全排列共有N ! 种情况, 算法复杂度O (N ! ) , 显然穷举法是行不通的。笔者的思路是建立这样一个数学模型, 假设不区分字母的大小写, 可以把所有的英文字母看成是26个节点, 把每一个单词看作是一条有向边, 即弧。这样, 弧头就是单词的首字母, 弧尾就是单词的尾字母, 且弧头、弧尾必然都在A ～Z 这26个点当中。一组单词就可以构成一个节点数有限的有向图, 模型建立起来了, 而判断单词能否完成接龙的问题也就转化成了一个图论问题, 即判断一个有向图中是否存在欧拉回路或者欧拉路。而且由于图的点数最多为26个, 若经过合理地设计, 算法的复杂度可降到常数级。

可以对定理做一个简单地应用。“teeth ”, “teach ”,“happy ”, “yet ”这4个单词可以完成接龙, 即teeth —happy —yet —teach , 它们构成的有向图如图2所示。“old ”, “ok ”, “king ”, “deep ”这4个单词无法完成接龙, 它们构成的有向图如图3所示。这是观察的结果, 可以再从图论的角度证明之。若能一笔把这些单词连起来, 则所有单词构成的有向图中最少存在着一条欧拉路。当然, 也可能是欧拉回路。图2是连通的有向图, 它没有欧拉回路, 但存在欧拉路。图2中T 点的入度为2, 出度为1, 出入度相差为1; H 点的出度为2, 入度为1, 出入度相差为1; Y 点的入度为1, 出度为1, 出入度相等。因此, 图2是满足定理2的“除两个结点外, 每个结点的入度等于出度。对于这两个结点, 一个结点的出度比入度多1, 另一个结点的出度比入度少1”这个充要条件的, 故存在欧拉路, 可以完成接龙。再看图3, 其中没有回路, 且O 点的入度为2, 出度为0, 出入度之差为2, 因此不可能有欧拉路, 故不能完成接龙

。

图3　无欧拉路的有向图　　　

3　总体算法设计

对于较少的单词可以通过人工画图, 然后进行观察和计算, 从而得出结论。但是如果有上千单

词, 人的大脑必然难以承受其复杂度。因此, 必须借助计算机。我们可以把解题的数学思想设计成算法, 按照算法编出程序, 并把待测试的单词组放在输入文件, 程序运行后读入文件中的数据, 并执行已经设计好的算法, 然后输出结果到输出文件, 通过分析输出文件就可以得出结论。因此, 设计一个好的算法是至关重要的, 不仅要完全反映出定理, 而且要综合考虑时间复杂度和空间复杂度的问题。首先要做的就是如何把定理转化为算法。因为笔者建立的是有向图模型, 而定理2又是针对有向图的, 所以把定理2转化为对应的算法, 于是得到了如图4所示的算法流程图。有了流程图, 仍然有许多细节问题要解决。这些问题如下:如何把单词组构建成有向图? 如何判断该图是弱连通的? 如何判断该图存在欧拉回路? 如何判断该图存在欧拉路? 这些问题都需要用具体的程序模块来实现。在第4部分, 将给出每个功能模块的具体代

图2　

存在欧拉路的有向图

图4　总体算法流程图

32码。

北京联合大学学报(自然科学版) 2005年9月

　　for (j =0; j

　　　　if (visited [j ]==0&&edge [i ][j ]==1) 　　　　　　dfs (j ) ;

　　　　if (visited [j ]==0&&edge [j ][i ]==1) 　　　　　　dfs (j ) ; 　　　　}　　　　}

　　　　 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

int iscon () {　 ＊此函数返回1表示该图是弱

visited 是个一维数组, 当visited [i ]=1时表示i

连通的, 返回0则说明不是＊

　　int i , j , ct =0; 　 ＊ct 用来表示有向图中连通子图的个数＊ 　　for (i =0; i

　　　　if (edge [i ][j ]==1&&visited [i ]==0) {　　　　　　dfs (i ) ; 　 ＊从i 点开始深度搜索直到无路可走为止＊

　　　　　　ct ++;　 ＊弱连通子图数目加1＊ 　　　　}

　　　　}　　　　if (c t ==1) return 1; 　 ＊仅有一个弱连通子图说明此有向图是弱连通的＊ 　　return 0; ＊返回零说明此图不连通＊

}

4. 4　判断单词组能否完成接龙的程序模块

void solve () {

　　 ＊head =1时表示入度比出度多1的特殊点找到了, tail =1时表示出度比入度多1的特殊点找到了, err =1时表示不存在欧拉回路和欧拉路。err 的默认值为0。如果仅存在两个特殊点, 且这两点分别满足入度比出度多1和出度比入度多1, 则err 保持0不变, 这说明存在欧拉路。如果在检查的过程中每个点都是出入度相等, 则err 保持0不变, 说明存在欧拉回路。＊

　　int err =0, head =0, tail =0, i ;

　　if (iscon () ) {　 ＊如果有向图是弱连通的＊ 　　for (i =0; i

　　　　if (in [i ]+out [i ]! =0) {　 ＊如果该点的度不为零＊ 　　　　　　if (in [i ]-out [i ]==1&&! head ) 4　具体模块的算法描述

完成算法的总体设计之后, 还要实现算法的每一个功能模块。下面给出几个主要模块的C 代码算法描述。

4. 1　几个重要全局变量的说明

int edge [26][26], visited [26], in [26], out [26]; edge 是个二维数组, 当edge [i ][j ]=1时表示有从j 到i 的一条弧, 当edge [i ][j ]=0时则表示没有。

点已经被访问到了。当visited [i ]=0时表示i 点

没有被访问到。

in 是一个一维数组, in [i ]=x 表示i 点的入度为x 。

out 是一个一维数组, out [i ]=x 表示i 点的出度为x 。

4. 2　把单词组构造成有向图的程序模块

memset (edge , 0, size of (edge ) ) ; for (i =0; i

　　} ＊以上为变量初始化＊

　　fscanf (fptr , “%d ”, &wordsnum ) ;　 ＊输入测试单词的个数＊

　　while (wordsnum --) { ＊循环直到输入完所有单词＊

　　　　fscanf (fptr , “%s ”, word ) ; 　 ＊输入单词＊

　　　　in [word [0]-`a ' ]++;　 ＊首字母的入度加1＊ 　　　　out [＊(strchr (word , ` 0' ) -1) -`a ' ]++;　 ＊尾字母的出度加1＊

　　　　edge [word [0]-`a ' ][＊(strchr (word ,` 0' ) -1) -`a ' ]=1; 　 ＊标识从尾字母到首字母有1条弧＊ 　　}

4. 3　判断该图是否为弱连通的程序模块

void dfs (int i ) {　 ＊此函数用于从i 点开始进行深度搜索＊ 　　int j ;

第19卷第3期孙君意:图论在单词接龙中的应用

33

＊

　　　　　　else if (in [i ]-out [i ]==-1&&! tail ) tail =1; ＊找到了出度比入度多1的特殊点＊

　　　　　　else if (in [i ]-out [i ]==0) continue ; ＊出度等于入度则继续检查下1点＊ 　　　　　　else err =1; 　 ＊除两个特殊点外还存在入度与出度不相等的点, 这说明既不存在欧拉回路也不存在欧拉路＊ 　　　　　　}　　　　}

　　}　　else 　 ＊有向图不是弱连通的则单词组不能接龙＊

　　　　err =1;

　　if (! err ) fprintf (outptr , “Ordering is possible . n ”); ＊err ==0说明接龙可以完成＊

　　else fprintf (outptr , “Ordering is not possible . n ”); ＊err ==1说明接龙不能完成＊

}

5　结束语

图论的正确应用大大降低了单词接龙求解的复杂度。为了检测程序的正确性, 笔者设计了1000多组长短不同的数据对程序进行了黑箱测试。结果显示, 大多数情况程序都能在0. 5s 以内得出正确结果, 然而对于一些特殊的数据, 耗费时间略长。这说明在算法上仍然可以进一步地优化。

[参考文献]

[1]　Poucher W . International AC M programming contest [EB OL ]. http : acm . uva . es p v101 10129. ht ml . 2005-05-29. [2]　洪帆. 离散数学基础[M ]. 第2版. 武汉:华中理工大学出版社, 2002.

The Application of Graph Theory in a Fan -tan Game

SUN Jun -yi

(Department of Information Technology of Huazhong Normal Universit y , Wuhan 　430079, China )

A bstract :The math proble m in a fan -tan game is discussed . B y using graph theor y to build a mathematical model and designing an effective algorithm to solve the problem , the program is done . This algorithm -based pr ogram can judge whether a group of words can be strung together . Following tests the method is found much less complex than the traditional method of exhaustion .

Key words :graph theor y ; Euler circuit ; fan -tan game ; graph algorithm

(责任编辑　李亚青)