Traversal

Components

Connected components and strongly connected components.

Undirected Graphs

is_connected(G)	Return True if G is connected.
number_connected_components(G)	Return the number of connected components in G.
connected_components(G)	Return a list of lists of nodes in each connected component of G.
connected_component_subgraphs(G)	Return a list of graphs of each connected component of G.
node_connected_component(G, n)	Return a list of nodes of the connected component containing node n.

Directed Graphs

is_strongly_connected(G)	Return True if G is strongly connected.
number_strongly_connected_components(G)	Return the number of strongly connected components in G.
strongly_connected_components(G)	Returns a list of strongly connected components in G.
strongly_connected_component_subgraphs(G)	Return a list of graphs of each strongly connected component of G.
strongly_connected_components_recursive(G)	Returns list of strongly connected components in G.
kosaraju_strongly_connected_components(G[, ...])	Returns list of strongly connected components in G.

DAGs

Algorithms for directed acyclic graphs (DAGs).

topological_sort(G[, nbunch])	Return a list of nodes in topological sort order.
topological_sort_recursive(G[, nbunch])	Return a list of nodes in topological sort order.
is_directed_acyclic_graph(G)	Return True if the graph G is a directed acyclic graph (DAG)

Distance

Shortest paths, diameter, radius, eccentricity, and related methods.

eccentricity(G[, v, sp, with_labels])	Return the eccentricity of node v in G (or all nodes if v is None).
diameter(G[, e])	Return the diameter of the graph G.
radius(G[, e])	Return the radius of the graph G.
periphery(G[, e])	Return the periphery of the graph G.
center(G[, e])	Return the center of graph G.

Shortest Paths

Shortest path algorithms.

average_shortest_path_length(G[, weighted])	Return the average shortest path length.
shortest_path(G, source, target)	Return a list of nodes in a shortest path between source and target.
shortest_path_length(G, source, target)	Return the shortest path length between the source and target.
single_source_shortest_path(G, source[, cutoff])	Return list of nodes in a shortest path between source and all other nodes reachable from source.
single_source_shortest_path_length(G, source)	Return the shortest path length from source to all reachable nodes.
all_pairs_shortest_path(G[, cutoff])	Return shortest paths between all nodes.
all_pairs_shortest_path_length(G[, cutoff])	Return dictionary of shortest path lengths between all nodes in G.
dijkstra_path(G, source, target)	Returns the shortest path from source to target in a weighted
dijkstra_path_length(G, source, target)	Returns the shortest path length from source to target in a weighted
single_source_dijkstra_path(G, source)	Return list of nodes in a shortest path between source and all other nodes reachable from source for a weighted graph.
single_source_dijkstra_path_length(G, source)	Returns the shortest path lengths from source to all other
single_source_dijkstra(G, source[, target, ...])	Returns shortest paths and lengths in a weighted graph G.
bidirectional_dijkstra(G, source, target)	Dijkstra’s algorithm for shortest paths using bidirectional search.
bidirectional_shortest_path(G, source, target)	Return a list of nodes in a shortest path between source and target.
dijkstra_predecessor_and_distance(G, source)	Returns two dictionaries representing a list of predecessors of a node and the distance to each node respectively.
predecessor(G, source[, target, cutoff, ...])	Returns dictionary of predecessors for the path from source to all
floyd_warshall(G[, huge])	The Floyd-Warshall algorithm for all pairs shortest paths.

Shortest paths using A* (“A star”) algorithm.

astar_path(G, source, target[, heuristic])	Return a list of nodes in a shortest path between source and target
astar_path_length(G, source, target[, heuristic])	Return a list of nodes in a shortest path between source and target

Search

Search algorithms.

See also networkx.path.

dfs_preorder(G[, source, reverse_graph])	Return list of nodes connected to source in depth-first-search preorder.
dfs_postorder(G[, source, reverse_graph])	Return list of nodes connected to source in depth-first-search postorder.
dfs_predecessor(G[, source, reverse_graph])	Return predecessors of depth-first-search with root at source.
dfs_successor(G[, source, reverse_graph])	Return succesors of depth-first-search with root at source.
dfs_tree(G[, source, reverse_graph])	Return directed graph (tree) of depth-first-search with root at source.