class StackX:
def __init__(self):
self.st = [] # make array
self.top = -1
def push(self,j): # put item on stack
self.top += 1
self.st.append(j)
def pop(self): # take item off stack
self.top -= 1
return self.st.pop()
def peek(self): # peek at top of stack
return self.st[self.top]
def isEmpty(self): # true if nothing on stack-
return self.top == -1
class Vertex:
def __init__(self,lab): # constructor
self.label = lab
self.wasVisited = False
class Graph:
def __init__(self):
self.vertexList = [] # adjacency matrix
self.adjMat = []
self.nVerts = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(0)
self.adjMat.append(l)
self.theStack = StackX()
def addVertex(self,lab):
self.vertexList.append( Vertex(lab))
self.nVerts += 1
def addEdge(self,start, end):
self.adjMat[start][end] = 1
self.adjMat[end][start] = 1
def displayVertex(self,v):
print self.vertexList[v].label ,
def dfs(self): # depth-first search # begin at vertex 0
self.vertexList[0].wasVisited = True # mark it
self.displayVertex(0) # display it
self.theStack.push(0) # push it
while( not self.theStack.isEmpty() ): # until stack empty,
# get an unvisited vertex adjacent to stack top
v = self.getAdjUnvisitedVertex( self.theStack.peek() )
if(v == -1): # if no such vertex,
self.theStack.pop()
else: # if it exists,
self.vertexList[v].wasVisited = True # mark it
self.displayVertex(v) # display it
self.theStack.push(v) # push it
# stack is empty, so we're done
for j in range(self.nVerts): # reset flags
self.vertexList[j].wasVisited = False # end dfs
def getAdjUnvisitedVertex(self,v):
for j in range(self.nVerts):
if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):
return j
return -1
theGraph = Graph()
theGraph.addVertex('A') # 0 (start for dfs)
theGraph.addVertex('B') # 1
theGraph.addVertex('C') # 2
theGraph.addVertex('D') # 3
theGraph.addVertex('E') # 4
theGraph.addEdge(0,1)
theGraph.addEdge(1,2)
theGraph.addEdge(0,3)
theGraph.addEdge(3,4)
print 'Visits: ',
theGraph.dfs() # depth-first search
class Queue:
def __init__(self): # constructor
self.SIZE = 20
self.queArray = []
for i in range(20):
self.queArray.append(0)
self.front = 0
self.rear = -1
def insert(self,j): # put item at self.rear of queue
if(self.rear == self.SIZE-1):
self.rear = -1
self.rear += 1
self.queArray[self.rear] = j
def remove(self): # take item from front of queue
temp = self.queArray[self.front]
self.front += 1
if(self.front == self.SIZE):
self.front = 0
return temp
def isEmpty(self): # true if queue is empty
return ( self.rear+1==self.front or (self.front+self.SIZE-1==self.rear) )
class Vertex:
def __init__(self,lab): # constructor
self.label = lab
self.wasVisited = False
class Graph:
def __init__(self):
self.vertexList = [] # adjacency matrix
self.adjMat = []
self.nVerts = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(0)
self.adjMat.append(l)
self.theQueue = Queue()
def addVertex(self,lab):
self.vertexList.append( Vertex(lab))
self.nVerts += 1
def addEdge(self,start, end):
self.adjMat[start][end] = 1
self.adjMat[end][start] = 1
def displayVertex(self,v):
print self.vertexList[v].label ,
def bfs(self): # breadth-first search
# begin at vertex 0
self.vertexList[0].wasVisited = True # mark it
self.displayVertex(0) # display it
self.theQueue.insert(0) # insert at tail
while( not self.theQueue.isEmpty() ): # until queue empty,
v1 = self.theQueue.remove() # remove vertex at head
# until it has no unvisited neighbors
while( self.getAdjUnvisitedVertex(v1) != -1 ):
v2 = self.getAdjUnvisitedVertex(v1)
self.vertexList[v2].wasVisited = True # mark it
self.displayVertex(v2) # display it
self.theQueue.insert(v2) # insert it
for j in range(self.nVerts): # reset flags
self.vertexList[j].wasVisited = False
def getAdjUnvisitedVertex(self,v):
for j in range(self.nVerts):
if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):
return j
return -1
theGraph = Graph()
theGraph.addVertex('A') # 0 (start for dfs)
theGraph.addVertex('B') # 1
theGraph.addVertex('C') # 2
theGraph.addVertex('D') # 3
theGraph.addVertex('E') # 4
theGraph.addEdge(0,1)
theGraph.addEdge(1,2)
theGraph.addEdge(0,3)
theGraph.addEdge(3,4)
print 'Visits: ',
theGraph.bfs() # breadth-first search
class StackX:
def __init__(self):
self.st = [] # make array
self.top = -1
def push(self,j): # put item on stack
self.top += 1
self.st.append(j)
def pop(self): # take item off stack
self.top -= 1
return self.st.pop()
def peek(self): # peek at top of stack
return self.st[self.top]
def isEmpty(self): # true if nothing on stack-
return self.top == -1
class Vertex:
def __init__(self,lab): # constructor
self.label = lab
self.wasVisited = False
class Graph:
def __init__(self):
self.vertexList = [] # adjacency matrix
self.adjMat = []
self.nVerts = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(0)
self.adjMat.append(l)
self.theStack = StackX()
def addVertex(self,lab):
self.vertexList.append( Vertex(lab))
self.nVerts += 1
def addEdge(self,start, end):
self.adjMat[start][end] = 1
self.adjMat[end][start] = 1
def displayVertex(self,v):
print self.vertexList[v].label ,
def mst(self): # minimum spanning tree (depth first)
# start at 0
self.vertexList[0].wasVisited =True
# mark it
self.theStack.push(0)
# push it
while(not self.theStack.isEmpty() ):
# until stack empty
# get stack top
currentVertex = self.theStack.peek()
# get next unvisited neighbor
v = self.getAdjUnvisitedVertex(currentVertex)
if(v == -1):
# if no more neighbors
self.theStack.pop()
else:
# got a neighbor
self.vertexList[v].wasVisited = True # mark it
self.theStack.push(v)
# push it
# display edge
self.displayVertex(currentVertex)
# from currentV
self.displayVertex(v)
# to v
print ' ',
for j in range(self.nVerts):
# reset flags
self.vertexList[j].wasVisited = False
def getAdjUnvisitedVertex(self, v):
for j in range(self.nVerts):
if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):
return j
return -1
theGraph = Graph()
theGraph.addVertex('A') # 0 (start for mst)
theGraph.addVertex('B') # 1
theGraph.addVertex('C') # 2
theGraph.addVertex('D') # 3Topological Sorting with Directed Graphs
theGraph.addVertex('E') # 4
theGraph.addEdge(0,1)
theGraph.addEdge(0,2)
theGraph.addEdge(0,3)
theGraph.addEdge(0,4)
theGraph.addEdge(1,2)
theGraph.addEdge(1,3)
theGraph.addEdge(1,4)
theGraph.addEdge(2,3)
theGraph.addEdge(2,4)
theGraph.addEdge(3,4)
print 'Minimum spanning tree: ',
theGraph.mst() # minimum spanning tree
class Vertex:
def __init__(self,lab): # constructor
self.label = lab
self.wasVisited = False
class Graph:
def __init__(self):
self.vertexList = [] # adjacency matrix
self.adjMat = []
self.nVerts = 0
for j in range(20): # set adjacency
l = []
for k in range(20):
l.append(0)
self.adjMat.append(l)
def addVertex(self,lab):
self.vertexList.append( Vertex(lab))
self.nVerts += 1
def addEdge(self,start, end):
self.adjMat[start][end] = 1
self.adjMat[end][start] = 1
def displayVertex(self,v):
print self.vertexList[v].label ,
def topo(self): # topological sort
orig_nVerts = self.nVerts # remember how many verts
while(self.nVerts > 0): # while vertices remain,
# get a vertex with no successors, or -1
currentVertex = self.noSuccessors()
if(currentVertex == -1):
# must be a cycleTopological Sorting with Directed Graphs
print 'ERROR: Graph has cycles'
return
# insert vertex label in sorted array (start at end)
self.sortedArray[nVerts-1] = self.vertexList[currentVertex].label
self.deleteVertex(currentVertex)
print 'Topologically sorted order: '
for j in range(orig_nVerts):
print sortedArray[j] ,
print ''
def noSuccessors(self): # returns vert with no successors
# (or -1 if no such verts)
isEdge = None
for row in range(self.nVerts): # for each vertex,
isEdge = False
# check edges
for col in range(self.nVerts):
if( self.adjMat[row][col] > 0 ): # if edge to
# another,
isEdge = True
break
if( not isEdge ):
# if no edges,
return row
return -1
def deleteVertex(self,delVert):
if(delVert != self.nVerts-1):
# if not last vertex,
# delete from vertexList
for j in range(self.nVerts-1):
self.vertexList[j] = self.vertexList[j+1]
# delete row from adjMat
for row in range(self.nVerts-1):
self.moveRowUp(row, nVerts)
# delete col from adjMat
for col in range(self.nVerts-1):
self.moveColLeft(col, nVerts-1)
self.nVerts -= 1
def moveRowUp(self,row,length):
for col in range(length):
self.adjMat[row][col] = self.adjMat[row+1][col]
def moveColLeft(self,col, length):
for row in range(self.length):
self.adjMat[row][col] = self.adjMat[row][col+1]
theGraph = Graph()
theGraph.addVertex('A') # 0
theGraph.addVertex('B') # 1
theGraph.addVertex('C') # 2
theGraph.addVertex('D') # 3
theGraph.addVertex('E') # 4
theGraph.addVertex('F') # 5
theGraph.addVertex('G') # 6
theGraph.addVertex('H') # 7Connectivity in Directed Graphs
theGraph.addEdge(0,3)
theGraph.addEdge(0,4)
theGraph.addEdge(1,4)
theGraph.addEdge(2,5)
theGraph.addEdge(3,6)
theGraph.addEdge(4,6)
theGraph.addEdge(5,7)
theGraph.addEdge(6,7)
theGraph.topo() # do the sort