如何找到原始有向圖？

Question

我正在考慮給我的作業問題，如下所示： 如果給定一個有向（或無向圖）的BFS和DFS遍歷， 如何找到原始圖？ 這兩種情況都有可能嗎？

三江源

Answer 1

如果我理解正確的話，這是不可能的，因爲BFS和DFS產生一棵樹，樹有| V | -1邊。因此，在這兩棵樹中，最多有2 | V | -2個不同的邊，原始圖可以有高達| V |（| V | -1）的邊指向，並且| V |（| V | -1 ）/ 2爲無向圖。