Find the out-component of a single vertex:

Find the out-component of a vertex set as the union of out-components:

Find the in-component of a vertex:

Highlight the different out-components:

Find the connected component for a vertex in an undirected graph:

Highlight the found component vertices:

Find the shortest distance between two vertices:

Find the shortest distance between two vertices, the hard way:

Set up functions for vertex visits (ignoring the precomputed distance):

Initialize the source vertex and traverse the graph in breadth-first order:

Extract the distance at the target and compare with

GraphDistance:

Find the black vertex closest to 1:

Count the number of discoveries when scanning the whole graph:

Set up a counter for each vertex and an event handler for counting the discoveries:

Some vertices have been discovered several times:

Compute all the connected components:

In an undirected graph,

BreadthFirstScan visits every vertex in a connected component:

Repeat the procedure until every vertex has been visited:

Test whether a graph is bipartite:

Try to find a consistent assignment of

for each vertex:

Each vertex is assigned the value

or

depending on the value at its predecessor:

When a vertex is rediscovered, it must not have the same value as the adjacent vertex:

The graph is bipartite if it can be scanned without finding any inconsistencies:

Construct a breadth-first scan tree using

:

Highlight the tree:

In a directed graph, the

edges can be classified as either

*back edges* or

*cross edges*:

Style tree edges black, back edges blue, and cross edges dashed:

The back edges would form cycles if added to the breadth-first scan tree:

In a timeline for each vertex, place a dot at the time of discovery and a line from previsit to postvisit:

Show timelines of events in a directed tree:

In an undirected tree:

In a directed

CycleGraph:

In an undirected

CycleGraph:

In a directed acyclic graph:

In a grid graph:

Show how the state of vertices changes during the scan:

Make discovered vertices red, active vertices yellow, visited vertices blue, and let non-tree edge color indicate whether they lead to

(red) or

(blue) invocation:

Find a shortest path in an unweighted graph:

Set up functions for vertex visits:

Traverse the graph in breadth-first order:

Reconstruct the path backward from the target vertex:

Find all shortest paths in an unweighted graph:

Set up functions for vertex visits:

Initialize properties at the source and traverse the graph in breadth-first order:

Extract the result at the target:

Betweenness centralities in Zachary's classic friendship network in a karate club:

Set up functions for vertex visits:

Accumulate

while considering all shortest paths from every vertex:

The cumulative distribution of betweenness centrality shows that two scores stand out:

Sort vertices in order of betweenness centrality (1 is the administrator, and 34 is the instructor):

Highlight the top two vertices: