图的遍历

来自计算思维百科
跳转至: 导航搜索

图的遍历('Traversing Graph)是指从图中某一顶点出发访遍图中其余顶点,且使每个顶点仅被访问一次。图的一种遍历方式是深度优先,它是一种回溯算法。

深度优先遍历从图中一个顶点出发一直向前走,依次访问与最近访问顶点邻接的顶点,无顶点访问时,返回至上一顶点,选择它的另一个未被访问的邻接顶点继续。

假设图1中无向图(a)。从V1出发的深度优先遍历过程如图1(b)所示,图中实线表示搜索,虚线表示回溯,线上数字表示搜索、回溯步骤。

                9.2.1.png

                                 图1 图的深度优先遍历过程 

深度优先遍历从顶点V1出发,访问V2,然后依次访问V4、V8、V5,因V5没有未访问过的邻接点,回溯至V8,V8也没有未访问过的邻接点,继续回溯,直到V1,V1有未访问的邻接点V3,故访问V3,继续遍历,直到回溯到V1,V1没有未访问过的邻接点,算法终止。图3-3(a)的深度优先遍历顺序是:V1,V2,V4,V8,V5,V3,V6,V7

该算法如何在网络爬虫中应用呢?可以将网站看做节点,网页中的超链接看做弧,那么互联网的不同网站和超链接构成图。网络爬虫可以从一个网站出发,下载这个网站的所有网页,然后再通过超链接进入下一个网站,下载该网站的所有网页,按照深度优先遍历如此继续下去,可下载整个互联网。当然,网络爬虫并不只是简单的深度优先遍历,它也用到广度优先遍历。