Ch09 Lab - 그래프

📘 교재 예제 (Code)

📘 Textbook Examples (Code)

Code09-01.py

인접 행렬로 무방향 그래프를 표현합니다

## 함수 선언 부분 ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [ [0 for _ in range(size)] for _ in range(size) ]

## 전역 변수 선언 부분 ##
G1, G3 = None, None

## 메인 코드 부분 ##

G1 = Graph(4)
G1.graph[0][1] = 1; G1.graph[0][2] = 1; G1.graph[0][3] = 1
G1.graph[1][0] = 1; G1.graph[1][2] = 1
G1.graph[2][0] = 1; G1.graph[2][1] = 1; G1.graph[2][3] = 1
G1.graph[3][0] = 1; G1.graph[3][2] = 1

print('## G1 무방향 그래프 ##')
for row in range(4) :
	for col in range(4) :
		print(G1.graph[row][col], end=' ')
	print()

G3 = Graph(4)
G3.graph[0][1] = 1; G3.graph[0][2] = 1
G3.graph[3][0] = 1; G3.graph[3][2] = 1

print('## G3 방향 그래프 ##')
for row in range(4) :
	for col in range(4) :
		print(G3.graph[row][col], end=' ')
	print()

Code09-01.py

Represents an undirected graph using an adjacency matrix

## Function Declarations ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [ [0 for _ in range(size)] for _ in range(size) ]

## Global Variables ##
G1, G3 = None, None

## Main Code ##
G1 = Graph(4)
G1.graph[0][1] = 1; G1.graph[0][2] = 1; G1.graph[0][3] = 1
G1.graph[1][0] = 1; G1.graph[1][2] = 1
G1.graph[2][0] = 1; G1.graph[2][1] = 1; G1.graph[2][3] = 1
G1.graph[3][0] = 1; G1.graph[3][2] = 1

print('## G1 Undirected Graph ##')
for row in range(4) :
	for col in range(4) :
		print(G1.graph[row][col], end=' ')
	print()

G3 = Graph(4)
G3.graph[0][1] = 1; G3.graph[0][2] = 1
G3.graph[3][0] = 1; G3.graph[3][2] = 1

print('## G3 Directed Graph ##')
for row in range(4) :
	for col in range(4) :
		print(G3.graph[row][col], end=' ')
	print()

Code09-02.py

인접 행렬로 방향 그래프를 표현합니다

## 함수 선언 부분 ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print(' ', end = ' ')
	for v in range(g.SIZE) :
		print(nameAry[v], end = ' ')
	print()
	for row in range(g.SIZE) :
		print(nameAry[row], end = ' ')
		for col in range(g.SIZE) :
			print(g.graph[row][col], end= '  ')
		print()
	print()

## 전역 변수 선언 부분 ##
G1 = None
nameAry = ['문별', '솔라', '휘인', '쯔위', '선미', '화사']
문별, 솔라, 휘인, 쯔위, 선미, 화사 = 0, 1, 2, 3, 4, 5


## 메인 코드 부분 ##

gSize = 6
G1 = Graph(gSize)
G1.graph[문별][솔라] = 1; G1.graph[문별][휘인] = 1
G1.graph[솔라][문별] = 1; G1.graph[솔라][쯔위] = 1
G1.graph[휘인][문별] = 1; G1.graph[휘인][쯔위] = 1
G1.graph[쯔위][솔라] = 1; G1.graph[쯔위][휘인] = 1; G1.graph[쯔위][선미] = 1; G1.graph[쯔위][화사] = 1
G1.graph[선미][쯔위] = 1; G1.graph[선미][화사] = 1
G1.graph[화사][쯔위] = 1; G1.graph[화사][선미] = 1

print('## G1 무방향 그래프 ##')
printGraph(G1)

Code09-02.py

Represents a directed graph using an adjacency matrix

## Function Declarations ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print(' ', end = ' ')
	for v in range(g.SIZE) :
		print(nameAry[v], end = ' ')
	print()
	for row in range(g.SIZE) :
		print(nameAry[row], end = ' ')
		for col in range(g.SIZE) :
			print(g.graph[row][col], end= '  ')
		print()
	print()

## Global Variables ##
G1 = None
nameAry = ['Moonbyul', 'Solar', 'Wheein', 'Tzuyu', 'Sunmi', 'Hwasa']
Moonbyul, Solar, Wheein, Tzuyu, Sunmi, Hwasa = 0, 1, 2, 3, 4, 5


## Main Code ##
gSize = 6
G1 = Graph(gSize)
G1.graph[Moonbyul][Solar] = 1; G1.graph[Moonbyul][Wheein] = 1
G1.graph[Solar][Moonbyul] = 1; G1.graph[Solar][Tzuyu] = 1
G1.graph[Wheein][Moonbyul] = 1; G1.graph[Wheein][Tzuyu] = 1
G1.graph[Tzuyu][Solar] = 1; G1.graph[Tzuyu][Wheein] = 1; G1.graph[Tzuyu][Sunmi] = 1; G1.graph[Tzuyu][Hwasa] = 1
G1.graph[Sunmi][Tzuyu] = 1; G1.graph[Sunmi][Hwasa] = 1
G1.graph[Hwasa][Tzuyu] = 1; G1.graph[Hwasa][Sunmi] = 1

print('## G1 Undirected Graph ##')
printGraph(G1)

Code09-03_.py

가중치 그래프를 인접 행렬로 표현합니다

## 클래스 및 함수 선언 부분 ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

## 전역 변수 선언 부분 ##
G1 = None
stack = []
visitedAry = []		# 방문한 정점

## 메인 코드 부분 ##

G1 = Graph(4)
G1.graph[0][2] = 1; G1.graph[0][3] = 1
G1.graph[1][2] = 1
G1.graph[2][0] = 1; G1.graph[2][1] = 1; G1.graph[2][3] = 1
G1.graph[3][0] = 1; G1.graph[3][2] = 1

print('## G1 무방향 그래프 ##')
for row in range(4) :
	for col in range(4) :
		print(G1.graph[row][col], end = ' ')
	print()

current = 0		# 시작 정점 A
stack.append(current)
visitedAry.append(current)

while (len(stack) != 0) :
	next = None
	for vertex in range(4) :
		if G1.graph[current][vertex] == 1 :
			if vertex in visitedAry :  	   # 방문한 적이 있는 정점이면 탈락
				pass
			else : 			   # 방문한 적이 없으면 다음 정점으로 지정
				next = vertex
				break

	if next != None :			  	   # 다음에 방문할 정점이 있는 경우
		current = next
		stack.append(current)
		visitedAry.append(current)
	else :            	  	  	  	  # 다음에 방문할 정점이 없는 경우
		current = stack.pop()


print('방문 순서 -->', end='')
for i in visitedAry :
	print(chr(ord('A')+i), end='   ')

Code09-03_.py

Represents a weighted graph using an adjacency matrix

## Class & Function Declarations ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

## Global Variables ##
G1 = None
stack = []
visitedAry = []		# Visited vertices

## Main Code ##
G1 = Graph(4)
G1.graph[0][2] = 1; G1.graph[0][3] = 1
G1.graph[1][2] = 1
G1.graph[2][0] = 1; G1.graph[2][1] = 1; G1.graph[2][3] = 1
G1.graph[3][0] = 1; G1.graph[3][2] = 1

print('## G1 Undirected Graph ##')
for row in range(4) :
	for col in range(4) :
		print(G1.graph[row][col], end = ' ')
	print()

current = 0		# Start vertex A
stack.append(current)
visitedAry.append(current)

while (len(stack) != 0) :
	next = None
	for vertex in range(4) :
		if G1.graph[current][vertex] == 1 :
			if vertex in visitedAry :  	   # If vertex already visited, skip
				pass
			else : 			   # If not visited, set as next vertex
				next = vertex
				break

	if next != None :			  	   # When there is a next vertex to visit
		current = next
		stack.append(current)
		visitedAry.append(current)
	else :            	  	  	  	  # When no next vertex to visit
		current = stack.pop()


print('Visit order -->', end='')
for i in visitedAry :
	print(chr(ord('A')+i), end='   ')

Code09-04.py

깊이 우선 탐색(DFS)을 구현합니다

gSize  = 6
def findVertex(g, findVtx) :

	stack = []
	visitedAry = []	# 방문한 노드

	current = 0	# 시작 정점
	stack.append(current)
	visitedAry.append(current)

	while (len(stack) != 0) :
		next = None
		for vertex in range(gSize) :
			if g.graph[current][vertex] != 0 :
				if vertex in visitedAry :	# 방문한 적이 있는 정점이면 탈락
					pass
				else :			# 방문한 적이 없으면 다음 정점으로 지정
					next = vertex
					break

		if next != None :				# 다음에 방문할 정점이 있는 경우
			current = next
			stack.append(current)
			visitedAry.append(current)
		else :					# 다음에 방문할 정점이 없는 경우
			current = stack.pop()

	if findVtx in visitedAry :
		return True
	else :
		return False

Code09-04.py

Implements depth-first search (DFS)

gSize  = 6
def findVertex(g, findVtx) :

	stack = []
	visitedAry = []	# Visited nodes

	current = 0	# Start vertex
	stack.append(current)
	visitedAry.append(current)

	while (len(stack) != 0) :
		next = None
		for vertex in range(gSize) :
			if g.graph[current][vertex] != 0 :
				if vertex in visitedAry :	# If vertex already visited, skip
					pass
				else :			# If not visited, set as next vertex
					next = vertex
					break

		if next != None :				# When there is a next vertex to visit
			current = next
			stack.append(current)
			visitedAry.append(current)
		else :					# When no next vertex to visit
			current = stack.pop()

	if findVtx in visitedAry :
		return True
	else :
		return False

Code09-05.py

너비 우선 탐색(BFS)을 구현합니다

## 클래스 및 함수 선언 부분 ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print(' ', end = ' ')
	for v in range(g.SIZE) :
		print(nameAry[v], end = ' ')
	print()
	for row in range(g.SIZE) :
		print(nameAry[row], end = ' ')
		for col in range(g.SIZE) :
			print("%2d" % g.graph[row][col], end = ' ')
		print()
	print()

def findVertex(g, findVtx) :

	stack = []
	visitedAry = []	# 방문한 노드

	current = 0	# 시작 정점
	stack.append(current)
	visitedAry.append(current)

	while (len(stack) != 0) :
		next = None
		for vertex in range(gSize) :
			if g.graph[current][vertex] != 0 :
				if vertex in visitedAry :	# 방문한 적이 있는 정점이면 탈락
					pass
				else :			# 방문한 적이 없으면 다음 정점으로 지정
					next = vertex
					break

		if next != None :				# 다음에 방문할 정점이 있는 경우
			current = next
			stack.append(current)
			visitedAry.append(current)
		else :					# 다음에 방문할 정점이 없는 경우
			current = stack.pop()

	if findVtx in visitedAry :
		return True
	else :
		return False

## 전역 변수 선언 부분 ##
G1 = None
nameAry = ['춘천', '서울', '속초', '대전', '광주', '부산' ]
춘천, 서울, 속초, 대전, 광주, 부산 = 0, 1, 2, 3, 4, 5


## 메인 코드 부분 ##

gSize = 6
G1 = Graph(gSize)
G1.graph[춘천][서울] = 10; G1.graph[춘천][속초] = 15
G1.graph[서울][춘천] = 10; G1.graph[서울][속초] = 40; G1.graph[서울][대전] = 11; G1.graph[서울][광주] = 50
G1.graph[속초][춘천] = 15; G1.graph[속초][서울] = 40; G1.graph[속초][대전] = 12
G1.graph[대전][서울] = 11; G1.graph[대전][속초] = 12; G1.graph[대전][광주] = 20; G1.graph[대전][부산] = 30
G1.graph[광주][서울] = 50; G1.graph[광주][대전] = 20; G1.graph[광주][부산] = 25
G1.graph[부산][대전] = 30; G1.graph[부산][광주] = 25

print('## 자전거 도로 건설을 위한 전체 연결도 ##')
printGraph(G1)

# 가중치 간선 목록
edgeAry = []
for i in range(gSize) :
	for k in range(gSize) :
		if G1.graph[i][k] != 0 :
			edgeAry.append([G1.graph[i][k], i, k])

from operator import itemgetter
edgeAry = sorted(edgeAry, key = itemgetter(0), reverse = True)

newAry = []
for i in range(0,len(edgeAry), 2) :
	newAry.append(edgeAry[i])

index = 0
while (len(newAry) > gSize-1) :	# 간선의 개수가 '정점 개수-1'일 때까지 반복
	start = newAry[index][1]
	end = newAry[index][2]
	saveCost = newAry[index][0]

	G1.graph[start][end] = 0
	G1.graph[end][start] = 0

	startYN = findVertex(G1, start)
	endYN = findVertex(G1, end)

	if startYN and endYN :
		del (newAry[index])
	else :
		G1.graph[start][end] = saveCost
		G1.graph[end][start] = saveCost
		index += 1

print('## 최소 비용의 자전거 도로 연결도 ##')
printGraph(G1)

Code09-05.py

Implements breadth-first search (BFS)

## Class & Function Declarations ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print(' ', end = ' ')
	for v in range(g.SIZE) :
		print(nameAry[v], end = ' ')
	print()
	for row in range(g.SIZE) :
		print(nameAry[row], end = ' ')
		for col in range(g.SIZE) :
			print("%2d" % g.graph[row][col], end = ' ')
		print()
	print()

def findVertex(g, findVtx) :

	stack = []
	visitedAry = []	# Visited nodes

	current = 0	# Start vertex
	stack.append(current)
	visitedAry.append(current)

	while (len(stack) != 0) :
		next = None
		for vertex in range(gSize) :
			if g.graph[current][vertex] != 0 :
				if vertex in visitedAry :	# If vertex already visited, skip
					pass
				else :			# If not visited, set as next vertex
					next = vertex
					break

		if next != None :				# When there is a next vertex to visit
			current = next
			stack.append(current)
			visitedAry.append(current)
		else :					# When no next vertex to visit
			current = stack.pop()

	if findVtx in visitedAry :
		return True
	else :
		return False

## Global Variables ##
G1 = None
nameAry = ['Chuncheon', 'Seoul', 'Sokcho', 'Daejeon', 'Gwangju', 'Busan' ]
Chuncheon, Seoul, Sokcho, Daejeon, Gwangju, Busan = 0, 1, 2, 3, 4, 5


## Main Code ##
gSize = 6
G1 = Graph(gSize)
G1.graph[Chuncheon][Seoul] = 10; G1.graph[Chuncheon][Sokcho] = 15
G1.graph[Seoul][Chuncheon] = 10; G1.graph[Seoul][Sokcho] = 40; G1.graph[Seoul][Daejeon] = 11; G1.graph[Seoul][Gwangju] = 50
G1.graph[Sokcho][Chuncheon] = 15; G1.graph[Sokcho][Seoul] = 40; G1.graph[Sokcho][Daejeon] = 12
G1.graph[Daejeon][Seoul] = 11; G1.graph[Daejeon][Sokcho] = 12; G1.graph[Daejeon][Gwangju] = 20; G1.graph[Daejeon][Busan] = 30
G1.graph[Gwangju][Seoul] = 50; G1.graph[Gwangju][Daejeon] = 20; G1.graph[Gwangju][Busan] = 25
G1.graph[Busan][Daejeon] = 30; G1.graph[Busan][Gwangju] = 25

print('## Full connection map for bike road construction ##')
printGraph(G1)

# Weighted edge list
edgeAry = []
for i in range(gSize) :
	for k in range(gSize) :
		if G1.graph[i][k] != 0 :
			edgeAry.append([G1.graph[i][k], i, k])

from operator import itemgetter
edgeAry = sorted(edgeAry, key = itemgetter(0), reverse = True)

newAry = []
for i in range(0,len(edgeAry), 2) :
	newAry.append(edgeAry[i])

index = 0
while (len(newAry) > gSize-1) :	# Number of edges is repeat until 'vertex count - 1'
	start = newAry[index][1]
	end = newAry[index][2]
	saveCost = newAry[index][0]

	G1.graph[start][end] = 0
	G1.graph[end][start] = 0

	startYN = findVertex(G1, start)
	endYN = findVertex(G1, end)

	if startYN and endYN :
		del (newAry[index])
	else :
		G1.graph[start][end] = saveCost
		G1.graph[end][start] = saveCost
		index += 1

print('## Minimum cost bike road connections ##')
printGraph(G1)

📗 응용 예제 (Ex)

📗 Applied Examples (Ex)

Ex09-01.py

그래프 응용: DFS와 BFS를 비교합니다

## 클래스 및 함수 선언 부분 ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print('	', end='')
	for v in range(g.SIZE) :
		print("%9s" % storeAry[v][0], end = ' ')
	print()
	for row in range(g.SIZE) :
		print("%9s" %storeAry[row][0], end = ' ')
		for col in range(g.SIZE) :
			print("%8d" % g.graph[row][col], end = ' ')
		print()
	print()

## 전역 변수 선언 부분 ##
G1 = None
storeAry = [['GS25', 30], ['CU', 60], ['Seven11', 10], ['MiniStop', 90], ['Emart24', 40]]
GS25, CU, Seven11, MiniStop, Emart24 = 0, 1, 2, 3, 4


## 메인 코드 부분 ##

gSize = 5
G1 = Graph(gSize)
G1.graph[GS25][CU] = 1; G1.graph[GS25][Seven11] = 1
G1.graph[CU][GS25] = 1; G1.graph[CU][Seven11] = 1; G1.graph[CU][MiniStop] = 1
G1.graph[Seven11][GS25] = 1; G1.graph[Seven11][CU] = 1; G1.graph[Seven11][MiniStop] = 1
G1.graph[MiniStop][Seven11] = 1; G1.graph[MiniStop][CU] = 1; G1.graph[MiniStop][Emart24] = 1
G1.graph[Emart24][MiniStop] = 1

print('## 편의점 그래프 ##')
printGraph(G1)

stack = []
visitedAry = []			# 방문한 편의점

current = 0			# 시작 편의점
maxStore = current		# 최대 개수 편의점 번호(GS25)
maxCount = storeAry[current][1]	# 편의점의 허니버터 숫자
stack.append(current)
visitedAry.append(current)

while (len(stack) != 0) :
	next = None
	for vertex in range(gSize) :
		if G1.graph[current][vertex] == 1 :
			if vertex in visitedAry :	# 방문한 적이 있는 편의점이면 탈락
				pass
			else :			# 방문한 적이 없는 편의점이면 다음 편의점으로 지정
				next = vertex
				break

	if next != None :				# 방문할 다음 편의점이 있는 경우
		current = next
		stack.append(current)
		visitedAry.append(current)
		if storeAry[current][1] > maxCount :
			maxCount = storeAry[current][1]
			maxStore = current
	else :					# 방문할 다음 편의점이 없는 경우
		current = stack.pop()

print('허니버터칩 최대 보유 편의점(개수) -->', storeAry[maxStore][0], '(', storeAry[maxStore][1], ')')

Ex09-01.py

Graph application: compares DFS and BFS

## Class & Function Declarations ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print('	', end='')
	for v in range(g.SIZE) :
		print("%9s" % storeAry[v][0], end = ' ')
	print()
	for row in range(g.SIZE) :
		print("%9s" %storeAry[row][0], end = ' ')
		for col in range(g.SIZE) :
			print("%8d" % g.graph[row][col], end = ' ')
		print()
	print()

## Global Variables ##
G1 = None
storeAry = [['GS25', 30], ['CU', 60], ['Seven11', 10], ['MiniStop', 90], ['Emart24', 40]]
GS25, CU, Seven11, MiniStop, Emart24 = 0, 1, 2, 3, 4


## Main Code ##
gSize = 5
G1 = Graph(gSize)
G1.graph[GS25][CU] = 1; G1.graph[GS25][Seven11] = 1
G1.graph[CU][GS25] = 1; G1.graph[CU][Seven11] = 1; G1.graph[CU][MiniStop] = 1
G1.graph[Seven11][GS25] = 1; G1.graph[Seven11][CU] = 1; G1.graph[Seven11][MiniStop] = 1
G1.graph[MiniStop][Seven11] = 1; G1.graph[MiniStop][CU] = 1; G1.graph[MiniStop][Emart24] = 1
G1.graph[Emart24][MiniStop] = 1

print('## Store graph ##')
printGraph(G1)

stack = []
visitedAry = []			# Visited stores

current = 0			# Start store
maxStore = current		# Store number with max count (GS25)
maxCount = storeAry[current][1]	# Number of HoneyButter per store
stack.append(current)
visitedAry.append(current)

while (len(stack) != 0) :
	next = None
	for vertex in range(gSize) :
		if G1.graph[current][vertex] == 1 :
			if vertex in visitedAry :	# If store already visited, skip
				pass
			else :			# If store not visited, set as next
				next = vertex
				break

	if next != None :				# When there is a next store to visit
		current = next
		stack.append(current)
		visitedAry.append(current)
		if storeAry[current][1] > maxCount :
			maxCount = storeAry[current][1]
			maxStore = current
	else :					# When no next store to visit
		current = stack.pop()

print('Store with most HoneyButterChips (count) -->', storeAry[maxStore][0], '(', storeAry[maxStore][1], ')')

Ex09-02.py

그래프 응용: 최단 경로 탐색

## 클래스 및 함수 선언 부분 ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print(' ', end = ' ')
	for v in range(g.SIZE) :
		print(cityAry[v], end = ' ')
	print()
	for row in range(g.SIZE) :
		print(cityAry[row], end =' ')
		for col in range(g.SIZE) :
			print("%2d" % g.graph[row][col], end = ' ')
		print()
	print()

def findVertex(g, findVtx) :

	stack = []
	visitedAry = []

	current = 0
	stack.append(current)
	visitedAry.append(current)

	while (len(stack) != 0) :
		next = None
		for vertex in range(gSize) :
			if g.graph[current][vertex] != 0 :
				if vertex in visitedAry :
					pass
				else :
					next = vertex
					break

		if next != None :
			current = next
			stack.append(current)
			visitedAry.append(current)
		else :
			current = stack.pop()

	if findVtx in visitedAry :
		return True
	else :
		return False

## 전역 변수 선언 부분 ##
G1 = None
cityAry = ['서울', '뉴욕', '런던', '북경', '방콕', '파리' ]
서울, 뉴욕, 런던, 북경, 방콕, 파리 = 0, 1, 2, 3, 4, 5


## 메인 코드 부분 ##

gSize = 6
G1 = Graph(gSize)
G1.graph[서울][뉴욕] = 80; G1.graph[서울][북경] = 10
G1.graph[뉴욕][서울] = 80; G1.graph[뉴욕][북경] = 40; G1.graph[뉴욕][방콕] = 70
G1.graph[런던][방콕] = 30; G1.graph[런던][파리] = 60
G1.graph[북경][서울] = 10; G1.graph[북경][뉴욕] = 40; G1.graph[북경][방콕] = 50
G1.graph[방콕][뉴욕] = 70; G1.graph[방콕][북경] = 50; G1.graph[방콕][런던] = 30; G1.graph[방콕][파리] = 20
G1.graph[파리][방콕] = 20; G1.graph[파리][런던] = 60;


print('## 해저 케이블 연결을 위한 전체 연결도 ##')
printGraph(G1)

# 가중치 간선 목록
edgeAry = []
for i in range(gSize) :
	for k in range(gSize) :
		if G1.graph[i][k] != 0 :
			edgeAry.append([G1.graph[i][k], i, k])

from operator import  itemgetter
edgeAry = sorted(edgeAry, key = itemgetter(0), reverse=False)

newAry = []
for i in range(0,len(edgeAry), 2) :
	newAry.append(edgeAry[i])

index = 0
while (len(newAry) > gSize-1) :	# 간선의 개수가 '정점 개수-1'일 때까지 반복
	start = newAry[index][1]
	end = newAry[index][2]
	saveCost = newAry[index][0]

	G1.graph[start][end] = 0
	G1.graph[end][start] = 0

	startYN = findVertex(G1, start)
	endYN = findVertex(G1, end)

	if startYN and endYN :
		del (newAry[index])
	else :
		G1.graph[start][end] = saveCost
		G1.graph[end][start] = saveCost
		index += 1

print('## 가장 효율적인 해저 케이블 연결도 ##')
printGraph(G1)

Ex09-02.py

Graph application: shortest path search

## Class & Function Declarations ##
class Graph() :
	def __init__ (self, size) :
		self.SIZE = size
		self.graph = [[0 for _ in range(size)] for _ in range(size)]

def printGraph(g) :

	print(' ', end = ' ')
	for v in range(g.SIZE) :
		print(cityAry[v], end = ' ')
	print()
	for row in range(g.SIZE) :
		print(cityAry[row], end =' ')
		for col in range(g.SIZE) :
			print("%2d" % g.graph[row][col], end = ' ')
		print()
	print()

def findVertex(g, findVtx) :

	stack = []
	visitedAry = []

	current = 0
	stack.append(current)
	visitedAry.append(current)

	while (len(stack) != 0) :
		next = None
		for vertex in range(gSize) :
			if g.graph[current][vertex] != 0 :
				if vertex in visitedAry :
					pass
				else :
					next = vertex
					break

		if next != None :
			current = next
			stack.append(current)
			visitedAry.append(current)
		else :
			current = stack.pop()

	if findVtx in visitedAry :
		return True
	else :
		return False

## Global Variables ##
G1 = None
cityAry = ['Seoul', 'NewYork', 'London', 'Beijing', 'Bangkok', 'Paris' ]
Seoul, NewYork, London, Beijing, Bangkok, Paris = 0, 1, 2, 3, 4, 5


## Main Code ##
gSize = 6
G1 = Graph(gSize)
G1.graph[Seoul][NewYork] = 80; G1.graph[Seoul][Beijing] = 10
G1.graph[NewYork][Seoul] = 80; G1.graph[NewYork][Beijing] = 40; G1.graph[NewYork][Bangkok] = 70
G1.graph[London][Bangkok] = 30; G1.graph[London][Paris] = 60
G1.graph[Beijing][Seoul] = 10; G1.graph[Beijing][NewYork] = 40; G1.graph[Beijing][Bangkok] = 50
G1.graph[Bangkok][NewYork] = 70; G1.graph[Bangkok][Beijing] = 50; G1.graph[Bangkok][London] = 30; G1.graph[Bangkok][Paris] = 20
G1.graph[Paris][Bangkok] = 20; G1.graph[Paris][London] = 60;


print('## Full connection map for undersea cables ##')
printGraph(G1)

# Weighted edge list
edgeAry = []
for i in range(gSize) :
	for k in range(gSize) :
		if G1.graph[i][k] != 0 :
			edgeAry.append([G1.graph[i][k], i, k])

from operator import  itemgetter
edgeAry = sorted(edgeAry, key = itemgetter(0), reverse=False)

newAry = []
for i in range(0,len(edgeAry), 2) :
	newAry.append(edgeAry[i])

index = 0
while (len(newAry) > gSize-1) :	# Number of edges is repeat until 'vertex count - 1'
	start = newAry[index][1]
	end = newAry[index][2]
	saveCost = newAry[index][0]

	G1.graph[start][end] = 0
	G1.graph[end][start] = 0

	startYN = findVertex(G1, start)
	endYN = findVertex(G1, end)

	if startYN and endYN :
		del (newAry[index])
	else :
		G1.graph[start][end] = saveCost
		G1.graph[end][start] = saveCost
		index += 1

print('## Most efficient undersea cable connections ##')
printGraph(G1)

📙 자가 실습 (Self)

📙 Self Practice (Self)

Self09-01.py

무방향 그래프를 직접 구현합니다

## 함수 선언부
class Graph() :
    def __init__ (self, size) :
        self.SIZE = size
        self.graph = [ [0 for _ in range(size)] for _ in range(size) ]

# 전역 변수부
G1, G3 = None, None

# 메인 코드부
G1 = Graph(4)
G1.graph[0][3] = 1
G1.graph[1][2] = 1; G1.graph[1][3] = 1
G1.graph[2][1] = 1
G1.graph[3][0] = 1; G1.graph[3][1] = 1

print('## 무방향 그래프 ##')
for row in range(4):
    for col in range(4):
        print(G1.graph[row][col], end=' ')
    print()

Self09-01.py

Implements an undirected graph yourself

## Function Declarations
class Graph() :
    def __init__ (self, size) :
        self.SIZE = size
        self.graph = [ [0 for _ in range(size)] for _ in range(size) ]

# Global Variables
G1, G3 = None, None

# Main Code
G1 = Graph(4)
G1.graph[0][3] = 1
G1.graph[1][2] = 1; G1.graph[1][3] = 1
G1.graph[2][1] = 1
G1.graph[3][0] = 1; G1.graph[3][1] = 1

print('## Undirected Graph ##')
for row in range(4):
    for col in range(4):
        print(G1.graph[row][col], end=' ')
    print()

Self09-02.py

DFS를 활용한 그래프 순회를 직접 구현합니다

## 클래스 및 함수 선언부
class Graph() :
    def __init__ (self, size) :
        self.SIZE = size
        self.graph = [ [0 for _ in range(size)] for _ in range(size) ]

# 전역 변수부
G1 = None
stack = []
visitedAry = [] # 방문한 노드
nameAry = ['문별', '솔라', '휘인', '쯔위', '선미', '화사']
문별, 솔라, 휘인, 쯔위, 선미, 화사 = 0, 1, 2, 3, 4, 5

# 메인 코드부
gSize = 6
G1 = Graph(gSize)
G1.graph[문별][솔라] = 1; G1.graph[문별][휘인] = 1
G1.graph[솔라][문별] = 1; G1.graph[솔라][쯔위] = 1
G1.graph[휘인][문별] = 1; G1.graph[휘인][쯔위] = 1
G1.graph[쯔위][솔라] = 1; G1.graph[쯔위][휘인] = 1; G1.graph[쯔위][선미] = 1; G1.graph[쯔위][화사] = 1
G1.graph[선미][쯔위] = 1; G1.graph[선미][화사] = 1
G1.graph[화사][쯔위] = 1; G1.graph[화사][선미] = 1

current = 0 # 시작점 A
stack.append(current)
visitedAry.append(current)

while (len(stack) != 0) :
    next = None
    for vertex in range(gSize) :
        if G1.graph[current][vertex] == 1 :
            if vertex in visitedAry : # 찾은게 이미 방문했으면
                pass
            else : # 방문 안했으면 다음 노드로 지정
                next = vertex
                break

    if next != None : # 다음 방문지 있으면
        current = next
        stack.append(current)
        visitedAry.append(current)
    else :
        current = stack.pop()


print('방문 순서 -->', end='')
for i in visitedAry :
    print( nameAry[i], end='   ')