FilesExpand file tree

 all-permutations

/

depth_first_search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

66 lines (53 loc) · 1.64 KB

 all-permutations

/

depth_first_search.py

Top

File metadata and controls

• Code
• Blame

66 lines (53 loc) · 1.64 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

#!/usr/bin/python

# encoding=utf8

""" Author: OMKAR PATHAK """

from __future__ import print_function

class Graph():

def __init__(self):

self.vertex = {}

# for printing the Graph vertexes

def printGraph(self):

print(self.vertex)

for i in self.vertex.keys():

print(i,' -> ', ' -> '.join([str(j) for j in self.vertex[i]]))

# for adding the edge beween two vertexes

def addEdge(self, fromVertex, toVertex):

# check if vertex is already present,

if fromVertex in self.vertex.keys():

self.vertex[fromVertex].append(toVertex)

else:

# else make a new vertex

self.vertex[fromVertex] = [toVertex]

def DFS(self):

# visited array for storing already visited nodes

visited = [False] * len(self.vertex)

# call the recursive helper function

for i in range(len(self.vertex)):

if visited[i] == False:

self.DFSRec(i, visited)

def DFSRec(self, startVertex, visited):

# mark start vertex as visited

visited[startVertex] = True

print(startVertex, end = ' ')

# Recur for all the vertexes that are adjacent to this node

for i in self.vertex.keys():

if visited[i] == False:

self.DFSRec(i, visited)

if __name__ == '__main__':

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

g.printGraph()

print('DFS:')

g.DFS()

# OUTPUT:

# 0  ->  1 -> 2

# 1  ->  2

# 2  ->  0 -> 3

# 3  ->  3

# DFS:

# 0 1 2 3