Question

Python3 question.

Suppose I have a undirect and unweighted graph with vertex list type, here is the code of the graph.

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

I want to use this to create a DFS method. How can I use stack only to finish the work?

Answer 1

CODE

def DFS(graph, start):

visited = {}

for v in graph:

visited[v] = False

stack = []

stack.append(start)

while (len(stack)):

start = stack[-1]

stack.pop()

if (not visited[start]):

print(start, end=' ')

visited[start] = True

for node in graph[start]:

if (not visited[node]):

stack.append(node)

graph = { "a" : ["c"],

"b" : ["c", "e"],

"c" : ["a", "b", "d", "e"],

"d" : ["c"],

"e" : ["c", "b"],

"f" : []

}

start = 'a'

DFS(graph, start)