Created
August 13, 2019 17:08
-
-
Save Biostate/4359bb7b347fcf8fe088283d6cd55406 to your computer and use it in GitHub Desktop.
Problem Solved with Adjacency List Representation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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