拓扑排序
这是我们老师留的题目,我已经做出来了,但算法不很好,题目如下
用C写一个程序,该程序从一个文本文件中读入一组字符,该文件的内容格式如下:
ab
ac
bd
be
cd
ce
df
eg
fh
gi
这种排列方式产生了一个拓扑图形,如下:
b d f h
a
c e g i
a的后面是b, b的后面是d和e, c的后面是d和e................
以此类推。
要求1: 将这个图形重新排列,并按照类似下面的顺序重新输出到屏幕上:
abcdefghi
要求2: 找出所有符合要求1的排列顺序,类似这样的排列acbedgfih也是符合要求的,找出所有的,并输出到屏幕
////////////////////
我的做法是:把每一个字符都给一个等级,a是1级,b,c是2级,d,e是3级,f,g是4级,i,h是5级,然后按级别输出。第二步,把所有的字符所有的排列可能性都找出来,然后再按等级输出,这样就找出所有符合规定的排列。这种算法在寻找所有可能的排列顺序时候很费时间,如果一个图很大的话,时间会很久。
就这个,我题目已经交了,绝对不是为了骗答案,纯粹娱乐,各位朋友各抒己见吧
[讨论]给大家出道题提提神
-
- 帖子: 30
- 注册时间: 2006-06-05 23:27
-
- 帖子: 50
- 注册时间: 2006-03-17 20:06
这是图论当中一个经典的问题。
首先,根据输入构造一个图,输入的每一行都是图中的一条有向边,输入的字母,就是节点。
比方说输入ab,那么对应的边就是 a -->b
此外,对于图的每一个节点,都定义一个出度与入度的概念。
所谓出度,就是由该节点发出去的有向边的条数, 所谓入度,则是指图中指向该节点的边的条数。
例如,对于题目中的例子,a的出度为2,入度为0;b的出度为2,入度为1;一次类推吧
产生所有序列的过程是一个使用深度优先的方法不断的在图中删除节点的过程。
每一次,可以从图中删除入度为0的节点,当有多于1个如度为0的节点的时候,就有了多个分之,
可以采用深度优先的方法,检查每一个分支。删除节点的同时,需要删除所有与该结点相关的边。
比方说删除节点a以后,边a-->b,a-->c被删除,这时候,bc的入度也就成了0,下一步就有了两个
可以被删出的节点:b和c
使用这样的方法,当图中所有的节点都被删除了,也就获得了满足条件的序列了。
不知道搂主看懂了没有,如果有点糊涂的话,可以去看看图论书,里头有好多类似的有意思的东西。
首先,根据输入构造一个图,输入的每一行都是图中的一条有向边,输入的字母,就是节点。
比方说输入ab,那么对应的边就是 a -->b
此外,对于图的每一个节点,都定义一个出度与入度的概念。
所谓出度,就是由该节点发出去的有向边的条数, 所谓入度,则是指图中指向该节点的边的条数。
例如,对于题目中的例子,a的出度为2,入度为0;b的出度为2,入度为1;一次类推吧
产生所有序列的过程是一个使用深度优先的方法不断的在图中删除节点的过程。
每一次,可以从图中删除入度为0的节点,当有多于1个如度为0的节点的时候,就有了多个分之,
可以采用深度优先的方法,检查每一个分支。删除节点的同时,需要删除所有与该结点相关的边。
比方说删除节点a以后,边a-->b,a-->c被删除,这时候,bc的入度也就成了0,下一步就有了两个
可以被删出的节点:b和c
使用这样的方法,当图中所有的节点都被删除了,也就获得了满足条件的序列了。
不知道搂主看懂了没有,如果有点糊涂的话,可以去看看图论书,里头有好多类似的有意思的东西。
-
- 帖子: 30
- 注册时间: 2006-06-05 23:27
-
- 帖子: 30
- 注册时间: 2006-06-05 23:27
-
- 帖子: 50
- 注册时间: 2006-03-17 20:06
-
- 帖子: 30
- 注册时间: 2006-06-05 23:27
-
- 帖子: 50
- 注册时间: 2006-03-17 20:06
skycn 写了:可是如果用诸如while类的循环的话,篇幅会太长,特别容易自己把自己稿乱了,递归相对明了一些
另外,我有个问题不明白,一个递归函数,比如,function(int max)
它调用它自己的时候,我是这样:
max--;
function(max);
好呢,还是
function(max--);
比较好。
我今天发现这两种方式的结果是不一样的,为什么?
代码: 全选
max--;
function(max);
代码: 全选
function(--max);
代码: 全选
function(max--);[/code]则等价于[code]function(max);
max--;