Traversal

Components

Undirected Graphs

is_connected (G)	Return True if G is connected. For undirected graphs only.
number_connected_components (G)	Return the number of connected components in G. For undirected graphs only.
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 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[, source])	Returns list of strongly connected components in G.

DAGs

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

Distance

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.

Paths

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 the source and target.
bidirectional_shortest_path (G, source, target)	Return list of nodes in a shortest path between 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[, cutoff])	Return the shortest path length from source to all reachable nodes.
all_pairs_shortest_path (G[, cutoff])	Return dictionary of 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 graph G.
dijkstra_path_length (G, source, target)	Returns the shortest path length from source to target in a weighted graph G.
bidirectional_dijkstra (G, source, target)	Dijkstra’s algorithm for shortest paths using bidirectional search.
single_source_dijkstra_path (G, source)	Returns the shortest paths from source to all other reachable nodes in a weighted graph G.
single_source_dijkstra_path_length (G, source)	Returns the shortest path lengths from source to all other reachable nodes in a weighted graph G.
single_source_dijkstra (G, source[, target])	Dijkstra’s algorithm for shortest paths in a weighted graph G.
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 nodes in G.
floyd_warshall (G[, huge])	The Floyd-Warshall algorithm for all pairs shortest paths.

Search

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.