一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 553|回复: 5
收起左侧

[编程题] CC150里的Graph到底什么意思。。。

[复制链接] |试试Instant~ |关注本帖
ml0353662 发表于 2015-4-11 15:47:16 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
百思不得其解。。。  CC150做到Graph的部分,书里直接就用了Graph这个类,但我找遍整个Java API,都没有。
将来估计也找不到, 所以不知道这些Graph的题是要怎么做呢?难道是自己编一个Graph的类来做?
而且书里用的Node有什么.state之类的, 这个好像也是没有的啊。。。。。
求大神指点
干.什么 发表于 2015-4-13 01:03:43 | 显示全部楼层
也和楼主一样纠结过,CC150 中关于 Graph 的题目远不如其他数据结构,但是做了点功课之后,我觉得作者这样的决定是权衡过利弊的。

1. Java 为什么没有提供 Graph?
在 Collections 中并没有直接提供 Graph 这种数据结构,原因是 Graph 的种类是实在是太多了,从实际开发和维护的角度来考虑,如果提供了有向的就势必要提供无向的,提供了有权重的就势必要提供没有权重的,种种不同类型的数据结构正交之后会变成一个巨大的 library,维护会变得非常困难。

2. CC150 对 Graph 的处理
CC150 对 Graph 的讲解只完成了 a). 用 Adjacent List 来表示 edges (a.k.a. neighbors) b). 基本 BFS 和 DFS 的代码框架 c). 4.2 一个问题(基于第五版)
我的理解是这说明针对 Graph 的面试题目不会太深,很少有人被问到最小生成树或者其他相对高级的 Graph Algorithm, 所以过多的讨论 Graph 问题不会有特别大的价值。

还想对 Graph 中的 State 多说两句,State 使用枚举实现的,如果放狗找一下的话,会发现大多数的实现都是使用 Set<GraphNode> visited 或者 boolean[] visited 来实现的。我觉得这个地方没有特别强调挺可惜的,因为 Enum 类型在 Java 中是线程安全的,HashSet 不是,这一点在分布式系统中是非常重要的(同样的思路在 singleton 模式中也有体现。)

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

stellari 发表于 2015-4-12 23:30:34 | 显示全部楼层
是的,基本意思就是说:这里用了自定义的Graph和Node类,至于这两类的界面的API到底是什么样子,作者认为她写的代码足够清楚,以致于不需要真正看到类的实现,读者也应能推断出来。

比如
  1. for (Node v : u.getAdjacent()) {
  2. 17 if (v.state == State.Unvisited) {
  3. 18 if (v == end) {
  4. 19 return true;
  5. 20 } else {
  6. 21 v.state = State.Visiting;
  7. 22 q.add(v);
  8. 23 }
  9. 24 }
  10. 25 }
  11. 26 u.state = State.Visited
复制代码
这段代码告诉你Node类中至少有getAdjacent()这个成员函数,看名字和用法,这个函数的作用肯定是获得与Node相邻的其他Node;还有state成员,作用是标记这个Node是否被访问过,并且取值只有3种情况。至于是哪3种情况,看各个情况的名字应该非常清楚了。

我建议你不要太纠结于书中某个未实现的细节,因为对于那些题来说,重点不是实现这些细节,而是在假设这些细节已经被实现的基础上,如何解出题目。你在面试的时候,有可能同样需要做这些假设。
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-13 02:06:22 | 显示全部楼层
干.什么 发表于 2015-4-12 12:03
也和楼主一样纠结过,CC150 中关于 Graph 的题目远不如其他数据结构,但是做了点功课之后,我觉得作者这样 ...

赞····涨姿势了
回复 支持 反对

使用道具 举报

 楼主| ml0353662 发表于 2015-4-13 20:05:59 | 显示全部楼层
干.什么 发表于 2015-4-13 01:03
也和楼主一样纠结过,CC150 中关于 Graph 的题目远不如其他数据结构,但是做了点功课之后,我觉得作者这样 ...

非常感谢! 你的回答让我豁然开朗
回复 支持 反对

使用道具 举报

 楼主| ml0353662 发表于 2015-4-13 20:06:57 | 显示全部楼层
stellari 发表于 2015-4-12 23:30
是的,基本意思就是说:这里用了自定义的Graph和Node类,至于这两类的界面的API到底是什么样子,作者认为她 ...

谢谢,原来如此,我还以为面试时也要把自定义类之类的全部写一遍才行。
也就是说主要是要理解思想而不是一些实现的细节。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 07:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表