对于年前后出生的同学来说，我们童年时接触的电脑，是这个样子的：在那个时代，小伙伴们喜爱的“玩具”，有的时候，可能并不是现在我们耳熟能详的那些属于那个时代的大型游戏，而是某些连“游戏”都称不上的Windows系统组件——比如这货：MSPaint，这个在Win98中甚至需要手动安装的软件，对于很多90后来说甚至是童年的一部分。而随着时代的变迁，虽然我们有了Photoshop之类的功能更加强大的软件，但MSPaint这样一个简约而不简单的软件，却一直延续到了今天，连界面都有了很大的变化：今天我们要谈的，是MSPaint这个软件的一个经常用到的小功能——油漆桶工具。大家都知道，油漆桶工具的作用，是将一片封闭的区域填充成指定的颜色——比如这样：而有的时候，我们会发现：用油漆桶在画布上点击一下之后，整个画布都被填充颜色了，比如下面这张图。我们都知道，之所以会出现这样的现象，是因为我们在绘制图形的时候，虽然画的线条看起来没有问题，但是放大画布就可以看清，其实线条并没有真正闭合，仍然有肉眼不易察觉的缝隙存在——因此颜料桶“倾倒”的“颜料”就会从线条的缝隙中“渗出来”，进而将整个画布都染成同一颜色。那么，这跟数据结构有什么关系呢？在前面的课程中，我们已经学习了图结构，以及图的两种重要的搜索算法——广度优先搜索与深度优先搜索。而这里要用到的，则是图的一种算法——“洪水灌溉”（FloodFill）算法。这个算法的基本思路，是从一个起始点出发，不断地把当前顶点的相邻顶点染成同一种颜色，直到把图中跟起始点连通的整个区域（称为联通分量）染色完成为止。如果我们把图类比成一个复杂的水管系统的话，那么洪水灌溉算法，正如它的字面意思所描述的那样，就相当于是从入口灌水，直到把整个连通器都灌满为止。如果我们感性地观察的话，我们是不是可以发现——洪水灌溉算法，其实跟上文描述的，画图工具的颜料“倾倒”过程，存在着相当程度的共通之处呢？看到这里，我想聪明的你，应该已经能够明白，为什么我们首先要介绍画图工具了——没错，以FloodFill为代表的一系列图论相关算法，在现实中有着十分广泛的应用。而画图的颜料桶工具，就是它的一个典型的应用场景——把整个画布抽象成一个图结构，以画布上没有被铅笔画过的像素点为图的顶点，颜料桶的填充过程实际上是一个FloodFill的过程。现在我们已经知道，现实中的很多事物都可以抽象成图这种应用极其广泛的数据结构——这样一来，更多图论相关的算法也就有了用武之地。不光是FloodFill，还有其他有趣且有用的算法——想要了解这些更高级的算法吗？快来学习《CS：数据结构》最新一章吧！预览时标签不可点收录于合集#个
转载请注明地址:http://www.1xbbk.net/jwbls/941.html
