清华版《数据结构》拓扑排序有一处不解

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3344 天前的主题，其中的信息可能已经有所发展或是发生改变。

https://imgur.com/noGfBr1

「在头结点中增加一个存放顶点入度的数组 indegree 」何意？
从 7.12 的算法来看，我认为就是另设了个数组来存储入度，类似于另设一栈来存储入度为零的顶点。

所以黄色高亮的头结点何意，感觉在算法中没有体现啊？

请各位解惑，感谢。

头结点

顶点

算法

入度

6 条回复 • 2015-09-27 22:37:44 +08:00

fetich

2015-09-27 18:21:41 +08:00

需要提及的是，书上并没有 FindIndegree 这个函数的定义，起码我没有找到。。。

fetich

2015-09-27 18:28:41 +08:00

第一次用 imgur.com ，各位能看到图片么？

fetich

2015-09-27 18:30:25 +08:00

在添加一条截图链接： http://rghost.net/6yfXCVbzh/image.png

GordianZ

MOD

2015-09-27 20:45:42 +08:00

贴图需要图片 URL

xjx0524

2015-09-27 20:57:50 +08:00

看代码 indegree 就是用来储存入度的，并不理解头结点什么含义，也许是要在代码头部先声明个数组？如果这书是翻译的可以看看原文，如果不是就算了。。。。

他这代码算是伪代码了， FindIndegree 就是计算入度用，至于怎么实现因为比较简单就没有往上写了。

fetich

2015-09-27 22:37:44 +08:00

@xjx0524
因为这里图是用邻接表存储，所以所有的表头结点（表示图的顶点）通常会按顺序结构存储，表头结点有两个域，结点信息和指向其单链表的第一个结点的指针。书的意思可能是在表头结点增加第三个域，但从后面对 indegree[]的使用来看不是这么一回事，我也很纠结。
如果 FindInDegree 有具体实现的，或许能知道怎么回事。。。