注册 登录
编程论坛 数据结构与算法

求解图操作中几个常见枚举值的意义。

yangfrancis 发布于 2017-04-08 10:57, 2843 次点击
最近看图结构的时候看到书上对顶点和边的状态用了以下枚举类型来表示。
顶点状态:
typedef enum{UNDISCOVERED, DISCOVERED, VISITED} VStatus;
边状态:
typedef enum{UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD} EStatus;

最要命的是书上没有说明这两组枚举类型的常数意义就直接上代码了,感觉好难看懂。网上查了一下这几个常数的确是经常定义点状态和边状态的,但自己人笨还没查到详细说明。想请高人解释一下它们的具体意义,应该什么时候把点或边定性为哪种状态。请不要单纯为我解释这些个英语单词的意思,这个我还是懂的。
谢谢了。
3 回复
#2
xzlxzlxzl2017-04-08 23:57
帮顶!
这通常是在图论里面吗?未深究,期待有大神解读。
#3
书生牛犊2017-04-09 23:20
这样翻译可能更好理解些

 顶点状态 {UNDISCOVERED未收录,DISCOVERED已收录,VISITED已遍历}
假设我们现在判断图上某两点AB是否存在通路。  初始化所有点为UNDISCOVERED,将要判断通路的其中一个顶点A设为起始点(标记状态为DISCOVERED),从所有标记为DISCOVERED的顶点中选一个遍历找到所有与之存在通路的状态还是UNDISCOVERED的,将这些顶点一律标记状态为DISCOVERED,同时修改刚刚这个我们遍历过的顶点A状态为VISITED。重复此项动作,直到B点被收入为DISCOVERED【可判定AB联通】或者所有的DISCOVERED都被修改为VISITED【判定AB不连通】。


  边状态 {UNDETERMINED未解决, TREE[FREE 吧]空闲, CROSS经过, FORWARD到哪里去, BACKWARD从哪里来}
  这通常出现于带权最短路的算法中。依赖UNDETERMINED、FREE、CROSS的状态标记可以先判断依靠现有的路径能否实现联通。【使用方法和上面顶点状态中的解释换汤不换药】。如果可以连通了,那么在递归判断最短路的时候我们就需要FORWARD和BACKWAED来记录路径具体走向。

再详细一点的解释我建议你可以先把这一章节跳过,看看那些经典的图的算法比如BFS、DFS、FLOYD、
只有本站会员才能查看附件,请 登录

跟着这些算法的思维走,等你看懂了、自己能写出一个这样的遍历程序反过头来理解这些 枚举值的意义就容易的多了。
#4
yangfrancis2017-04-11 14:43
多谢回复。之前手机结贴的,不便回复。现在补上。
我自己后来结合代码试着理解了一下,顶点和书生牛犊的解释应该是一致的。边好像是这样(仅为个人理解):在深度优先遍历中,所有边的初始状态是UNDETERMINED,当当前顶点遇到没有处理过的邻居,当前顶点和邻居间的边置为TREE (还真是TREE,可能是指它可以作为一个新起点发起搜索树吧), 如果遇到一个被发现时间比当前顶点还早的VISITED邻居,置为FORWARD (没看出这种关系和forward这个单词有什么联系),如果遇到一个被发现时间不比当前顶点处理得早的VISITED邻居,置为CROSS, 如果遇到的邻居已被发现但其邻居检索尚未完成(即DISCOVERED邻居),将边置为BACKWARD.

感觉比广度遍历复杂得多,也没看出规定这几个常数区别存在什么样的意义。本想放一放,先学习下一块;下一块是拓扑排序,更像天书……
1