图遍历算法

上一篇文章中我们简单介绍了什么是图和图分析，图分析的应用场景和优点，以及一些常用的图工具，这篇文章里将介绍一下简单的图遍历算法。

图的遍历

图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。图遍历算法主要分为两种：广度优先搜索和深度优先搜索。

广度优先搜索

广度优先搜索是从图的一个顶点开始，向外一层一层地搜索，优先访问所有相邻顶点，直至图中所有顶点都被访问到为止的搜索方法，如下图所示：

 

             图1                              图2

   

             图3                              图4

图1至4展示了在一张图中依据广度优先算法得到的遍历顺序，可以很清楚地看见搜索顺序是逐层往下，将一个顶点的相邻顶点全部遍历完毕后再遍历这些顶点的全部相邻顶点，依次往下进行。

深度优先搜索

深度优先搜索是深度优先搜索的遍历顺序为搜索一个顶点的首个相邻顶点，沿着一条路径走到底然后回溯再走下一条路径，如下图所示：

  

             图5                              图6

  

             图7                              图8

             图9                    

从图5至9可以明显看到深度优先遍历与广度优先遍历的区别，深度优先遍历每次只遍历一个顶点的首个相邻顶点，然后再遍历该相邻顶点的首个相邻顶点，依次往下。

总结

以上就是对于基本的图遍历算法的介绍，感兴趣的朋友可以自己动手尝试，在这里我推荐使用graphscope这个平台。graphscope是阿里达摩院智能计算实验室研发并开源的全球首个一站式超大规模分布式图计算平台，支持多种图算法，可以方便地进行图分析和图计算，并且在性能上也达到极致。在图分析测试 LDBC GraphAnalytics Benchmark 上，GraphScope 与PowerGraph 以及其他最新系统比较，几乎在所有算法和数据集的组合中居于领先水平。从下图中我们可以看到，在执行广度优先遍历算法（BFS）时，GraphScope用时0.23秒，远小于PowerGraph的4.31秒。

图10

GraphScope 的白皮书、代码已经在github.com/alibaba/graphscope 开源，可以直接试用。