Yesterday, user @lcz , while responding as a third party to one of my Answers regarding GraphTheory, asked about breadth-first search. So, I decided to write a more-interesting example of it than the relatively simple example that was used in that Answer. I think that this is general enough to be worthy of a Post.

This application generates all maximal paths in a graph that begin with a given vertex. (I'm calling a path maximal if it cannot be extended and remain a path.) This code requires Maple 2019 or later and 1D input. This works for both directed and undirected graphs. Weights, if present. are ignored.

restart:

AllMaximalPaths:= proc(G::GRAPHLN, v)
description 
    "All maximal paths of G starting at v by breadth-first search"
;
option `Author: Carl Love <carl.j.love@gmail.com> 2021-Mar-17`;
uses GT= GraphTheory;
local 
    P:= [rtable([v])], R:= rtable(1..0),
    VL:= GT:-Vertices(G), V:= table(VL=~ [$1..nops(VL)]),
    Departures:= {op}~(GT:-Departures(G))
;
    while nops(P) <> 0 do
        P:= [
            for local p in P do
                local New:= Departures[V[p[-1]]] minus {seq}(p);
                if New={} then R,= [seq](p); next fi;                
                (
                    for local u in New do 
                        local p1:= rtable(p); p1,= u
                    od
                )       
            od
        ]
    od;
    {seq}(R)  
end proc
:
#large example:
GT:= GraphTheory:
K9:= GT:-CompleteGraph(9):
Pa:= CodeTools:-Usage(AllMaximalPaths(K9,1)):
memory used=212.56MiB, alloc change=32.00MiB, 
cpu time=937.00ms, real time=804.00ms, gc time=312.50ms

nops(Pa);
                             40320
#fun example:
P:= GT:-SpecialGraphs:-PetersenGraph():
Pa:= CodeTools:-Usage(AllMaximalPaths(P,1)):
memory used=0.52MiB, alloc change=0 bytes, 
cpu time=0ns, real time=3.00ms, gc time=0ns

nops(Pa);
                               72

Pa[..9]; #sample paths
    {[1, 2, 3, 4, 10, 9, 8, 5], [1, 2, 3, 7, 8, 9, 10, 6], 
      [1, 2, 9, 8, 7, 3, 4, 5], [1, 2, 9, 10, 4, 3, 7, 6], 
      [1, 5, 4, 3, 7, 8, 9, 2], [1, 5, 4, 10, 9, 8, 7, 6], 
      [1, 5, 8, 7, 3, 4, 10, 6], [1, 5, 8, 9, 10, 4, 3, 2], 
      [1, 6, 7, 3, 4, 10, 9, 2]}

Notes on the procedure:

The two dynamic data structures are

• P: a list of vectors of vertices. Each vector contains a path which we'll attempt to extend.
• R: a vector of lists of vertices. Each list is a maximal path to be returned.

The static data structures are

• V: a table mapping vertices (which may be named) to their index numbers.
• Departures: a list of sets of vertices whose k^th set is the possible next vertices from vertex number k.

On each iteration of the outer loop, P is completely reconstructed because each of its entries, a path p, is either determined to be maximal or it's extended. The set New is the vertices that can be appended to the p (connected to vertex p[-1]). If New is empty, then p is maximal, and it gets moved to R. 

The following code constructs an array plot of all the maximal paths in the Petersen graph. I can't post the array plot, but you can see it in the attached worksheet: BreadthFirst.mw

#Do an array plot of each path embedded in the graph:
n:= nops(Pa):
c:= 9: 
plots:-display(
    (PA:= rtable(
        (1..ceil(n/c), 1..c),
        (i,j)-> 
            if (local k:= (i-1)*ceil(n/c) + j) > n then 
                plot(axes= none)
            else 
                GT:-DrawGraph(
                    GT:-HighlightTrail(P, Pa[k], inplace= false), 
                    stylesheet= "legacy", title= typeset(Pa[k])
                )
            fi
    )),
    titlefont= [Times, Bold, 12]
);

#And recast that as an animation so that I can post it:
plots:-display(
    [seq](`$`~(plots:-display~(PA), 5)),
    insequence
);