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 | |
