# Question:How to get a DFS spanning tree?

## Question:How to get a DFS spanning tree?

Maple 2021

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. see  https://en.wikipedia.org/wiki/Depth-first_search

Here I write a  DFS function in maple  language according to the principle of  BFS algorithm.

Pseudo codes:

```procedure DFS_iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)```

Maple DFS codes:

DFS:=proc(g::Graph,x)
local  s,seen,vertex,nodes,w,vertexlist;
s := stack[new]():
stack[push](x, s):
seen :=[x]:
vertexlist:= []:
while not stack[empty](s) do
vertex:=stack[pop](s):
vertexlist:= [op(vertexlist),vertex]:
nodes:= Neighborhood(g, vertex):
for w in nodes do
if not evalb(w in seen) then:
stack[push](w, s):
seen :=[op(seen),w]:
end if:
end do:
end do:
return  vertexlist
end proc:
with(GraphTheory):with(SpecialGraphs):
P := PetersenGraph():
DrawGraph(P);
DFS(P,1)

[1, 6, 10, 9, 8, 4, 3, 7, 5, 2]

The result of a depth-first search of a graph can be conveniently described in terms of a spanning tree of the vertices reached during the search.

But I haven't figured out how to improve the  above codes to get this DFS spanning tree.

PS: The stack seems to be deprecated in maple2021.

As another way to search BFS algorithm, Carl Love  provided an example of the application of BFS algorithm.

I also wrote a BFS code implementation based on the queue as follows.

BFS:=proc(g::Graph,x)
local  s,seen,vertex,nodes,w,vertexlist;
s:= SimpleQueue():
s:-enqueue(x):
seen :=[x]:
vertexlist:= []:
while not s:-empty() do
vertex:=s:-dequeue():
vertexlist:= [op(vertexlist),vertex]:
nodes:= Neighborhood(g, vertex):
for w in nodes do
if not evalb(w in seen) then:
s:-enqueue(w):
seen :=[op(seen),w]:
end if:
end do:
end do:
return  vertexlist
end proc:
BFS(P,1)

[1, 2, 5, 6, 3, 9, 4, 8, 7, 10]

﻿