【第三轮】7.7-7.13 CareerCup 4.2

【解题思路】
用DFS递归遍历直到访问到目标节点或无连通路径……
研究了半天肿么表示graph真是弱爆了=。=最后终于在GeeksforGeeks上找到些不错的栗子 喵
【时间复杂度】
V(O+E)
【空间复杂度】
V(O+E)
【gist link】
https://gist.github.com/fe02d53a80a5684422da

【解题思路】
BFS , DFS
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/fa095f6e3b3f82d4c83e

ps : 比较 DFS & BFS

【解题思路】
BFS
【时间复杂度】
O(V+E)
【空间复杂度】
O(V)
【gist link】
https://gist.github.com/iwilbert/fef11bcadca3b1acfa9e

【解题思路】 BFS
【时间复杂度】 O(V+E)
【空间复杂度】 O(V)
【gist link】 https://gist.github.com/jyhjuzi/11fb399098dafe34a3b4

【解题思路】 DFS和BFS都写了一遍, 用hashtable做访问记录
【时间复杂度】 O(N)
【空间复杂度】 O(N)
【gist link】
https://gist.github.com/Noahsark/5b95a325a0b86e58ba0d

jyh橘子 发表于 2014-7-15 13:09
【解题思路】 BFS
【时间复杂度】 O(V+E)
【空间复杂度】 O(V)

首先 object永远不要用 “==” 比较，最安全的做法是用Object.equal()
其次 不要写类似于“(current.nexts != null && current.nexts.size() != 0)”的表达，即时你知道current.next已经initialize了，NPE的隐患总会有的

renli3000 发表于 2014-7-18 03:29
首先 object永远不要用 “==” 比较，最安全的做法是用Object.equal()
其次 不要写类似于“(current.nex ...

灰常感谢！  
第一条有道理，我以后多注意。但是第二条我不太懂，如果&&应该是前一个成立了才会判断后一个的吧，应该不会有NPE了吧？  希望你给解释一下，谢谢哈~

jyh橘子 发表于 2014-7-18 04:24
灰常感谢！  
第一条有道理，我以后多注意。但是第二条我不太懂，如果&&应该是前一个成立了才会判断后一 ...

举个例子 计算if(a && b) 时
java会先算 c = a & b 然后是 if(c)
所以b的NPE 是在计算c的时候抛出的

renli3000 发表于 2014-7-18 04:46
举个例子 计算if(a && b) 时
java会先算 c = a & b 然后是 if(c)
所以b的NPE 是在计算c的时候抛出的

Got it !    非常感谢哈，我基础不好，各种不扎实！

【解题思路】1. 表示directed graph 参考了geeksforgeeks，每个顶点有他对应的adjacent list，addedge()用来添加directed edge
                  2. 找路径，最后就变成了在adjacent lists 里找，为了防止可能存在的circle，访问过的顶点需要标记
                  3. 具体查找采用bfs，用一个queue来添加当前正在查看的顶点，dequeue一个顶点要保证已经enqueue它的所有adjacent vertices
                     只要queue没空就循环找下去，直到发现返回true，不然就false

【时间复杂度】O(V+E)
【空间复杂度】O(V)
【gist link】: https://gist.github.com/xun-gong/7242a6c9205de1a3f43d