자료구조와 알고리즘 with 파이썬 chapter8. 그래프

08-1 그래프란?

• 그래프 : 복잡하게 연결된 객체 사이의 관계를 효율적으로 표현할 수 있는 자료구조. 
• 그래프는 정점의 집합과 간선의 집합으로 구성되므로 수학적으로 G = (V, E)와 같이 표시. 
• 정점들은 자체로는 큰 의미가 없지만, 이들을 간선으로 연결하면 관계가 만들어지고 그래프가 형성된다. 

그래프의 종류

• 무방향 그래프 : 두 정점을 연결하는 간선에 방향성이 없는 그래프. 간선은 양방향으로 갈수 있는 길. (A, B)로 표현
• 방향 그래프 : 다이그래프라고도 한다. 간선은 한 방향으로만 갈 수 있는 길. <A, B>로 표현. <A, B>와 <B, A>는 서로 다른 간선. 
• 완전 그래프 : 그래프의 모든 정점 사이에 간선이 존재하는 그래프. 정점이 n개인 무방향 완전 그래프는 n * (n-1)/2개의 간선을 갖고, 방향 그래프는 n * (n-1)개의 간선을 갖는다. 
• 부분 그래프 : 원래의 그래프에서 정점이나 간선 일부만을 이용해 만든 그래프. 
• 가중치 그래프 : 간선에 가중치가 할당된 그래프. (네트워크)

그래프의 용어

• 인접 : 간선으로 연결된 두 정점을 인접해 있다고 말한다. 
• 정점의 차수 : 그 정점에 연결된 간선의 수. 방향 그래프에서는 차수가 두 가지로 나뉜다. 외부에서 오는 간선의 수를 진입 차수, 외부로 향하는 간선의 수를 진출 차수라 부른다. 
• 경로 : 간선을 따라갈 수 있는 길을 순서대로 나열한 것. 경로를 구성하는 간선의 수를 경로 길이라고 한다. 
• 단순 경로 : 반복되는 간선이 없는 경로. 
• 사이클 : 시작 정점과 종료 정점이 같은 단순 경로. 
• 연결 그래프 : 모든 정점 사이에 경로가 존재한느 그래프. 
• 트리 : 사이클을 가지지 않는 연결 그래프. 

08-2 그래프의 표현

인접 행렬을 이용한 표현

• 2차원 배열을 이용하는 것. n*n 행렬. 간선이 있는 부분은 1로 표시, 존재하지 않는 부분 0으로 표시. 
• 무방향 그래프에서는 인전 행렬이 항상 대칭 행렬. 

인접 리스트를 이용한 표현

• 각 정점이 인접한 정점 리스트를 갖도록 하여 간선들을 표현. 

인접 행렬과 인접 리스트 중에서 어떤 것을 사용할까요?

• 정점이 n개인 그래프를 표현하기 위한 메모리의 양은 인접 행렬의 경우 n^2이므로 인접 리스트보다는 약간 불리하다.
• 그래프에 간선 (u, v)가 있는지를 검사하려면 행렬은 해당 성분을 바로 검사하면 되지만, 인접 리스트에서는 정점 u의 인접 리스트에서 v가 있는지 하나씩 검사해 보아야 하기 때문에 인접 리스트가 불리하다.
• 메모리 사용량이 중요하거나 정점에 비해 간선이 별로 없는 희소그래프에서는 인접리스트가 좋은 선택
• 정점끼리의 인접 여부를 빨리 알아내야 하거나, 완전 그래프나 이와 유사한 조밀 그래프라면 인접 행렬이 더 좋은 선택. 

08-3 그래프순회

• 그래프 순회 : 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문하는 작업. 
• 깊이 우선 탐색(DFS) : 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향을 다시 탐색. 
• 너비 우선 탐색(BFS) : 시작 정점에서 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문. 

깊이 우선 탐색

• 시작 정점에서 한 방향으로 갈 수 있는 곳까지 깊이 탐색을 진행하다가 더 이상 갈 곳이 없으면 가장 최근에 만났던 갈림길 정점으로 되돌아온다. 후입 선출 구조의 스택에 저장. 

def DFS(vtx, adj, s, visited):
	print(vtx[s], end' ')
    visited[s] = True
    
    for v in range(len(vtx)):
    	if adj[s][v] != 0
        	if visited[v]==False:
            	DFS(vtx, adj, v, visited)

너비 우선 탐색

• 가까운 정점부터 꼼꼼하게 살피고 먼 정점으 찾아가는 전략
• 큐를 사용. 큐에서 정점을 꺼낼 때마다 아직 방문하지 않은 모든 인접 정점들을 방문하고 큐에 삽입. 큐가 공백 상태가 될 때까지 계속된다. 

from queue import Queue
def BFS_AL(vtx, aList, s):
	n = len(vtx)
    visited = [False]*n
    Q = Queue()
    Q.put(s)
    visited[s] = True
    while not Q.empty():
    	s = Q.get()
        print(vtx[s], end=' ')
        for v in aList[s]:
        	if visited[v]==False:
            	Q.put(v)
                visited[v] = True

08-4 신장 트리

• 신장 트리 : 그래프 내 모든 정점을 포함하는 트리. 그래프의 정점은 모두 포함하고, 간선은 일부만을 포함해 트리의 형태(사이클이 없어야함)를 이루어야 한다. 
• 그래프이 정점수가 n이라면 신장 트리는 정확히 n-1개의 간선으로 모든 정점을 연결. 

08-5 최소 비용 신장 트리

• 그래프의 모든 정점(사이트)은 연결
• 연결에 필요한 간선의 가중치 합이 최소

최소 신장트리(MST): 가중치 그래프의 여러 신장 트리 중에서 간선의 가중치 합이 최소인 것.

프림 알고리즘

Prim()
그래프에서 시작정점을 선택하여 초기 트리(MST)를 만든다.
MST와 인접한 정점 중 간선의 가중치가 가장 작은 정점 v를 선택
v와 이때의 간선을 MST에 추가
아직 모든 정점이 삽입되지 않았으면 2행으로 이동

• selected[ ]: 정점이 MST에 포함되었는지를 기록. selected[v]가 True이면 v가 MST에 포함된 것. 맨 처음에는 MST가 공백 트리이므로 배열의 모든 요소가 False가 되고, 단계마다 선택되는 정점이 True로 변경
• dist[ ] : 현재까지 구성된 MST와 정점 사이의 최단거리를 저장한다. 처음에는 시작정점의 값만 0이고 나머지는 모두 무한대이다. 새로운 정점 u가 MST에 추가되면 u에 인점한 정점 v의 최단 거리 dist[v]가 더 짧아질 수 있다. 만약, 즉, 간선 (u, v)의 가중치가 기존의 dist[v]보다 적으면 dist[v]를 (u, v)의 가중치로 변경

프림 알고리즘의 구현

INF = 999
def getMinVertex(dist, selected):
	minv = 0
    mindist = INF
    for v in range(len(dist)):
    	if selected[v]==False and dist[v]<mindist:
        	mindist = dist[v]
            minv = v
    return minv