In the BFS algorithm in the booklet, it says in a comment in case BLACK: "can only happen in directed graphs". I tihk it should be "undirected", since in undirected graphs, if (u,v) is in E then u is in Adj(u) , and vice versa. And in directed (simple) graphs, if (u,v) is in E then (v,u) isn't.If I'm wrong, ill be happy to know why. Thanks.
Date: 31 Oct 2014 14:14
Number of posts: 2
RSS: New posts
In directed simple graphs, (u,v) and (v,u) can both be valid edges.. The fact that the graph is simple means that there can't be two edges that are both (u,v) (or an edge (u,u)).
In an undirected graph, there are no forwards edges or back edges (therefore a back edge can only exist in a directed graph). If you find a vertex that is black, it is either your parent or uncle, or it has already marked the edge as a cross edge (try running BFS on some simple examples).