Clone Graph 的两个follow up

如果要用2d array，图的顶点认为是0～n的表示？
如果是一般的连通图，顶点定义为
Node {
  label: value;
  neighbors: list of Nodes
}
不用哈希表能避免环？

zhuyisong 发表于 2017-1-12 08:29
2d array 如何做。。。你是说把输入的节点改成一个2darray吗？那输入就要跟面试官交流了？

可以啊.. 就说maybe before inputting the graph into the method we can change the way of representing the graph converting it into a 2d array, which is better for running time.

laiguojiuhao 发表于 2017-1-12 08:40
如果要用2d array，图的顶点认为是0～n的表示？
如果是一般的连通图，顶点定义为
Node {

CS 101--
图有两种表示方式，one is 2d array, a[i][j] means from node i to node j is connected or not. 0 means not connected, 1 means connected. 你只要copy这个2d array, 图里面所有的关系就知道了. 跟避免环无关，因为根本就没有用到BFS这个algorithm.

yuanxiehuang 发表于 2017-1-12 08:45
CS 101--
图有两种表示方式，one is 2d array, a[j] means from node i to node j is connected or not. ...

replace a[j] with a左括号i括号左括号j右括号

laiguojiuhao 发表于 2017-1-12 08:40
如果要用2d array，图的顶点认为是0～n的表示？
如果是一般的连通图，顶点定义为
Node {

我只是就dfs这个algorithm说我觉得不好，请不要take it personal, if I offend you in some way, I apologize.

yuanxiehuang 发表于 2017-1-12 08:50
我只是就dfs这个algorithm说我觉得不好，请不要take it personal, if I offend you in some way, I apolo ...

啊没有啊。。。dfs又不是我发明的，为啥会觉得offended，不过如果是说递归不好也可以自己维护栈啊，空间也比bfs开得少，也不用找最近的，不是很懂为啥会笼统地说dfs不好？工作中经常出现无限深的图吗？

意思就是用adjacent matrix表示图，instead of adjacent list，取决于顶点类的定义吧，感觉还是要和面试的确认一下

laiguojiuhao 发表于 2017-1-12 09:38
啊没有啊。。。dfs又不是我发明的，为啥会觉得offended，不过如果是说递归不好也可以自己维护栈啊，空间 ...

1. 我的意思是在遍历图的过程中，DFS这个algorithm不好, DFS是个最通用和强大的算法之一，还有至于递归啥的，工作中真的很少见到，因为尽量避免这些可能会引发爆栈的算法.

yuanxiehuang 发表于 2017-1-12 09:57
1. 我的意思是在遍历图的过程中，DFS这个algorithm不好, DFS是个最通用和强大的算法之一，还有至于递归啥 ...

图的遍历一个简单的应用就是爬虫，不过写过爬虫的人都知道一个很common的问题就是如果碰到要爬eg. www.google.com/12-01-2016这种网页会一直爬下去，所以我说在所有涉及图的经典算法中常用的是inverted index, bfs, 地杰斯特拉算法，都不是DFS算法. 然后在工作中，我的经验是，尽量不用递归的，自己维护栈啥的，这有点不切实际...code review的时候肯定会说.

yuanxiehuang 发表于 2017-1-12 10:04
图的遍历一个简单的应用就是爬虫，不过写过爬虫的人都知道一个很common的问题就是如果碰到要爬eg. www.go ...

感谢！受教
也许不太相关，不过自己维护栈并不是不切实际的做法，实际上iterative的dfs和bfs代码的差别很小，主要就是出入queue的顺序，fifo queue或者lifo queue。dfs最主要的问题就是遇到无限深图，像你说的网页一直爬下去，bfs就是空间开得很大；所以还有折衷的depth limited dfs，bidirectional bfs啥的。写算法的人要意识到自己在做什么吧，如果你的搜索空间巨大，全部搜完用什么都爆栈。而且像functional programming都全部用递归

laiguojiuhao 发表于 2017-1-12 11:11
感谢！受教
也许不太相关，不过自己维护栈并不是不切实际的做法，实际上iterative的dfs和bfs代码的差别 ...

嗯好，多讨论讨论技术对大家的技术和工作能力的提升都有帮助.