CoCalc Public Filessage_worksheets / ADS_depth_first_search.ipynbOpen with one click!
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