'''graph traversal basic algorithm, show order with indentation.
To do something, starting and ending processing of a vertex indicated.'''
from DFS import driver, numToChar
def DFSSweepIndent(g):
'''Show stack of visits.
g[1:] is a list containing lists of adjacent nodes,
g[0] used for directedness and vertex names.
'''
lim = len(g)
visited = [False]*lim # ignore index 0 as in g
for i in range(1, lim):
if not visited[i]:
dfs(g, visited, i, 0)
def dfs(g, visited, v, lev):
'''g is a list of lists of adjacent nodes.
visited is a list showing which nodes are visited so far,
v is the starting vertex index >= 1, for the search
lev gives the recursion/indentation amount.
'''
visited[v] = True
print(lev*' '+"visiting ", numToChar(v, g)) # or other first visit code
for w in g[v]:
if not visited[w]:
dfs(g, visited, w, lev+1)
# optional code for after child finished processing
print(lev*' '+"finishing", numToChar(v, g)) # or other vertex completion processing
if __name__ == '__main__':
driver(DFSSweepIndent, 'A:BCF B:ACD C:ABDF D:BC E:G F:AC G:E')