图的广度优先算法以及广度优先生成树

2744557306

首先了解一下图的两种存储方式

邻接矩阵，如下为有向图的的邻接矩阵。对于A结点，可以通往B结点，在我们第一列的A行B列就标识为1.对于C结点可以通往A结点，那么C行A列就被标注为1。其他节点也一样。

邻接表，下图为有向图的邻接表矩阵，对于计算机而言，会对邻接表进行一个0开始的的排列。由这个排列的序号代表结点，对于A结点而言，它只有一条通道，指向B而B的序号为2，所以就成了A->1。同理B指向C，E，F。也就对应的2，4，5。
9 H% J$ A$ S' E# c, h  Q8 z

了解了图的存储方式，我们就可以讲解图的广度优先算法了

对于下面的图我们对它进行广度优先算法，首先对2顶点进行广度优先算法，在图中，我们很容易得到2结点连接1，6结点。那么计算机是如何寻找呢？答案是在右边两个图的存储结构中寻找，在邻接矩阵中2结点的第一个点为1，所以结果为2 ->1.接下来再找2行中的元素（找邻接矩阵中的1）发现第二个元素为6。结果自然就变成了2 -> 1 ->6。在邻接矩阵中我们发现2行中已经没有元素了。接下来到下一个过程。我们寻找1的指向结点，在邻接矩阵中我们发现1指向5、指向2。由于2已经在我们的序列中了，意味着我们已经找到了且没有其他指向。所以结果为2 -> 1 ->6 ->5。接下来在找6结点中的元素，6元素指向2，3，7.所以2已经被找到，所以结果为2 ->1 ->6 ->5 ->3->7。接下来寻找5结点。我们发现5结点指向1结点，而1节点已经被找到。所以我们就跳到3结点，3结点指向4，6，7。所以结果为2 ->1 ->6 ->5 ->3 ->7 ->4。接下来在7结点中寻找。7结点指向6，3，4，8。同样由于序列中已经有了6，3，4结点。所以我们的结果为2 ->1 ->6 ->5 ->3 ->7 ->4 -> 8。

同理在邻接表中，也是这样的。但是由于邻接表的存储顺序并不一定会按照顺序存储。所以会出现2 - 6 - 1的现象。那么我们的结果就应该变为2 ->6 ->1 ->5 ->3 ->7 ->4 -> 8。

广度优先生成树，是根据广度优先算法生成的。只要对图进行广度优先查询就一定可以得到一颗树，这棵树的名字就叫广度优先生成树。如下图所示：

  R( ?$ G8 J, _
7 K/ n8 u+ o) d. e( E
& n" k$ [% l1 p2 h