Скажем, у меня есть подключенный и ненаправленный граф G, и я хочу преобразовать G в DAG. Решение для меня ясно: я назначу каждому узлу номер, а затем каждое ребро (u, v) будет направлено u-> v, только если число, назначенное u, меньше v.
Однако это не было моим первоначальным решением. Сначала я подумал, а почему бы просто не запустить BFS? Я знаю, что BFS никогда не будет генерировать цикл, только дерево или перекрестие (которое не создает циклы). Я знаю, что BFS проблематична c с ориентированными графами, но данный граф G является ненаправленным . Мне сказали, что BFS здесь не работает, но не сказали почему. Я пытался подумать почему сам, но до сих пор не понимаю.
Спасибо!