Advanced Search

Question: How to get a DFS spanning tree?

Question:How to get a DFS spanning tree?

lcz 1009 Maple 2021
graphtheory
February 01 2022
4

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]

 
Please Wait...