可以在 Directed Acyclic Graph 上使用广度优先搜索吗？
例如，你从根节点开始（假设它有3个连接的节点，边缘都从根指向它们），在BFS之后，你在有向边缘之后从根访问第一个连接节点，你必须回来到根节点并访问第二个连接节点，如果它是一个无向图，但你不能在有向图的情况下，所以我假设BFS不能用于有向无环图？
此外，一行节点 1 -> 2 -> 3 -> 4 可以被认为是有向无环图，对吗？
1 -> 2 -> 3 -> 4
谢谢
1 - > 2 - > 3 - > 4是DAG
BFS意味着快速搜索 . 如果您从节点u启动bfs，则将找到可从u访问的每个节点，但找不到那些无法从u访问的节点 .
例如G（V，E）图v = {1,2,3,4} E = {（1,2），（1,3），（4,1）}如果你从节点1运行bfs，节点将发现2和3，但未发现4
但如果你从4运行bfs，将会发现每个节点
因此，如果您知道DAG的拓扑排序，您可以按拓扑顺序从节点运行bfs，将发现每个节点并正确计算它们的级别 .
1 回答
1 - > 2 - > 3 - > 4是DAG
BFS意味着快速搜索 . 如果您从节点u启动bfs，则将找到可从u访问的每个节点，但找不到那些无法从u访问的节点 .
例如G（V，E）图v = {1,2,3,4} E = {（1,2），（1,3），（4,1）}如果你从节点1运行bfs，节点将发现2和3，但未发现4
但如果你从4运行bfs，将会发现每个节点
因此，如果您知道DAG的拓扑排序，您可以按拓扑顺序从节点运行bfs，将发现每个节点并正确计算它们的级别 .