 CoCalc Public Filessage_worksheets / ADS_depth_first_search.ipynb
Author: Ken Levasseur
Views : 225
Compute Environment: Ubuntu 18.04 (Deprecated)

# Implementation of the Depth-First Search algorithm

We use external lists to keep track of whether a vertex has been found (array name: found) and where it was found from (array name: frm, since from is a reserved word).

We start with a random graph. The default is a random graph with 100 vertices and a probablity of any edge being present being 0.05.

In :
n=100
set_random_seed(2021)
rgraph=graphs.RandomGNP(n,0.05)
rgraph.plot(layout='circular') In :
rgraph.neighbors(source)

[49, 65, 2, 18, 83, 52, 21, 6, 86, 10, 74, 59, 60, 45, 47]

We will search for sink=95 starting at source=0.

In :
source=0
sink=95


Initialize the "found" and "from" lists:

In :
found=list(map(lambda k:False,range(n)))
found[source]=True

In :
frm=list(map(lambda k:-1,range(n)))

In :
def dfp(so,sk):
nbs=rgraph.neighbors(so)
nbsNew=filter(lambda v:not(found[v]),nbs)
if sk in nbsNew:
print('found from '+str(so))
return()
if nbsNew==[]:
return()
for v in nbsNew:
dfp(v,sk)

In :
dfp(0,95)

--------------------------------------------------------------------------- RuntimeError Traceback (most recent call last) <ipython-input-45-d7271d12febb> in <module>() ----> 1 dfp(Integer(0),Integer(95)) <ipython-input-44-a0191eded801> in dfp(so, sk) 9 return() 10 for v in nbsNew: ---> 11 dfp(v,sk) ... last 1 frames repeated, from the frame below ... <ipython-input-44-a0191eded801> in dfp(so, sk) 9 return() 10 for v in nbsNew: ---> 11 dfp(v,sk) RuntimeError: maximum recursion depth exceeded while calling a Python object 
In :
def path_to(v):
if found[v]:
S=[]
k=v
while frm[k]!=source:
S.append(k)
k=frm[k]
S.append(k)
S.append(source)
return(S)
else:
return  []

In :
path_to(sink)

[95, 32, 6, 80, 44, 0]

We can use the function to find other vertices.

In :
path_to(30)

[30, 44, 0]

Not every vertex can be reached:

In :
path_to(31)

not?

7 in range(10)

The