【第三轮】7.7-7.13 CareerCup 4.2

4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】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

【解题思路】递归思想。当a和b链接后，设定a到b为1，b到a为-1，无路径的两点间距离设为0，以此类推。之后判断a和c是否有路径时，从a开始遍历全图，直到能遍历至c为止。显然，如果在半程中碰到-1或者全为0（即没有路），则返回false。遍历成功则为true
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】
https://github.com/donnice/donnice/blob/master/Q4_2
【Test case】
我对照的是附件里的图。大家可以拿自己的有向图试一试

【解题思路】BST, actually qiuckunion... do not use recursion, but recursion could be easier
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】https://gist.github.com/bitcpf/629c20bb88618ac70df0

【解题思路】BFS
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/ddf4f88a839401471697

【解题思路】BFS
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/nealhu/ff50192e189ae3f01e4f

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

【解题思路】
BFS

【时间复杂度】
O(V+E)

【空间复杂度】
O(V+E)

【gist link】
https://gist.github.com/chrislukkk/e37504aa6c3dc21b49fe

【解题思路】
DFS
【时间复杂度】
O(V+E)
【空间复杂度】
O(V+E)
【gist link】
https://gist.github.com/chouclee/60c5d74e6fa206e656c7

【解题思路】
BFS

【时间复杂度】
O(v+e)


【空间复杂度】
O(v)


【gist link】
https://gist.github.com/happyWinner/cd03c98bdf6ca5a5c4ec