129 字
1 分钟
图的遍历
从某一顶点出发,对图中所有顶点访问一次且仅访问一次
由于图可能存在环路,因此在访问过程中需要记录已经访问过的顶点,以避免重复访问。就是构造一个visited数组。
深度优先DFS
不撞南墙不回头,一直往下走,没有下一个就回退到上一个。
深度遍历序列不唯一
广度优先搜索BFS
层层扩散,一条边可达,两条边可达…
从某一顶点出发,对图中所有顶点访问一次且仅访问一次
由于图可能存在环路,因此在访问过程中需要记录已经访问过的顶点,以避免重复访问。就是构造一个visited数组。
不撞南墙不回头,一直往下走,没有下一个就回退到上一个。
深度遍历序列不唯一
层层扩散,一条边可达,两条边可达…