<< DiscreteMath`Combinatorica`
<< Graphics`Animation`

\(\(\(BFS[\ 
        x_Graph\ ]\)\(\ \)\(:=\)\(
\)\(Module[\ {data\  = \ 
            x, \ bfsList\  = \ 
            InversePermutation[BreadthFirstTraversal[\ x, \ 1\ ]\ ], \ 
          e\  = \ {}\ }, \ 
        e\  = \ BreadthFirstTraversal[data, \ 1, \ 
            Edge]; 
bfsfile\  = \ 
          Table[
Graphics[
{
Rectangle[{0, 0}, \ {1, 
                    1}, 
ShowGraph[
Highlight[\ data, 
{\ 
Take[\ e, \ 
                          Quotient[\ t, 2]\ ]\ , 
Take[
                          bfsList, \ 
                          Quotient[t, 2]\  + 
                            Mod[t, 
                              2]]
}, 
{
HighlightedVertexColors -> {Green}, 
HighlightedVertexStyle -> 
                          Disk[Normal], 
HighlightedEdgeColors -> {Red}
}
], 
PlotLabel -> "Breadth-First Search", 
TextStyle\  -> \ {FontSize\  -> \ 15, \ 
                        FontColor -> 
                          Purple}\ , 
Background -> 
                      RGBColor[1, 1, 1], 
\ 
                    Graphics]\ ], 
Text["www.combinatorica.com", \ {0.5, 
                    0.0}, \ {TextStyle -> {FontColor -> 
                          Red}}]
}, 
{\ 
                AspectRatio -> 1, \ 
                ImageSize -> 
                  350}
], 
\ {t, \ 1, \ 
              2*\((Length[bfsList])\) - 1, \ 
              1\ }]; 
bfsfile
]\)\(\ \)\)\)

\(\(\(DFS[
        x_Graph]\)\(\ \)\(:=\)\(\ \)\(Module[\ {data\  = \ x, \ 
          dfsList\  = \ DepthFirstTraversal[\ x, \ 1\ ], \ e\  = \ {}\ }, \ 
        e\  = \ DepthFirstTraversal[data, \ 1, \ 
            Edge]; 
dfsfile\  = \ 
          Table[
Graphics[
{
Rectangle[{0, 0}, \ {1, 
                    1}, 
ShowGraph[
Highlight[\ data, 
{\ 
Take[\ e, \ 
                          Quotient[\ t, 2]\ ]\ , 
Take[
                          dfsList, \ 
                          Quotient[t, 2]\  + 
                            Mod[t, 
                              2]]
}, 
{
HighlightedVertexColors -> {Green}, 
HighlightedVertexStyle -> 
                          Disk[Normal], 
HighlightedEdgeColors -> {Red}
}
], 
PlotLabel -> "Depth-First Search", 
Background -> 
                      RGBColor[1, 1, 
                        1], 
TextStyle\  -> \ {FontSize\  -> \ 15, \ FontColor -> Purple}\ , \ 
                    Graphics]\ ], 
Text["www.combinatorica.com", \ {0.5, 
                    0.0}, \ {TextStyle -> {FontColor -> 
                          Red}}]
}, 
{\ 
                AspectRatio -> 1, \ 
                ImageSize -> 
                  350}
], 
\ {t, \ 1, \ 
              2*\((Length[dfsList])\) - 1, \ 
              1\ }]; 
dfsfile
]\)\(\ \)\)\)

g1  =  DodecahedralGraph
v2  =  TranslateVertices[Vertices[g1], {0.5, 0.707}];
v3  =  TranslateVertices[Vertices[g1], {1, 0}];
g3  =  GraphUnion[3, g1];
g3  =  ChangeVertices[g3,  Join[Vertices[g1], v2, v3] ];
g3  =  AddEdges[g3, {{1, 22}, {25, 41}}];
ShowGraph[g3];

ShowAnimation[ DFS[g3]]

ShowAnimation[ BFS[g3]]