CC150里的Graph到底什么意思。。。

百思不得其解。。。  CC150做到Graph的部分，书里直接就用了Graph这个类，但我找遍整个Java API，都没有。
将来估计也找不到， 所以不知道这些Graph的题是要怎么做呢？难道是自己编一个Graph的类来做？
而且书里用的Node有什么.state之类的， 这个好像也是没有的啊。。。。。
求大神指点

也和楼主一样纠结过，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 模式中也有体现。）

是的，基本意思就是说：这里用了自定义的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种情况，看各个情况的名字应该非常清楚了。

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

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

赞····涨姿势了

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

非常感谢！ 你的回答让我豁然开朗

stellari 发表于 2015-4-12 23:30
是的，基本意思就是说：这里用了自定义的Graph和Node类，至于这两类的界面的API到底是什么样子，作者认为她 ...

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