CoCalc Public Filessage_worksheets / ADS_depth_first_search.ipynb
Author: Ken Levasseur
Views : 225
License: Other -- explicitly state in your code
Compute Environment: Ubuntu 18.04 (Deprecated)

Implementation of the Depth-First Search algorithm

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

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 [16]:
n=100
set_random_seed(2021)
rgraph=graphs.RandomGNP(n,0.05)
rgraph.plot(layout='circular')

In [28]:
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 [18]:
source=0
sink=95


Initialize the "found" and "from" lists:

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

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

In [44]:
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==[]:
print('not found')
return()
for v in nbsNew:
dfp(v,sk)

In [45]:
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 [12]:
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:
print(str(v)+' not found from '+str(source))
return  []

In [75]:
path_to(sink)

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

We can use the function to find other vertices.

In [71]:
path_to(30)

[30, 44, 0]

Not every vertex can be reached:

In [74]:
path_to(31)

31 not found from 0
[]
In [ ]:
not?

O

In [35]:
7 in range(10)

True
In [ ]:
The