Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 454
License: OTHER
Kernel: SageMath (stable)

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.

n=100 set_random_seed(2021) rgraph=graphs.RandomGNP(n,0.05) rgraph.plot(layout='circular')
Image in a Jupyter notebook
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.

source=0 sink=95

Initialize the "found" and "from" lists:

found=list(map(lambda k:False,range(n))) found[source]=True
frm=list(map(lambda k:-1,range(n)))
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)
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
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 []
path_to(sink)
[95, 32, 6, 80, 44, 0]

We can use the function to find other vertices.

path_to(30)
[30, 44, 0]

Not every vertex can be reached:

path_to(31)
31 not found from 0
[]
not? O
7 in range(10)
True
The