This post will be mostly code. Please use proper indenting cuz Python otherwise will make your life hell. If you’re using Sublime go to, set Convert Indentation to tabs.

Gist : I have used the collections.defaultdict dict DT for implementing a dict of sets.

Vertices have been stored as adjacency list kind of elements as a dictionary. The code is raw and may have errors ( though no compilation error as of the post’s writing). Please comment for additional details. This is purely for testing purposes.

A Graph.

from collections import defaultdict
#The Graph will be a dictionary of sets

class Graph():

def __init__(self, connections, directed = False):

self.graph = defaultdict(set)

self.directed = directed

self.add_connections (connections)

def add_connections(self, connections):

for node1,node2 in connections:

self.add_connection(node1,node2)

def add_connection(self, node1, node2):

self.graph[node1].add(node2)

if not self.directed:

self.graph[node2].add(node1)

def remove(self, node):

#removes all references to the node

#Use iteritems for dict items like k,v in dictname.iteritems():

for n,cons in self.graph.iteritems():

try:

#Removing from a set involves setname.remove(element)

cons.remove(node)

except KeyError:

pass

try:

#Removing from a dictionary involves rem dict_element_name

del self.graph[node]

except KeyError:

pass

def isconnected(self, node1, node2):

if node1 in self.graph[node2] or node2 in self.graph[node1]:

return True

return False

def dfs(self,start):

#If start node does not exist, return None (search is futile)

if start not in self.graph:

return None

#Start with an empty set

visited = set()

#To return unse ( which is not a set

unset = []

#Initially fill stack with start vertex

stack = [start]

#While stack is not empty keep repeating this algorithms

while stack:

#Take the first element of stack (pop means last inserted , aggressive)

vertex = stack.pop()

#If vertex has not been visited yet, add it to visited and look for all the element in graph[vertex]

if vertex not in visited:

visited.update(vertex)

unset.append(vertex)

stack.extend(self.graph[vertex] - visited)

return unset

def bfs(self, start):

if start not in self.graph:

return None

visited = set()

queue = [start]

unset = []

while queue:

vertex = queue.pop(0)

if vertex not in visited:

visited.update(vertex)

unset.append(vertex)

queue.extend(self.graph[vertex] - visited)

return unset

#Should work but not tested

def findpath(self,v1, v2):

m = bfs(v1)

if v2 in m:

return m[:m.index(v2)+1]

return None