title: Why can't BFS convert an undirected graph to a DAG?
body: <p>Say I have a connected and <em>undirected</em> graph G, and I want to convert G to a DAG. The solution is clear to me: I will assign each node a number, and then, each edge (u,v) will be directed u->v only if the number that is assigned to u is smaller than v.</p>
  
  <p>However, this was not my initial solution. At first, I thought, why not just running BFS? I know that BFS would never generate a cycle, only a tree or a cross edge (which <em>do not</em> create cycles). I know that BFS is problematic with directed graphs, but the given graph G is <em>undirected</em>. I was told that BFS won't work here, but wasn't told why. I tried to think why by myself but I still don't get it.</p>
  
  <p>Thanks!</p>