BFS DFS CONTOH
class Node:
def __init__(self,name):
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
class Edge:
def __init__(self,src,dest):
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return f"{self.src}->{self.dest}"
class Digraph:
def __init__(self):
self.edges = {}
def addNode(self,node):
if node in self.edges:
raise ValueError("Node sudah ada")
else:
self.edges[node] = []
def addEdge(self,edge):
src = edge.getSource()
dest = edge.getDestination()
if not (src in self.edges and dest in self.edges):
raise ValueError("Node tidak ada")
self.edges[src].append(dest)
def childrenOf(self,node):
return self.edges[node]
def hasNode(self,node):
return node in self.edges
def getNode(self,name):
for n in self.edges:
if n.getName() == name:
return n
raise NameError(name)
def __str__(self):
res = ""
for src in self.edges:
for dest in self.edges[src]:
res = res + f"{src}->{dest}\n"
return res[:-1] # remove last newline
#graph tidak berarah
class Graph(Digraph):
def addEdge(self,edge):
Digraph.addEdge(self,edge)
rev = Edge(edge.getDestination(),edge.getSource())
Digraph.addEdge(self,rev)
#coba panggil
def buildCityGraph():
g = Digraph()
# Create 7 nodes
for name in (
'Boston',
'Providence',
'New York',
'Chicago',
'Denver',
'Phoenix',
'Los Angeles'
):
g.addNode(Node(name))
# Create edges
g.addEdge(Edge(g.getNode('Boston'), g.getNode('Providence')))
g.addEdge(Edge(g.getNode('Boston'), g.getNode('New York')))
g.addEdge(Edge(g.getNode('Providence'), g.getNode('Boston')))
g.addEdge(Edge(g.getNode('Providence'), g.getNode('New York')))
g.addEdge(Edge(g.getNode('New York'), g.getNode('Chicago')))
g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Denver')))
g.addEdge(Edge(g.getNode('Chicago'), g.getNode('Phoenix')))
g.addEdge(Edge(g.getNode('Denver'), g.getNode('Phoenix')))
g.addEdge(Edge(g.getNode('Denver'), g.getNode('New York')))
g.addEdge(Edge(g.getNode('Los Angeles'), g.getNode('Boston')))
return g
def printPath(path):
result = ""
for i in range(len(path)):
result += str(path[i])
if i != len(path) - 1:
result += " -> "
print(result)
#DFS
def dfs(graph, start, end, toPrint=False, path=[]):
path.append(start)
if toPrint:
print("Current DFS path:", end=" ")
printPath(path)
if start == end:
return path
for nextNode in graph.childrenOf(start):
if nextNode not in path:
return dfs(graph, nextNode, end, toPrint, path)
return None
#TEST DFS
g = buildCityGraph()
start = g.getNode("Boston")
end = g.getNode("Phoenix")
result = dfs(g, start, end, toPrint=True)
if result is not None:
print("DFS path found:", end=" ")
printPath(result)
else:
print("DFS path not found")
# BFS
def bfs(graph, start, end, toPrint=False):
initPath = [start]
pathQueue = [initPath]
while len(pathQueue) != 0:
tmpPath = pathQueue.pop(0)
if toPrint:
print("Current BFS path:", end=" ")
printPath(tmpPath)
lastNode = tmpPath[-1]
if lastNode == end:
return tmpPath
for nextNode in graph.childrenOf(lastNode):
if nextNode not in tmpPath:
newPath = tmpPath + [nextNode]
pathQueue.append(newPath)
return None
# Panggil BFS
g = buildCityGraph()
start = g.getNode("Boston")
end = g.getNode("Phoenix")
result = bfs(g, start, end, toPrint=True)
if result is not None:
print("BFS path found:", end=" ")
printPath(result)
else:
print("BFS path not found")
Komentar
Posting Komentar