파이썬에서 그래프(Graph) 구현하기

 

이번 포스팅에서는 그래프(Graph) 자료구조 포스팅(https://junwha0511.blog.me/221698233962)에 이어 

그래프를 파이썬에서 구현해보는 포스팅을 하겠습니다.

 

 

그래프(Graph) 자료구조란?

Graph는 정점(Vertex, 혹은 Node)과정점들을 연결하는 간선(Edge)으로 이루어진 자료구조입니다.​

 

 

 

그래프 구조는 파이썬에서 딕셔너리 자료형(https://junwha0511.blog.me/221698243080)으로 구현할 수 있습니다.

 

바로 이중 딕셔너리를 사용하는 방법인데요,

예를 들어 A, B 정점이 있고 가중치가 5인 간선으로 이어져 있다면

 

weight = {'A':{'B':5}, 'B':{'A':5}}

 

위와 같이 A와 B의 상호 관계를 이중 딕셔너리를 사용해 표현할 수 있습니다.

 

하나하나 관계를 입력하는 것은 매우 시간이 오래 걸리는 작업이기 때문에

 

아래와 같이 'A-B=3'과 같은 형식으로 입력을 자동화하는 코드를 구현하였습니다.

weight = {'A':{}, 'Z':{}}
flag={'A':True, 'Z':False}
dist={'A':0, 'Z':float('inf')}
route=['Z']
ptd='Z'

print('input Graph(like A-B=1, but always A is start node and Z is destination)')
print('if you like to stop, input END')
while True:
	while True:
		line = input()
		if line == 'END':
			break
		else:
			node1 = line[line.index('-')-1]
			node2 = line[line.index('-')+1]
			weightValue = int(line[line.index('=')+1:])
			if not (node1 in weight):
				weight[node1] = {}
				flag[node1] = False
				dist[node1] = float('inf')
			if not (node2 in weight):
				weight[node2] = {}
				flag[node2] = False
				dist[node2] = float('inf')
			weight[node1][node2] = weightValue
			weight[node2][node1] = weightValue		
	print('Below is your graph, you like to stop? [Y/N]')
	print(weight)
	print(flag)
	print(dist)
	isYes = input()
	if isYes=='Y':
		break

while not flag['Z']:
	nextDist=float('inf')
	nextNode=None
	for key in flag.keys():
		if flag[key]:
			for node in weight[key]:
				if not flag[node]:
					cDist=dist[key]+weight[key][node]
					if cDist<nextDist:
						nextNode=node
						nextDist=cDist
	dist[nextNode]=nextDist
	flag[nextNode]=True


while flag['A']:
	for node in weight[ptd]:
		if (dist[ptd]-weight[ptd][node])==dist[node]:
			route.insert(0,node)
			flag[node]=False
			ptd=node
			break	
print(dist['Z'])
print(route)

 

 

사용자가 텍스트를 입력하면, '-'를 기준으로 node1과 node2로 구분하고, '=' 뒤의 숫자를 모두 파싱합니다.

END를 입력하면 현재 그래프 구조를 보여준 뒤 Y 혹은 N을 눌러 다음 단계를 진행할 수 있습니다.