r******n
发帖数: 170 | 1 有可以简单coding出来的实现吗？
觉得topological sortting之类的方法，可以说说，似乎不好code。但是面试官似乎要
code。 |
g*****i
发帖数: 2162 | |
A**u
发帖数: 2458 | 3 会问这个吗？
totally 不会
【在 r******n 的大作中提到】
: 有可以简单coding出来的实现吗？
: 觉得topological sortting之类的方法，可以说说，似乎不好code。但是面试官似乎要
: code。
|
B*******1
发帖数: 2454 | 4 不就是dfs加个上color吗？
【在 r******n 的大作中提到】
: 有可以简单coding出来的实现吗？
: 觉得topological sortting之类的方法，可以说说，似乎不好code。但是面试官似乎要
: code。
|
r******n
发帖数: 170 | 5 sorry,我自己有点混淆了。
有向图，必须有edge的概念，所以只能用topological sort判断，对吧？
判断tree还是graph,随便用dfs/bfs，看是否一个node会visit多次就知道了。
【在 g*****i 的大作中提到】
: http://en.wikipedia.org/wiki/Topological_sorting 有算法啊,如果s为空但是graph还有edge就有环
|
i******s
发帖数: 301 | 6 不一定哦，看我ebay search电面，三哥想搞你就会问。
【在 A**u 的大作中提到】
: 会问这个吗？
: totally 不会
|
i******s
发帖数: 301 | 7 对，关键在于图是怎样表示，是用矩阵还是邻接表，当时我就用的wiki的第一个算法，
因为之前写过。如果被问到，你先要搞清楚图怎么表示，剩下的其实还好，说实话我觉
得问这种问题的interviewer都有点想搞你的意思。
【在 r******n 的大作中提到】
: sorry,我自己有点混淆了。
: 有向图，必须有edge的概念，所以只能用topological sort判断，对吧？
: 判断tree还是graph,随便用dfs/bfs，看是否一个node会visit多次就知道了。
|
j********x
发帖数: 2330 | 8 topo sort 要在确定dag之后做，反过来干嘛。。。
【在 r******n 的大作中提到】
: sorry,我自己有点混淆了。
: 有向图，必须有edge的概念，所以只能用topological sort判断，对吧？
: 判断tree还是graph,随便用dfs/bfs，看是否一个node会visit多次就知道了。
|
l***i
发帖数: 1309 | 9 you can compute indeg[] for every node. Then start with any node with indeg=
0 and decrease all its neighbor's indeg by 1, push all indeg=0 nodes into a
queue and keep going. If you can exhaust all nodes, then it is DAG (assume
graph is connected, or you can use bfs/dfs to mark all nodes in current
connected component), otherwise there are cycles. Correctness can be proved
by induction. |
i******r
发帖数: 793 | 10 我觉得两种方法都行：
1.求强连通分量
2.拓扑排序 |
z******w
发帖数: 36 | 11 1 time DFS is enough, find the backward edge. If the backward edge exist,
there are cycles in the diagram. |
c*******0
发帖数: 5247 | 12 Why do you even need a Topo sort? Finding DAG is not a topo sort, it's just
used there. |
h********e
发帖数: 1972 | 13 DFS标号法。。。。这个undergraduate algorithm.. |
