({{, (RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])[g,s,{"(Subscript[event, 1])"->(Subscript[f, 1]),"(Subscript[event, 2])"->(Subscript[f, 2]),…}]
performs a breadth-first scan (bfs) of the graph g starting at the vertex s and evaluates (Subscript[f, i]) whenever "(Subscript[event, i])" occurs.}, {, (RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])[g,{"(Subscript[event, 1])"->(Subscript[f, 1]),"(Subscript[event, 2])"->(Subscript[f, 2]),…}]
performs a breadth-first scan of the whole graph g.}, {, (RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])[{v->w,…},…]
uses rules v->w to specify the graph g. }})

OpenersNotesSection(Spacer1)Details

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])[g,s,{…}] visits vertices in the graph g connected to the vertex s in breadth-first order.

In breadth-first order, all vertices adjacent to the currently visited vertex are visited first.

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])[g,{…}] performs multiple breadth-first scans starting from the first vertex in the vertex list of g, and then starts from the first vertex in the vertex list that has not been visited, effectively scanning each connected component.

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])[g,…] gives a list {(Subscript[w, 1]),(Subscript[w, 2]),…} representing a tree where (Subscript[w, i]) is the predecessor of (Subscript[v, i]) and where {(Subscript[v, 1]),(Subscript[v, 2]),…} is the vertex list of g.

Events that provide access to vertex discovery include:

"DiscoverVertex"->fd calls fd[u,v,d] when vertex u is discovered from visited vertex v at distance d from the start vertex s.

"UnvisitedVertex"->fru calls fru[u,v] when the unvisited vertex u is rediscovered from the visited vertex v.

"VisitedVertex"->frv calls frv[u,v] when the visited vertex u is rediscovered from the visited vertex v.

Events that provide access to vertex visits include:

"PrevisitVertex"->fs calls fs[u] before the vertex u has been visited.

"PostvisitVertex"->fe calls fe[u] after the vertex u has been visited.

A bfs-tree is the tree generated by the edges traversed during a breadth-first scan.

Events that provide access to edge exploration from the visited vertex include:

"FrontierEdge"->ffe calls ffe[v->u] for an edge v->u where the vertex v is being visited and u has not been discovered. Typically useful for scanning the bfs-tree.

"CycleEdge"->fce calls fce[v->u] for an edge v->u where the vertex v is being visited and u has already been discovered. Typically useful for finding cycles or edges not in the bfs-tree.

For an undirected graph the edges used in the callbacks are taken to be undirected edges v<->u.

OpenersPrimaryExamplesSection(Spacer1)Examples  (83)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Visit the vertices of a tree in breadth-first order:

BreadthFirstScan[,1,{"PrevisitVertex"->(Print["Visiting ",#]&)}];

Highlight the breadth-first scan tree:

GridGraph[{3,5},VertexSize->{5->Medium}]

Reap[BreadthFirstScan[%,5,{"FrontierEdge"->Sow}]][[2,1]]//HighlightGraph[%,#]&

OpenersExampleSection1(Spacer1)Scope  (18)

OpenersExampleSubsection0(Spacer1)Basic  (6)

Use events to execute code during the scan:

Reap[BreadthFirstScan[,1,{"FrontierEdge"->Sow}]][[2,1]]

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan]) works with undirected graphs:

g=;

HighlightGraph[%,
Reap[BreadthFirstScan[%,1,{"FrontierEdge"->Sow}]][[2,1]]]

Directed graphs:

g=;

HighlightGraph[g,
Reap[BreadthFirstScan[g,1,{"FrontierEdge"->Sow}]][[2,1]]]

Use rules to specify the graph:

g={2\[DirectedEdge]1,1\[DirectedEdge]4,5\[DirectedEdge]1,3\[DirectedEdge]2,6\[DirectedEdge]2,3\[DirectedEdge]4,3\[DirectedEdge]7,4\[DirectedEdge]8,6\[DirectedEdge]5,7\[DirectedEdge]6,8\[DirectedEdge]7,8\[DirectedEdge]5};

HighlightGraph[g,
Reap[BreadthFirstScan[g,1,{"FrontierEdge"->Sow}]][[2,1]]]

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan]) discovers the entire graph if the start vertex is omitted:

Reap[BreadthFirstScan[,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan]) works with large graphs:

g=GridGraph[{10,10,10,10}];

Timing[BreadthFirstScan[g,1]//Length]

OpenersExampleSubsection1(Spacer1)Vertex Visit Process  (2)

Vertices are visited in the order of discovery:

g=PetersenGraph[5,2]

Reap[BreadthFirstScan[g,1,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

Reap[BreadthFirstScan[g,1,{"PrevisitVertex"->Sow}]][[2,1]]

Only one vertex is visited at a time:

g=PetersenGraph[4,1]

Reap[BreadthFirstScan[g,1,{"PrevisitVertex"->(Sow["("<>ToString[#]<>" "]&),
"PostvisitVertex"->(Sow[ToString[#]<>") "]&)}]][[2,1]]

OpenersExampleSubsection2(Spacer1)Edge Discovery Process  (2)

"FrontierEdge" is triggered for edges that lead to undiscovered vertices:

g=;

StringJoin@@Reap[BreadthFirstScan[g,1,{"FrontierEdge"->(Sow["Frontier: "<>ToString[#]<>". "]&),"PrevisitVertex"->(Sow["Start visit "<>ToString[#]<>". "]&),"PostvisitVertex"->(Sow["Finish "<>ToString[#]<>".\n"]&)}]][[2,1]]

"CycleEdge" is triggered for edges that lead to discovered vertices:

print[g0_?GraphQ]:=
Module[{g=g0},With[{str=StringJoin@@Reap[BreadthFirstScan[g,1,{"CycleEdge"->(Sow["Cycle edge: "<>ToString[#]<>". "]&),"PrevisitVertex"->(Sow["Start visit "<>ToString[#]<>". "]&),"PostvisitVertex"->(Sow["Finish "<>ToString[#]<>".\n"]&),
"FrontierEdge"->((PropertyValue[{g,#},EdgeStyle]=Directive[Arrowheads[Medium],Thick,Black])&)}]][[2,1]]},Print[g];Print[str]]]

In a directed graph:

print[]

In an undirected graph:

print[]

OpenersExampleSubsection3(Spacer1)Vertex Discovery Process  (3)

The "DiscoverVertex" event is triggered when a vertex is discovered for the first time:

StringJoin@@Reap[BreadthFirstScan[,1,{"DiscoverVertex"->(Sow["Discover: "<>ToString[#1]<>". "]&),"PrevisitVertex"->(Sow["\nStart visit "<>ToString[#]<>". "]&),"PostvisitVertex"->(Sow["Finish "<>ToString[#]<>"."]&)}]][[2,1]]

The "VisitedVertex" event is triggered for revisited vertices that have been visited:

StringJoin@@Reap[BreadthFirstScan[,1,{"VisitedVertex"->(Sow["Visited: "<>ToString[#1]<>". "]&),"PrevisitVertex"->(Sow["Start visit "<>ToString[#]<>". "]&),"PostvisitVertex"->(Sow["Finish "<>ToString[#]<>".\n"]&)}]][[2,1]]

The "UnvisitedVertex" event is triggered for discovered vertices that have not yet been visited:

StringJoin@@Reap[BreadthFirstScan[,1,{"UnvisitedVertex"->(Sow["Unvisited: "<>ToString[#1]<>". "]&),"PrevisitVertex"->(Sow["Start visit "<>ToString[#]<>". "]&),"PostvisitVertex"->(Sow["Finish "<>ToString[#]<>".\n"]&)}]][[2,1]]

OpenersExampleSubsection4(Spacer1)Scan Tree Predecessors  (5)

(RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan]) returns a list of predecessors in the breadth-first scan tree:

BreadthFirstScan[,7]

The predecessor list can be used to reconstruct the breadth-first scan tree:

g=;

BreadthFirstScan[g,7]

Construct edges between each vertex and its predecessor:

Thread[%\[UndirectedEdge]VertexList[g]]

Edges that are self-loops are not part of the tree:

HighlightGraph[g,Cases[%,u_\[UndirectedEdge]v_/;u=!=v]]

When the scan produces a spanning tree, (RefLink[TreeGraph, paclet:ref/TreeGraph]) is more convenient:

g=;

HighlightGraph[g,TreeGraph[VertexList[g],BreadthFirstScan[g,7]]]

The predecessors can also be obtained using the "DiscoverVertex" event:

g=;

Initialize with the (RefLink[VertexList, paclet:ref/VertexList]) and reassign values when a vertex is discovered:

pre=VertexList[g];

BreadthFirstScan[g,7,{"DiscoverVertex"->((pre[[VertexIndex[g,#1]]]=#2)&)}];
pre

Compare with the return value from (RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan]):

%===BreadthFirstScan[g,7]

The breadth-first scan tree can also be obtained using the "FrontierEdge" event:

g=;

Reap[BreadthFirstScan[g,7,{"FrontierEdge"->Sow}]][[2,1]]

HighlightGraph[g,%]

OpenersExampleSection2(Spacer1)Options  (42)

OpenersExampleSubsection5(Spacer1)"CycleEdge"  (8)

After "OutEdges", each edge is passed to either "FrontierEdge" or "CycleEdge":

g=;

"FrontierEdge" is triggered iff the edge leads to a vertex being discovered for the first time:

BreadthFirstScan[g,1,{"DiscoverVertex"->(Print["Discover: ",#1]&),"OutEdges"->(Print["Out-edge: ",#]&),"FrontierEdge"->(Print["Frontier edge: ",#]&),"CycleEdge"->(Print["Cycle edge: ",#]&)}];

Following "CycleEdge", either "VisitedVertex" or "UnvisitedVertex" is triggered:

g=;

"VisitedVertex" is triggered iff the adjacent vertex has already been visited:

BreadthFirstScan[g,1,{"CycleEdge"->(Print["Cycle edge: ",#]&),"VisitedVertex"->(Print["Revisiting visited: ",#]&),"UnvisitedVertex"->(Print["Revisiting unvisited: ",#]&)}];

Indicate calls to the "CycleEdge" function in a directed tree:

g=;

The event is never triggered for this graph:

Reap[BreadthFirstScan[g,1,{"CycleEdge"->Sow}]][[2]]

In an undirected tree:

g=;

The event is triggered for every edge:

Reap[BreadthFirstScan[g,1,{"CycleEdge"->Sow}]][[2,1]]

Sort[Sort/@%]===Sort[Sort/@EdgeList[g]]

In a directed (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

Reap[BreadthFirstScan[g,1,{"CycleEdge"->Sow}]][[2,1]]

In an undirected (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

The event is triggered more than once for some edges:

Reap[BreadthFirstScan[g,1,{"CycleEdge"->Sow}]][[2,1]]

{Length[%],EdgeCount[g]}

In a directed acyclic graph:

g=;

Reap[BreadthFirstScan[g,1,{"CycleEdge"->Sow}]][[2,1]]

Highlight the cycle edges:

HighlightGraph[g,%]

In a grid graph:

g=;

The event is triggered more than once for some edges:

Reap[BreadthFirstScan[g,1,{"CycleEdge"->Sow}]][[2,1]]

{Length[%],EdgeCount[g]}

OpenersExampleSubsection6(Spacer1)"DiscoverVertex"  (8)

Following "FrontierEdge", "DiscoverVertex" is triggered for the adjacent vertex:

g=;

"DiscoverVertex" is also triggered for the starting vertex:

BreadthFirstScan[g,1,{"FrontierEdge"->(Print["Frontier edge: ",#]&),"DiscoverVertex"->(Print["Discover ",#1," from ",#2," at distance ",#3]&)}];

The "DiscoverVertex" event is triggered when a vertex is discovered for the first time:

g=;

It can be used to find the breadth-first ordering of the vertices:

dv[u_,v_,d_]:=Sow[u]

Reap[BreadthFirstScan[g,1,{"DiscoverVertex"->dv}]][[2,1]]

The "DiscoverVertex" event is triggered prior to the call to "PrevisitVertex":

Reap[BreadthFirstScan[g,1,{"DiscoverVertex"->(Sow["Discover "<>ToString[#1]]&),"PrevisitVertex"->(Sow["Previsit "<>ToString[#]]&)}]][[2,1]]

Show the arguments being passed to the "DiscoverVertex" function in a directed tree:

g=;

print[u_,v_,d_]:=Print[u," discovered from ",v," at distance ",d]

BreadthFirstScan[g,1,{"DiscoverVertex"->print}];

In an undirected tree:

g=;

print[u_,v_,d_]:=Print[u," discovered from ",v," at distance ",d]

BreadthFirstScan[g,1,{"DiscoverVertex"->print}];

In a directed (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

print[u_,v_,d_]:=Print[u," discovered from ",v," at distance ",d]

BreadthFirstScan[g,1,{"DiscoverVertex"->print}];

In an undirected (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

print[u_,v_,d_]:=Print[u," discovered from ",v," at distance ",d]

BreadthFirstScan[g,1,{"DiscoverVertex"->print}];

In a directed acyclic graph:

g=;

print[u_,v_,d_]:=Print[u," discovered from ",v," at distance ",d]

BreadthFirstScan[g,1,{"DiscoverVertex"->print}];

In a grid graph:

g=;

print[u_,v_,d_]:=Print[u," discovered from ",v," at distance ",d]

BreadthFirstScan[g,1,{"DiscoverVertex"->print}];

OpenersExampleSubsection7(Spacer1)"FrontierEdge"  (8)

After "OutEdges", each edge is passed to either "FrontierEdge" or "CycleEdge":

g=;

"FrontierEdge" is triggered iff the edge leads to a vertex being discovered for the first time:

BreadthFirstScan[g,1,{"DiscoverVertex"->(Print["Discover: ",#1]&),"OutEdges"->(Print["Out-edge: ",#]&),"FrontierEdge"->(Print["Frontier edge: ",#]&),"CycleEdge"->(Print["Cycle edge: ",#]&)}];

Following "FrontierEdge", "DiscoverVertex" is triggered for the adjacent vertex:

g=;

"DiscoverVertex" is also triggered for the starting vertex:

BreadthFirstScan[g,1,{"FrontierEdge"->(Print["Frontier edge: ",#]&),"DiscoverVertex"->(Print["Discover ",#1," from ",#2," at distance ",#3]&)}];

The "FrontierEdge" function is called for every edge in a directed tree:

g=;

Reap[BreadthFirstScan[g,1,"FrontierEdge"->Sow]][[2,1]]

Sort[%]===Sort[EdgeList[g]]

It is called for every edge in an undirected tree:

g=;

Reap[BreadthFirstScan[g,1,"FrontierEdge"->Sow]][[2,1]]

Sort[Sort/@%]===Sort[Sort/@EdgeList[g]]

Highlight the breadth-first scan tree in a directed (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

Reap[BreadthFirstScan[g,1,{"FrontierEdge"->Sow}]][[2,1]]

HighlightGraph[g,%]

In an undirected (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

Reap[BreadthFirstScan[g,1,{"FrontierEdge"->Sow}]][[2,1]]

HighlightGraph[g,%]

In a directed acyclic graph:

g=;

Reap[BreadthFirstScan[g,1,{"FrontierEdge"->Sow}]][[2,1]]

HighlightGraph[g,%]

In a grid graph:

g=;

Reap[BreadthFirstScan[g,1,{"FrontierEdge"->Sow}]][[2,1]]

HighlightGraph[g,%]

OpenersExampleSubsection8(Spacer1)"PostvisitVertex"  (2)

"PostvisitVertex" is the last event triggered during a vertex visit:

g=;

Like "DiscoverVertex", it can be used to find the breadth-first ordering of the vertices:

Reap[BreadthFirstScan[g,1,{"PostvisitVertex"->Sow}]][[2,1]]

After "PostvisitVertex", the visit process continues with the next unvisited vertex in the queue:

Reap[BreadthFirstScan[g,1,{"PrevisitVertex"->(Sow["Previsit "<>ToString[#]]&),"PostvisitVertex"->(Sow["Postvisit "<>ToString[#]]&)}]][[2,1]]

Relative order of "PrevisitVertex", "PostvisitVertex", and "DiscoverVertex":

g=;

Reap[BreadthFirstScan[g,1,{"DiscoverVertex"->(Sow["Discover "<>ToString[#1]]&),"PrevisitVertex"->(Sow["Previsit "<>ToString[#1]]&),"PostvisitVertex"->(Sow["Postvisit "<>ToString[#1]]&)}]][[2,1]]

OpenersExampleSubsection9(Spacer1)"PrevisitVertex"  (2)

The "PrevisitVertex" event is triggered at the beginning of each vertex visit:

g=;

Like "DiscoverVertex", it can be used to find the breadth-first ordering of the vertices:

Reap[BreadthFirstScan[g,1,{"PrevisitVertex"->Sow} ]][[2,1]]

"PrevisitVertex" is triggered at some time after the call to "DiscoverVertex":

Reap[BreadthFirstScan[g,1,{"DiscoverVertex"->(Sow["Discover "<>ToString[#1]]&),"PrevisitVertex"->(Sow["Previsit "<>ToString[#]]&)}]][[2,1]]

Relative order of "PrevisitVertex", "PostvisitVertex", and "DiscoverVertex":

g=;

Reap[BreadthFirstScan[%,1,{"DiscoverVertex"->(Sow["Discover "<>ToString[#1]]&),"PrevisitVertex"->(Sow["Previsit "<>ToString[#1]]&),"PostvisitVertex"->(Sow["Postvisit "<>ToString[#1]]&)}]][[2,1]]

OpenersExampleSubsection10(Spacer1)"UnvisitedVertex"  (7)

After "CycleEdge", either "VisitedVertex" or "UnvisitedVertex" is triggered:

g=;

"UnvisitedVertex" is triggered iff the adjacent vertex has not already been visited:

BreadthFirstScan[%,1,{"CycleEdge"->(Print["Cycle edge: ",#]&),"VisitedVertex"->(Print["Revisiting visited: ",#]&),"UnvisitedVertex"->(Print["Revisiting unvisited: ",#]&)}];

Indicate the predecessor being passed to the "UnvisitedVertex" function in a directed tree:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

The event is never triggered for this graph:

BreadthFirstScan[g,1,{"UnvisitedVertex"->print}];

In an undirected tree:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

The event is never triggered for this graph:

BreadthFirstScan[g,1,{"UnvisitedVertex"->print}];

In a directed (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

print[u_,v_]:=Print[u," revisited from ",v]

The event is never triggered for this graph:

BreadthFirstScan[g,1,{"UnvisitedVertex"->print}];

In an undirected (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

print[u_,v_]:=Print[u," revisited from ",v]

BreadthFirstScan[g,1,{"UnvisitedVertex"->print}];

In a directed acyclic graph:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

Before a discovered vertex has been visited, it may be rediscovered zero, one, or more times:

BreadthFirstScan[g,1,{"UnvisitedVertex"->print}];

In a grid graph:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

BreadthFirstScan[g,1,{"UnvisitedVertex"->print}];

OpenersExampleSubsection11(Spacer1)"VisitedVertex"  (7)

After "CycleEdge", either "VisitedVertex" or "UnvisitedVertex" is triggered:

g=;

"VisitedVertex" is triggered iff the adjacent vertex has already been visited:

BreadthFirstScan[g,1,{"CycleEdge"->(Print["Cycle edge: ",#]&),"VisitedVertex"->(Print["Revisiting visited: ",#]&),"UnvisitedVertex"->(Print["Revisiting unvisited: ",#]&)}];

Indicate the predecessor being passed to the "VisitedVertex" function in a directed tree:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

The event is never triggered for this graph:

BreadthFirstScan[g,1,{"VisitedVertex"->print}];

In an undirected tree:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

After a vertex has been visited, it is revisited from each of its children:

BreadthFirstScan[g,1,{"VisitedVertex"->print}];

In a directed (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

print[u_,v_]:=Print[u," revisited from ",v]

BreadthFirstScan[g,1,{"VisitedVertex"->print}];

In an undirected (RefLink[CycleGraph, paclet:ref/CycleGraph]):

g=;

print[u_,v_]:=Print[u," revisited from ",v]

BreadthFirstScan[g,1,{"VisitedVertex"->print}];

In a directed acyclic graph:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

The event is never triggered for this graph:

BreadthFirstScan[g,1,{"VisitedVertex"->print}];

In a grid graph:

g=;

print[u_,v_]:=Print[u," revisited from ",v]

After a vertex has been visited, it may be revisited zero, one, or more times:

BreadthFirstScan[g,1,{"VisitedVertex"->print}];

OpenersExampleSection3(Spacer1)Applications  (17)

OpenersExampleSubsection12(Spacer1)Basic Applications  (10)

Find the out-component of a single vertex:

outComponent[g_?GraphQ,v_]/;VertexQ[g,v]:=
Reap[BreadthFirstScan[g,v,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

outComponent[,2]

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

outComponent[g_?GraphQ,v_]/;VertexQ[g,v]:=
Reap[BreadthFirstScan[g,v,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

outComponent[g_?GraphQ,vl_List]:=Union@@Map[outComponent[g,#]&,vl]

outComponent[,{2,8}]

Find the in-component of a vertex:

inComponent[g_?GraphQ,v_]/;VertexQ[g,v]:=
Reap[BreadthFirstScan[ReverseGraph[g],v,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

Highlight the different out-components:

g=;

{HighlightGraph[g,inComponent[g,2]],HighlightGraph[g,inComponent[g,3]]}

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

connectedComponent[g_?UndirectedGraphQ,v_]/;VertexQ[g,v]:=
Reap[BreadthFirstScan[g,v,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

Highlight the found component vertices:

g=;

HighlightGraph[g,connectedComponent[g,9]]

Find the shortest distance between two vertices:

graphDistance[g_?GraphQ,s_,t_]/;VertexQ[g,s]&&VertexQ[g,t]:=
Catch[BreadthFirstScan[g,s,{"DiscoverVertex"->Function[{u,v,d},If[u===t,Throw[d]]]}];∞]

graphDistance[,1,12]

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

s=1;t=3*4;
g=GridGraph[{3,4},VertexSize->{s->Medium,t->Medium}]

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

discoverFun[u_,v_,_]:=If[u≠v,PropertyValue[{g,u},"Distance"]=PropertyValue[{g,v},"Distance"]+1]

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

PropertyValue[{g,s},"Distance"]=0;

BreadthFirstScan[g,s,{"DiscoverVertex"->discoverFun}];

Extract the distance at the target and compare with (RefLink[GraphDistance, paclet:ref/GraphDistance]):

{PropertyValue[{g,t},"Distance"],GraphDistance[g,s,t]}

Find the black vertex closest to 1:

g=;

BreadthFirstScan[g,1,
{"DiscoverVertex"->(If[PropertyValue[{g,#1},VertexStyle]===Black,Throw[#1]]&)}]//Catch

Count the number of discoveries when scanning the whole graph:

g=;

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

Do[PropertyValue[{g,v},"count"]=0,{v,VertexList[g]}];

discover[v_,u_,_]/;u===v:=(++PropertyValue[{g,v},"count"];Print["Starting scan at ",v])

discover[v_,u_,_]/;u=!=v:=(++PropertyValue[{g,v},"count"];Print["Discover ",v])

BreadthFirstScan[g,"DiscoverVertex"->discover];

Some vertices have been discovered several times:

Table[v->PropertyValue[{g,v},"count"],{v,VertexList[g]}]

Compute all the connected components:

g=;

In an undirected graph, (RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan]) visits every vertex in a connected component:

Reap[BreadthFirstScan[g,2,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

HighlightGraph[g,%]

Repeat the procedure until every vertex has been visited:

Do[PropertyValue[{g,v},"Visited"]=False,{v,VertexList[g]}];

findComponent[start_]:=Reap[BreadthFirstScan[g,start,{"DiscoverVertex"->((PropertyValue[{g,#1},"Visited"]=True;Sow[#1])&)}]][[2,1]]

Reap[Do[If[¬PropertyValue[{g,start},"Visited"],Sow[findComponent[start]]],
{start,VertexList[g]}]][[2,1]]

Compare with (RefLink[ConnectedComponents, paclet:ref/ConnectedComponents]):

Sort[Sort/@%]===Sort[Sort/@ConnectedComponents[g]]

Test whether a graph is bipartite:

g=GraphDisjointUnion[CompleteGraph[{2,3}],CycleGraph[7]]

Try to find a consistent assignment of "Partition" for each vertex:

Do[PropertyValue[{g,v},"Partition"]=0,{v,VertexList[g]}];

Each vertex is assigned the value 1 or -1 depending on the value at its predecessor:

discover[u_,v_,_]/;u===v:=PropertyValue[{g,u},"Partition"]=1

discover[u_,v_,_]/;u=!=v:=PropertyValue[{g,u},"Partition"]=-PropertyValue[{g,v},"Partition"]

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

rediscover[u_,v_]:=If[PropertyValue[{g,u},"Partition"]==PropertyValue[{g,v},"Partition"],Throw[False]]

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

Catch[BreadthFirstScan[g,{"DiscoverVertex"->discover,"VisitedVertex"->rediscover,"UnvisitedVertex"->rediscover}];True]

OpenersExampleSubsection13(Spacer1)Illustrating the Scan Process  (4)

Construct a breadth-first scan tree using "FrontierEdge":

g=GridGraph[{3,4},VertexSize->{2->Medium}]

Reap[BreadthFirstScan[g,2,{"FrontierEdge"->Sow}]][[2,1]]

Highlight the tree:

HighlightGraph[g,%]

In a directed graph, the "CycleEdge" edges can be classified as either back edges or cross edges:

backEdgeQ[g_,v_\[DirectedEdge]a_]:=Catch[Module[{t=v,p},While[True,If[t===a,Throw[True]];
p=PropertyValue[{g,t},"Pre"];
If[p===t,Throw[False],t=p]]]]

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

color[g0_?GraphQ,v_]/;VertexQ[g0,v]:=
Module[{g=g0},
BreadthFirstScan[g,1,{"DiscoverVertex"->((PropertyValue[{g,#1},"Pre"]=#2)&),"FrontierEdge"->((PropertyValue[{g,#},EdgeStyle]=Directive[Arrowheads[Small],Thick,Black])&),"CycleEdge"->((PropertyValue[{g,#},EdgeStyle]=If[backEdgeQ[g,#],Directive[Arrowheads[Small],Blue],Directive[Arrowheads[Small],Black,Dashed]])&)}];
g]

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

{color[,1],color[,1]}

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

vertexTimeline[data_]:=With[{p=First/@Position[data,True],tMax=25},Graphics[{Gray,Thin,Line[{{0,0},{tMax+1,0}}],Black,Thick,Disk[{p[[1]],0},0.2],Line[{{p[[2]],0},{If[Length[p]==3,p[[3]],tMax+1],0}}]},PlotRange->{{0,tMax+1},{-0.5,0.5}},ImageSize->400]]

graphTimelines[g_,start_]:=
With[{data=Reap[BreadthFirstScan[g,start,{"DiscoverVertex"->(Sow[{#1,"",""}]&),"PrevisitVertex"->(Sow[{"",#1,""}]&),"PostvisitVertex"->(Sow[{"","",#1}]&)}]][[2,1]]},TableForm[Table[vertexTimeline[Thread[Or@@Map[#===v&,data\[Transpose],{2}]]],{v,VertexList[g]}],TableHeadings->{VertexList[g],None}]]

Show timelines of events in a directed tree:

graphTimelines[,1]

In an undirected tree:

graphTimelines[,1]

In a directed (RefLink[CycleGraph, paclet:ref/CycleGraph]):

graphTimelines[,1]

In an undirected (RefLink[CycleGraph, paclet:ref/CycleGraph]):

graphTimelines[,1]

In a directed acyclic graph:

graphTimelines[,1]

In a grid graph:

graphTimelines[,1]

Show how the state of vertices changes during the scan:

Dynamic[g,Initialization:>(g=SetProperty[,ImageSize->150];)]

Make discovered vertices red, active vertices yellow, visited vertices blue, and let non-tree edge color indicate whether they lead to "UnvisitedVertex" (red) or "VisitedVertex" (blue) invocation:

pause:=Pause[0.5]

BreadthFirstScan[g,1,{"DiscoverVertex"->((PropertyValue[{g,#1},VertexStyle]=Red;pause)&),"PrevisitVertex"->((PropertyValue[{g,#},VertexStyle]=Yellow;pause)&),"PostvisitVertex"->((PropertyValue[{g,#},VertexStyle]=Blue;pause)&),"FrontierEdge"->((PropertyValue[{g,#},EdgeStyle]=Directive[Arrowheads[Small],Dashing[{}],Thick,Black];pause)&),"UnvisitedVertex"->((PropertyValue[{g,#2\[DirectedEdge]#1},EdgeStyle]=Directive[Arrowheads[Small],Dashing[{}],Red];pause)&),"VisitedVertex"->((PropertyValue[{g,#2\[DirectedEdge]#1},EdgeStyle]=Directive[Arrowheads[Small],Dashing[{}],Blue];pause)&)}];

OpenersExampleSubsection14(Spacer1)Shortest Path Applications  (3)

Find a shortest path in an unweighted graph:

s=1;
t=3*4;
g=GridGraph[{3,4},VertexSize->{s->Medium,t->Medium}]

Set up functions for vertex visits:

discoverFun[u_,v_,d_]:=If[u≠v,PropertyValue[{g,u},"Predecessor"]=v]

Traverse the graph in breadth-first order:

BreadthFirstScan[g,s,{"DiscoverVertex"->discoverFun}];

Reconstruct the path backward from the target vertex:

Reap[Module[{v=t},While[v≠s,Sow[v];v=PropertyValue[{g,v},"Predecessor"]];Sow[v]]][[2,1]]//Reverse

Compare with (RefLink[FindShortestPath, paclet:ref/FindShortestPath]):

{HighlightGraph[g,PathGraph[%]],HighlightGraph[g,PathGraph@FindShortestPath[g,s,t]]}

Find all shortest paths in an unweighted graph:

s=1;
t=3*4;
g=GridGraph[{3,4},VertexSize->{s->Medium,t->Medium}]

Set up functions for vertex visits:

discoverFun[u_,v_,d_]:=If[u≠v,PropertyValue[{g,u},"ShortestPaths"]=Table[Append[p,u],{p,PropertyValue[{g,v},"ShortestPaths"]}];PropertyValue[{g,u},"Distance"]=d]

revisitFun[u_,v_]:=If[PropertyValue[{g,u},"Distance"]==PropertyValue[{g,v},"Distance"]+1,PropertyValue[{g,u},"ShortestPaths"]=Join[PropertyValue[{g,u},"ShortestPaths"],Table[Append[p,u],{p,PropertyValue[{g,v},"ShortestPaths"]}]]]

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

PropertyValue[{g,s},"ShortestPaths"]={{s}};
PropertyValue[{g,s},"Distance"]=0;

BreadthFirstScan[g,s,{"DiscoverVertex"->discoverFun,"VisitedVertex"->revisitFun,"UnvisitedVertex"->revisitFun}];

Extract the result at the target:

Table[HighlightGraph[g,p],{p,PathGraph/@PropertyValue[{g,t},"ShortestPaths"]}]

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

g=ExampleData[{"NetworkGraph","ZacharyKarateClub"}]

Set up functions for vertex visits:

discoverFun[u_,v_,d_]:=(If[u=!=v,PropertyValue[{g,u},"ShortestPathCount"]=PropertyValue[{g,v},"ShortestPathCount"]];
PropertyValue[{g,u},"Distance"]=d)

revisitFun[u_,v_]:=If[PropertyValue[{g,u},"Distance"]==PropertyValue[{g,v},"Distance"]+1,PropertyValue[{g,u},"ShortestPathCount"]+=PropertyValue[{g,v},"ShortestPathCount"]]

Accumulate "BetweennessCentrality" while considering all shortest paths from every vertex:

Do[PropertyValue[{g,v},"BetweennessCentrality"]=0,{v,VertexList[g]}];

Do[Do[PropertyValue[{g,v},"ShortestPathCount"]=0,{v,VertexList[g]}];PropertyValue[{g,s},"ShortestPathCount"]=1;BreadthFirstScan[g,s,{"DiscoverVertex"->discoverFun,"VisitedVertex"->revisitFun,"UnvisitedVertex"->revisitFun}];
Do[With[{score=Total[Table[((PropertyValue[{g,v},"ShortestPathCount"])/(PropertyValue[{g,u},"ShortestPathCount"]))PropertyValue[{g,u},"PathScore"],{u,Select[EdgeList[g,v\[UndirectedEdge]_]/.{v\[UndirectedEdge]u_:>u,u_\[UndirectedEdge]v:>u},PropertyValue[{g,#},"Distance"]>PropertyValue[{g,v},"Distance"]&]}]]},
PropertyValue[{g,v},"PathScore"]=score+1;PropertyValue[{g,v},"BetweennessCentrality"]+=score],{v,Most@SortBy[VertexList[g],-PropertyValue[{g,#},"Distance"]&]}],{s,VertexList[g]}]

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

scores=Table[PropertyValue[{g,v},"BetweennessCentrality"],{v,VertexList[g]}];
Plot[Count[scores,_?(#≤x&)],{x,0,Max[scores]+1},PlotRange->{0,Length[scores]},GridLines->{None,Automatic},Filling->Axis]

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

SortBy[VertexList[g],PropertyValue[{g,#},"BetweennessCentrality"]&]

Highlight the top two vertices:

HighlightGraph[g,%[[-2;;]]]

OpenersExampleSection4(Spacer1)Properties & Relations  (4)

Vertices are discovered in breadth-first order:

Reap[BreadthFirstScan[,1,
{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

Reap[BreadthFirstScan[,1,
{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

For a directed graph, the discovery follows the direction of the edges:

Reap[BreadthFirstScan[,1,
{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

Only vertices reachable from the start vertex are discovered:

g=;

ConnectedComponents[g]

Discover all vertices by picking a start vertex from each connected component:

Reap[BreadthFirstScan[g,1,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

Reap[BreadthFirstScan[g,4,{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

For a directed graph, only vertices reachable following the edge directions are discovered:

Reap[BreadthFirstScan[,4,
{"DiscoverVertex"->(Sow[#1]&)}]][[2,1]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[DepthFirstScan, paclet:ref/DepthFirstScan])  ▪  (RefLink[Graph, paclet:ref/Graph])  ▪  (RefLink[TreeGraph, paclet:ref/TreeGraph])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Programming, paclet:guide/GraphProgramming])}, {▪(RefLinkPlain[Computation on Graphs, paclet:guide/ComputationOnGraphs])}, {▪(RefLinkPlain[Graphs & Networks, paclet:guide/GraphsAndNetworks])}})}})