이 글은 기존 Tistory 블로그에서 옮겨온 글입니다. 원문: https://jms3084.tistory.com/15
1. 그래프 출력 함수
def print_graph(g):
for row in range(g.SIZE):
for col in range(g.SIZE):
print(g.graph[row][col], end = '\\t')
print()
print()
2. 깊이 우선 탐색 함수
def find_vertex(g, find_vtx):
stack = []
visitedAry = []
current = 0
stack.append(current)
visitedAry.append(current)
while len(stack) > 0:
next = None
for vertex in range(g.SIZE):
if g.graph[current][vertex] != 0:
if vertex not in visitedAry:
next = vertex
break
if next != None:
current = next
stack.append(current)
visitedAry.append(current)
else:
current = stack.pop()
if find_vtx in visitedAry:
return True
else:
return False
3. 최소 비용 신장 트리 생성 함수
- 최대 비용 신장트리인 경우 오름차순으로 정렬하면 된다.
def minimum_spanning_tree(g):
edgeAry = []
for row in range(g.SIZE):
for col in range(g.SIZE):
if g.graph[row][col] != 0:
edgeAry.append([g.graph[row][col], row, col])
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 g.SIZE - 1 < len(newAry):
weight = newAry[index][0]
start = newAry[index][1]
end = newAry[index][2]
g.graph[start][end] = 0
g.graph[end][start] = 0
start_found = find_vertex(g, start)
end_found = find_vertex(g, end)
if start_found and end_found:
del newAry[index]
else:
g.graph[start][end] = weight
g.graph[end][start] = weight
index += 1
4. 그래프 순회하며 최소, 최대값 구하는 함수
- 기존 함수에서 빨간색으로 칠해둔 부분만 추가하면 된다.
def find_max_count(g, storeAry):
stack = []
visitedAry = []
current = 0
stack.append(current)
visitedAry.append(current)
**maxStore = current
minStore = current
maxCount = storeAry[current][1]
minCount = storeAry[current][1]**
while len(stack)!=0:
next =None
for vertex in range(g.SIZE):
if g.graph[current][vertex] == 1:
if vertex not in visitedAry:
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
if storeAry[current][1] < minCount:
minCount = storeAry[current][1]
minStore = current**
else:
current = stack.pop()
**return storeAry[maxStore], storeAry[minStore]**
5. 그래프의 원리
- 그래프는 여러 노드가 연결된 자료구조이다.
- 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나뉜다.
- 간선에 가중치를 부여해 가중치 그래프도 만들 수 있다.
- 트리의 노드에 해당하는 용어가 그래프에서는 정점이다.