作业地址：http://coursera.cs.princeton.edu/algs4/assignments/wordnet.html
作业难点：
1、作业为第二部分的第一次作业，主要是熟悉程序代码书写，关键是设计数据结构；
2、数据结构设计：
①我们需要设计一个list，用来存放synsets的第二部分，同时为了保持索引id，使用ArrayList比较好；
②构建synsets集，为高效存取这里使用HashMap；
③存取hypernyms集，为高效存取这里也使用HashMap；
④构建WordGraph，即WordNet的有向图；
3、如何判断WordGraph是否有根：
通过一个HashSet集ids，在构建synsets时增加id，在构建hpyernyms时移除id，然后id为空时，说明图有根。
4、如何判断两点的祖先：
通过两次BreadthFirstDirectedPaths遍历，记录两点的广度优先搜索路径，然后逐个遍历WordGraph的顶点，寻找最短路径祖先；
5、如何求得两点的距离：
求两点到祖先的距离之和即可。
容易扣分点：
无
部分代码：
1、WordNet数据结构及构造函数：
private ArrayList<String> wordList; private HashMap<String, Bag<Integer>> idMap; private HashSet<Integer> ids; private Digraph G; private SAP sap; // constructor takes the name of the two input files public WordNet(String synsets, String hypernyms) { ids = new HashSet<Integer>(); wordList = new ArrayList<String>(); idMap = new HashMap<String, Bag<Integer>>(); readSynsets(synsets); // build digraph G = new Digraph(wordList.size()); buildWordDigraph(G, buildHynMap(hypernyms)); // check is rooted DAG isRootedDAG(); // create sap instance sap = new SAP(G); }
2、SAP数据结构及求祖先函数：
private final Digraph G; private BreadthFirstDirectedPaths bfsPrior, bfsNext; // a common ancestor of v and w that participates in a shortest // ancestral bfs; -1 if no such bfs public int ancestor(int u, int w) { checkInput(u, w); int result = -1; int shortestLength = Integer.MAX_VALUE; bfsPrior = new BreadthFirstDirectedPaths(G, u); bfsNext = new BreadthFirstDirectedPaths(G, w); for (int i = 0; i < G.V(); i++) { if (bfsPrior.hasPathTo(i) && bfsNext.hasPathTo(i)) { int dist = bfsPrior.distTo(i) + bfsNext.distTo(i); if (dist < shortestLength) { shortestLength = dist; result = i; } } } return result; }
原文：http://www.cnblogs.com/notTao/p/6357331.html
