그래프

개념

--> 여러 노드가 서로 연결된 자료구조
--> 트리는 하위 노드 방향으로만 이어지는 구조

용어

정점(Vertex) : 트리에서의 노드 개념
간선(Edge) : 정점을 이어주는 선
정점 집합 : V(G)
간선 집합 : E(G)

종류

1. 무방향 그래프

--> 간선에 방향성이 없는 그래프
방향성이 없는 간선의 쌍은 소괄호 ( ) 로 표기한다.

2. 방향 그래프

--> 간선에 방향성이 있는 그래프
방향성이 있는 간선의 쌍은 < > 로 표기한다.

3. 가중치 그래프

--> 간선마다 다른 가중치가 부여된 그래프

깊이 우선 탐색의 작동

그래프 순회는 반드시 시작 정점까지 돌아가야 한다
1) DFS : 깊이 우선 탐색
2) BFS : 너비 우선 탐색

그래프의 인접 행렬 표현

--> 그래프를 코드로 구현할 때 인접 행렬 사용
--> 연결되었으면 1, 아니면 0
--> 출발점과 도착점이 같은 자기 자신은 0
* 무방향 그래프의 인접 행렬은 대각선을 기준으로 서로 대칭

구현

1. 그래프의 정점 (Vertex) 생성

--> 인접 행렬은 2차원 배열이므로, 행과 열이 같은 2차원 배열을 생성하는 클래스로 작성

class Graph():
    def __init__(self, size):
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)] # 0으로 초기화
G1 = graph(4) # 4 * 4 크기의 인접 행렬 생성

2. 그래프의 정점 연결

--> 0, 1, 2, 3 은 각각 A, B, C, D 로 간주한다.

# [출발점][도착점]
G1.graph[0][1] = 1 # (A,B) 간선
G1.graph[0][2] = 1 # (A,C) 간선
G1.graph[0][3] = 1 # (A,D) 간선
G1.graph[1][0] = 1 # (B,A) 간선
G1.graph[1][2] = 1 # (B,C) 간선

생성 최종

## 함수 선언 부분 ##
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) # 4*4 그래프 생성
G1.graph[0][1] = 1;
# 생략
print('## G1 무방향 그래프 ##')
for row in range(4): # 2차원 배열 출력
    for col in range(4):
        print(G1.graph[row][col], end = ' ')
    print()
G3 = Graph(4)
G3.graph[0][1] = 1;
# 생략
print('## G3 방향 그래프 ##')
for row in range(4):
    for col in range(4);
        print(G3.graph[row][col], end = ' ')
    print()

3. 그래프 개선

--> 0, 1, 2, 3 으로 되어있는 정점을 이름으로 변경

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

4. DFS 구현 --> 스택 사용

1) 방문한 정점을 스택에 push -> append()
2) 방문할 곳이 막다른 곳이라면 스택에서 pop -> pop()
3) 기존에 방문한 여부를 확인하고자 방문 기록 배열 사용
4) 스택의 길이가 0이면 스택이 비어있는 것으로 처리

stack = []
stack.append(값1) # push
data = stack.pop() # pop

* 다음 정점을 찾는 과정은 인접 행렬에서 먼저 만나는 1을 찾는 과정

1) 첫 번째 정점 방문 (A)

current 변수에 정점 A 대입 -> 스택에 푸시 -> 방문 기록 추가

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

2) 두 번째 정점 방문 (C)

A열에서 가장 먼저 1이 나오는 C를 다음 정점으로 설정 (반복문) -> current 변수에 정점 C 대입 -> 스택과 방문기록에 추가

next = None
for vertex in range(4):
    if G1.graph[current][vertex] == 1: # A열에서 찾기
        next = vertex
        break
current = next # C를 current로 지정
stack.append(current)
visitedAry.append(current)

3) 세 번째 정점 방문 (B)

C열에서 방문한 정점 제외 가장 먼저 1이 나오는 B를 다음 정점으로 설정 (반복문) -> current를 B로 설정 -> 스택과 방문기록에 추가

next = None
for vertex in range(4):
    if G1.graph[current][vertex] == 1:
        if vertex in visitedAry: # 방문한 적 있으면 탈락
            pass
        else:
            next = vertex
            break
current = next
stack.append(current)
visitedAry.append(current)

4) 되돌아오는 과정

B열에서 방문한 정점 제외 가장 먼저 1이 나오는 정점 찾기 (반복문) -> 더 이상 방문할 정점이 없다 -> 스택에서 B를 pop 하여 현재 정점으로 지정

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()

--> 스택이 비어있으면 모든 정점을 방문한 것!!

최종

current = 0 # 시작 정점
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()

그래프의 응용

모든 정점이 연결되어있는지 확인하는 함수

gSzie = 6
def findVertex(g, findVtx):
    stack = []
    visitedAry = [] # 방문한 정점
    current = 0 # 시작 정점
    stack.append(current)
    visitedAry.append(current)
    while (len(stack) != 0): # 스택의 길이가 0이면 모든 정점 순회 완료
        next = None
        for vertex in range(gSize);
            if g.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()
        if findVtx in visitedAry:
            return True # 있으면 연결되어있는 상태
        else:
            return False # 없으면 연결되지않은 상태

신장 트리

--> 최소 간선으로 그래프의 모든 정점이 연결되는 그래프
--> 간선 개수 : 정점 개수 - 1

최소 비용 신장 트리

--> 신장 트리 중 간선의 가중치 합이 최소인 트리

구현 알고리즘

1) 프림 알고리즘
2) 크루스컬 알고리즘

가중치와 간선 목록 생성

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)
# edgeAry의 간선을 0번째 아이템을 기준으로 내림차순 정렬
# reverse=False --> 오름차순 정렬

중복 간선 제거

--> 같은 간선이 2개씩 중복되므로, 짝수번 혹은 홀수번의 간선을 제거하면 된다.

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

크루스컬 알고리즘

가중치가 높은 간선부터 제거

조건1. 간선을 제거해도 정점이 모두 연결되어야 한다.
조건2. 최소 신장 트리의 간선 갯수는 정점의 개수 -1 이다.

index = 0 # 가장 비용이 높은 간선의 index
start = newAry[index][1] # 출발 도시
end = newAry[index][2] # 도착 도시
G1.graph[start][end] = 0
G1.graph[end][start] = 0 # 간선 비용 초기화
del(newAry[index]) # 간선 삭제

해당 간선을 삭제하지 못하고 다음으로 넘어가야 할 때

--> 간선 삭제를 취소하고 index 변수를 다음 칸으로 이동
--> 복구를 대비하여 saveCost 변수에 기존 가중치 저장
--> findVertex 함수를 이용하여 정점이 떨어져있는지 확인
--> 정점이 떨어져있다면 가중치를 복구하고 index 1 증가

전체 코드

## 클래스와 함수 선언 부분 ##
class Graph():
    def __init__(self, size):
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]
def prtinGraph(g):
# 생략
def findVertex(g, findVtx):
# 생략
## 전역 변수 선언 부분 ##
G1 = None
nameAry = ['춘천', '서울', '속초', '대전', '광주', '부산']
춘천, 서울, 속초, 대전, 광주, 부산 = 0, 1, 2, 3, 4, 5
## 메인 코드 부분 ##
gSize = 6
G1 = Graph(gSize)
# 생략
# 가중치 간선 목록
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 # 가중치가 가장 큰 간선의 index
while (len(newAry) > gSize - 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