Graph traversal algorithm

In the last article, we briefly introduced what graph and graph analysis are, the application scenarios, advantages of graph analysis, and some commonly used graph tools. In this article, we will introduce a simple graph traversal algorithm.

Graph traversal means that starting from any specified vertex (called the initial point) in a given graph, all vertices in the graph are accessed along the edges of the graph according to a certain search method, so that each vertex is visited only once. This process is called graph traversal. Graph traversal algorithms are mainly divided into two types: breadth first search and depth first search.

Breadth-first search is a search method that starts from a vertex of the graph and searches outward layer by layer, accesses all adjacent vertices preferentially until all vertices in the graph are accessed, as shown in the figure below:

Figure1:

Figure2:

Figure 3:

Figure 4:

Figure 1–5 shows the traversal order obtained by the breadth-first algorithm in a graph. It can be clearly seen that the search order is layer by layer. After all the adjacent vertices of a vertex are traversed, all the adjacent vertices of these vertices are traversed. and proceed downward in turn.

The depth advantage search is that the traversal sequence of the depth-first search is to search for the first adjacent vertex of a vertex, follow a path to the end, then go back to the next path, as shown in the following figure:

Figure 5:

Figure 6:

Figure 7:

Figure 8:

Figure 9:

From Figures 5–9, we can clearly see the difference between depth-first traversal and breadth-first traversal. Depth-first traversal only traverses the first adjacent vertex of one vertex at a time, then traverses the first adjacent vertex of the adjacent vertex, and then goes down.

This is the introduction of the basic graph traversal algorithm, if you are interested, i recommend you try GraphScope.

Graphscope is the world’s first one-stop ultra-large-scale distributed graph computing platform developed and open-sourced by the Intelligent Computing Laboratory of Alibaba Dharma Academy. It supports a variety of graph algorithms, which can easily perform graph analysis and graph calculations, and achieves high performance. On the LDBC GraphAnalytics Benchmark for graph analysis testing, GraphScope compares with PowerGraph and other latest systems, and it takes the lead in almost all combinations of algorithms and data sets. From the figure below, we can see that when performing the breadth-first traversal algorithm (BFS), GraphScope takes 0.23 seconds, which is much less than PowerGraph’s 4.31 seconds. GraphScope’s open source coding have been released at github.com/alibaba/graphscope, you can try it directly.

Figure 10: