b*********n 发帖数: 1258 | |
g*******y 发帖数: 1930 | 2 DFS肯定是可以的,DFS用来找back edge,一个back edge就一定是回路
BFS对于有向图貌似不行,BFS只能找到cross edge,但是cross edge不一定构成回路。
不过对于无向图的话,cross edge就是回路了。 |
w********p 发帖数: 948 | 3 DFS可以用back edge来判断是否有loop
BFS 稍微改点code, 对有向图,无向图也都可以 |
k***e 发帖数: 556 | 4 你平常是在哪找到的这些题目?能告知一下吗?我只知道careercup。
bfs can be used only for the undirected graph. it is easy to give a counter
example of directly graph that bfs did not work.
dfs works in both cases.
marking is definitely needed.
【在 b*********n 的大作中提到】 : 是不是mark一下访问过的就可以了
|
w********p 发帖数: 948 | 5 我也想知道大家都做些啥题
check circle in direct Graph G by BFS
If any logic error, please correct me
BFSCheckCircleDirectedGraph(G, s) { O(V+E)
For all vertex i in vertex[G] –s
color[i] = white
parent[i]=Null;
degree[i]=0;
color[s]=Gray;
parent[s]=Null;
degree[i]=0;
Enqueue (root s);
while Queue != 0
i = head of Queue
for each adjacency vertex j of vertex i
if color[j] == while then
color[j] = Gray;
degree[j] = degree[i]+1;
parent[j] = i;
|
k***e 发帖数: 556 | 6 你加了一个checkCircle,对于每个新grey的点再做bfs于已变色的vertices上,看是否
会回到该点。应该是正确的,时间复杂度为O(V^2).
ps,你说下伪码就可以了,我最怕读别人的代码来 :) |
w********p 发帖数: 948 | |
g*******y 发帖数: 1930 | 8 check circle有问题。你check circle中,怎么能用BFS里标记的颜色呢。
另外,一个check circle本质就是一个DFS(按照你的递归写法)。你想想,你的程序里
面得调用多少次check circle
【在 w********p 的大作中提到】 : 我也想知道大家都做些啥题 : check circle in direct Graph G by BFS : If any logic error, please correct me : BFSCheckCircleDirectedGraph(G, s) { O(V+E) : For all vertex i in vertex[G] –s : color[i] = white : parent[i]=Null; : degree[i]=0; : color[s]=Gray; : parent[s]=Null;
|
H*M 发帖数: 1268 | 9 你们为什么非得用BFS?
DFS不是很简单很standard的吗?
【在 g*******y 的大作中提到】 : check circle有问题。你check circle中,怎么能用BFS里标记的颜色呢。 : 另外,一个check circle本质就是一个DFS(按照你的递归写法)。你想想,你的程序里 : 面得调用多少次check circle
|
g*******y 发帖数: 1930 | 10 我前面的回帖就说了,DFS做这个挺好的,BFS不合适。
【在 H*M 的大作中提到】 : 你们为什么非得用BFS? : DFS不是很简单很standard的吗?
|
H*M 发帖数: 1268 | 11 就是啊 DFS一个经典用处不就是这个吗
难道interviewer故意为难同学们用BFS...也太令人发指了吧
【在 g*******y 的大作中提到】 : 我前面的回帖就说了,DFS做这个挺好的,BFS不合适。
|
w********p 发帖数: 948 | 12 这个额也没法子,n 年前,被面试 问道如何用bfs, dfs, 找circle。 反正答得乱的很
【在 g*******y 的大作中提到】 : check circle有问题。你check circle中,怎么能用BFS里标记的颜色呢。 : 另外,一个check circle本质就是一个DFS(按照你的递归写法)。你想想,你的程序里 : 面得调用多少次check circle
|
a****n 发帖数: 1887 | |