下一问题是，如何基于一个任意的强连通有向图在网络上进行广度优先搜索（BFS），有向图上具有明确区分的源节点。更精确地讲，如何给有向图创建广度优先生成树。创建这种树是为了有一个方便的结构用作广播通信的基础。BFS树可以使一个特定节点上的进程向网络中所有其他进程发送消息的最大通信时间最小化（假设消息在每个通信信道中的传递时间相等）。
在每一对邻接节点都是双向通信的时候，也就是网络是无向图的时候，BFS问题和它的解决方法就比较简单。我们会指出对这种情况的简化。
