说我有一个已连接且无向的图G，我想将G转换为DAG。解决方案对我来说很清楚：我将为每个节点分配一个数字，然后，仅当分配给u的数字小于v时，才将每个边（u，v）定向为u-> v。
但是，这不是我最初的解决方案。首先，我想，为什么不只运行BFS？我知道BFS永远不会生成循环，只会生成树或交叉边缘（不创建循环）。我知道BFS对于有向图是有问题的，但是给定的图G是无向。有人告诉我BFS在这里不起作用，但没有告诉为什么。我试图独自思考为什么，但还是不明白。
谢谢！
BFS正常工作。如果按照发现顶点的顺序处理每个顶点的所有边，则每个边将从较旧的顶点变为较新的顶点。
如果按BFS顺序对顶点进行编号，则结果与您的编号方案一致。