cugraph.bfs#

cugraph.bfs(G, start=None, depth_limit=None, i_start=None, directed=None, return_predecessors=True)[source]#

找到图的广度优先遍历的距离和前驱节点。与SSSP不同，BFS支持无权图。

Parameters:
Gcugraph.Graph, networkx.Graph, CuPy or SciPy sparse matrix

图或矩阵对象，应包含连接信息。如果存在边权重，应为单精度或双精度浮点值。

自版本24.12起已弃用：接受networkx.Graph已被弃用，并将在未来版本中移除。对于networkx.Graph，请直接使用带有nx-cugraph后端的networkx。参见：https://rapids.ai/nx-cugraph/

startInteger or list, optional (default=None)

图的顶点ID，遍历从此开始，或者如果是一个列表，遍历从图的每个组件中的顶点开始。图的每个连接组件只允许一个顶点。

depth_limitInteger or None, optional (default=None)

限制搜索的深度

i_startInteger, optional (default=None)

与start相同，为了API兼容性而添加。只能设置start或i_start，不能同时设置两者。

directedbool, optional (default=None)
NOTE

仅适用于非图形类型（例如稀疏矩阵）的G值。如果与图形对象一起使用，则会引发TypeError。

如果为True，则将输入矩阵转换为有向的cugraph.Graph， 否则将使用无向的cugraph.Graph对象。

return_predecessorsbool, optional (default=True)

是否返回每个顶点的前驱节点（否则返回-1）

Returns:
Return value type is based on the input type. If G is a cugraph.Graph,
returns:
cudf.DataFrame

df['vertex'] 顶点ID

df['distance'] 每个顶点到起始顶点的路径距离

df['predecessor'] 对于列中的每个第i个位置，表示在'vertex'列中位置i的顶点之前紧邻的顶点ID

If G is a networkx.Graph, returns:

pandas.DataFrame 的内容与上述描述的 cudf.DataFrame 相同。

If G is a CuPy or SciPy matrix, returns:

一个由CuPy ndarrays（如果输入是CuPy矩阵）或Numpy ndarrays（如果输入是SciPy矩阵）组成的2元组，表示：

distance: cupy or numpy ndarray

源点和顶点之间的最短距离的ndarray。

predecessor: cupy or numpy ndarray

从源点到顶点的路径上前驱节点的ndarray，可用于重建最短路径。

…或者如果 return_sp_counter 为 True，则返回一个包含上述两个数组的 3 元组，再加上：

sp_counter: cupy or numpy ndarray

指向每个顶点的最短路径数量的ndarray。

示例

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> df = cugraph.bfs(G, 0)
On this page
Show Source