graph - BFS が DFS よりも並列化に適しているのはなぜですか?

Question

BFS アルゴリズムは、DFS よりも並列実装に適していると読みました。なぜこれが真実であるべきなのか、直感を理解するのに苦労しています。誰でも説明できますか？

ありがとう

Answer 1

BFS はフロンティアを伝播する手順です。「伝播」とは、アクセスされていないすべての隣接する頂点をキューにプッシュすることを意味し、それらは個別に処理できます。

DFS では、頂点は A->B->C のような方向に沿って 1 つずつ訪問されます。B を訪問する前に C を訪問する必要があります。これは、簡単に並列化できない順次処理です。

しかし、実際には、BFS と DFS の両方を並列化するのは困難です。これは、すべての処理ノードがグローバル情報を認識している必要があるためです。グローバル変数にアクセスするには、常にノード間の同期と通信が必要です。

Answer 2

一般的なDFSとBFSに関するいくつかの良い情報があります。

• 幅優先探索と深さ優先探索
• BFSとDFSの違い
• 幅優先探索/深さ優先探索のアニメーション
• DFS と BFS の違いは何ですか?

特にアニメーションは、 BFSがより多くの並列概念を使用する方法を示しています。BFSは並列に実装できると思いますが、 DFSの並列ソリューションはありません。 DFSは、すべての子を 1 回呼び出す線形アルゴリズムです。