Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 479
License: OTHER
Tweet
Share
Share
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