Breadth-First Search

Algorithm link: Breadth-First Search

Breadth-first Search (BFS) is an algorithm used to explore the vertices of a graph layer by layer. It starts at the given vertex and explores all vertices at the present depth prior to moving on to the vertices at the next depth level.

Specifications

CREATE QUERY tg_bfs(SET<STRING> v_type, SET<STRING> e_type,INT max_hops=10,
    VERTEX v_start, BOOL print_accum = True, STRING result_attr = "",
    STRING file_path = "", BOOL display_edges = True)

Time complexity

This algorithm has a time complexity of \$O(V+E)\$, where \$V\$ is equal to the number of vertices and \$E\$ is equal to the number of edges.

Characteristic Value

Result

Returns all the vertices that are accessible from the source vertex

Required input parameters

  • v_type: vertex types to traverse

  • e_type: edge types to traverse

  • max_hops: look only this far from each vertex

  • v_start: source vertex for traversal

  • print_accum: print JSON output

  • result_attr: INT attr to store results to

  • file_path: file to write CSV output to

  • display_edges:output edges for visualization

Result size

V = number of vertices

Graph types

Directed or undirected edges, weighted or unweighted edges

Example

In the example below, we run tg_bfs algorithm from the source vertex alex on the social10 graph.

# Use _ for default values
RUN QUERY tg_bfs(["Person"], ["Friend"], _, ("Alex","Person"), _, _, _, _) (1)
1 Putting _ in the position of a parameter will use the default value for that parameter.

Below is the visualized result of the query:

bfs ex