Skip to content

Instantly share code, notes, and snippets.

@Biostate
Created August 13, 2019 17:08
Show Gist options
  • Save Biostate/4359bb7b347fcf8fe088283d6cd55406 to your computer and use it in GitHub Desktop.
Save Biostate/4359bb7b347fcf8fe088283d6cd55406 to your computer and use it in GitHub Desktop.
Problem Solved with Adjacency List Representation
class Stack:
def __init__(self):
self.nodes = []
def pop(self):
return self.nodes.pop()
def push(self,x):
self.nodes.append(x)
def DFS(x):
stack.push(x)
visiteds.append(x)
for i in nod[x]:
if i not in visiteds:
path[i] = x
DFS(i)
stack.pop()
stack = Stack()
nod = [
[1,2],
[0,3,6],
[0,5],
[1],
[6],
[2,6,7],
[1,4,5,7],
[5,6]
]
visiteds = [] # Stores visiteds
path = [None] * len(nod) # Stores path
DFS(5)
print(visiteds, path)
# If you want to run some examples in the code you can use the link on the bottom.
# The website generates random BFS graphs. Just modify Adjacency table in "nod" array.
# https://www.cs.usfca.edu/~galles/visualization/DFS.html
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment