キン〇マハムスター佐藤  2021/03/28更新

Python グラフ理論を扱うときのベースになるクラス


グラフ理論を扱うときのベースになるクラス テストコード付き

クラスの中のbfsメソッドは探索して成功か失敗を返します。bfs2メソッドは探索経路をリスト型で返します。dfs,dfs2も同じ。

これがあれば関係図や経路探索の課題は解けるんじゃないでしょうか



class Graph():
	def __init__(self):
		self.adjacencyList={}

	#ノート追加
	def addVertext(self ,v):
		if self.adjacencyList.get(v) == None:
			self.adjacencyList[v] = []

	#無向グラフ
	def addEdge(self ,v1,v2):
		self.adjacencyList[v1].append(v2)
		self.adjacencyList[v2].append(v1)
	def removeEdge(self,v1, v2):
		self.adjacencyList[v1].remove(v2)
		self.adjacencyList[v2].remove(v1)

	#有向グラフ
	def addEdgeDirected(self ,v1,v2):
		self.adjacencyList[v1].append(v2)
	def removeEdgeDirected(self,v1, v2):
		self.adjacencyList[v1].remove(v2)
	
	def disp(self):
	    print(self.adjacencyList)

    #幅優先探索
	def bfs(self,start,goal):
		#start スタート goal ゴール
		que = [start]
		visited = set()
		currendVertex=''
		visited.add(start)
		while len(que)>0 :
			currentVertex = que.pop()
			for vertex in self.adjacencyList[currentVertex]:
				print(currentVertex,vertex,visited)
				if vertex == goal:
					visited.add(vertex)
					return True
				if (vertex in visited)==False:
					visited.add(vertex)
					que.insert(0,vertex)

		return False

    #幅優先探索
	def bfs2(self,start,goal):
		#start スタート goal ゴール
		que = [start]
		visited = []
		currendVertex=''
		visited.append(start)
		while len(que)>0 :
			currentVertex = que.pop()
			for vertex in self.adjacencyList[currentVertex]:
				#print(currentVertex,vertex,visited)
				if vertex == goal:
					visited.append(vertex)
					que=[]
					break
				if (vertex in visited)==False:
					visited.append(vertex)
					que.insert(0,vertex)

		return visited

    #深さ優先探索
	def dfs(self,start,goal):
		#start スタート goal ゴール
		que = [start]
		visited = set()
		currendVertex=''
		visited.add(start)
		while len(que)>0 :
			currentVertex = que.pop()
			for vertex in self.adjacencyList[currentVertex]:
				if vertex == goal:
					visited.add(vertex)
					return True
				if (vertex in visited)==False:
					visited.add(vertex)
					que.append(vertex)

		return False
    #深さ優先探索
	def dfs2(self,start,goal):
		#start スタート goal ゴール
		que = [start]
		visited = []
		currendVertex=''
		visited.append(start)
		while len(que)>0 :
			currentVertex = que.pop()
			for vertex in self.adjacencyList[currentVertex]:
				if vertex == goal:
					visited.append(vertex)
					que=[]
					break
				if (vertex in visited)==False:
					visited.append(vertex)
					que.append(vertex)

		return visited
#テストコード
a = Graph()
a.addVertext('a')
a.addVertext('b')
a.addVertext('c')
a.addVertext('d')
a.addVertext('f')
a.addEdge('a','b')
a.addEdge('a','c')
a.addEdge('c','d')
a.addEdge('d','f')
a.disp()

b = a.dfs2('a','f')
print(b)



タイトルとURLをコピーしました