BFS
BFS————queue
基本框架:
queue存储初始结点
while(queue非空)
{
取出队头
扩展队头
}
树、图的存储
-
树就是特殊的图,无向图就是特殊的有向图(每条边都双向)
-
所以我们只需要研究有向图的存储
-
有向图的存储方式:邻接矩阵、邻接表(用的多,和哈希表拉链法差不多)
拓扑序列
- 是针对有向图的,有环的有向图是不存在拓扑序的,有向无环图(拓扑图)一定存在拓扑序列。
入度为0的点入队
while(queue不空)
{
取出队头
枚举t的所有出边
删掉出边,对应入度--
if入度==0
入队
}