Breadth-First Search

Supported Graph Characteristics

Unweighted edges

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

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,  SET<STRING> e_type_set,INT max_hops=10,
    VERTEX v_start, BOOL print_results = True, STRING result_attribute = "",
    STRING file_path = "", BOOL display_edges = True)

Parameters

Parameter Description Default

SET<STRING> v_type_set

Vertex types to traverse

(empty set of strings)

SET<STRING> e_type_set

Edge types to traverse

(empty string)

INT max_hops

Maximum hops for the algorithm to look from each vertex

10

VERTEX v_start

Source vertex for traversal. Provide the vertex ID and type as a tuple: ("id","type")

N/A

BOOL print_results

Whether to print JSON output

True

STRING result_attribute

The vertex attribute to store results to in INT format

(empty string)

STRING file_path

The path for a CSV output file

(empty string)

BOOL display_edges

Whether to output edges for visualization

False

Output

Returns all the vertices that are accessible from the source vertex.

The result size is equal to \$V\$, or the number of vertices.

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.

Example

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

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