알고리즘 9주차

08. 그래프

 

그래프

: 정점(vertex)과 간선(edge)의 집합

: G = (V, E)

 

그래프의 종류

무방향 그래프 / 방향 그래프

완전 그래프 /부분 그래프

가중치 그래프 (network)

 

그래프의 용어

- 인접: 간선으로 연결된 두 정점의 관계

- 정점의 차수: 정점에 연결된 간선의 수

- 경로: 간선을 따라갈 수 있는 길을 나열한 것 

- 경로 길이: 경로를 구성하는 간선의 수

- 단순 경로: 반복되는 간선이 없는 경로

- 사이클: 시작 정점과 종료 정점이 같은 단순 경로

- 연결 그래프: 모든 정점 사이에 경로가 존재함

- 트리: 사이클을 가지지 않은 연결 그래프. 트리는 연결 그래프에 속한다.

 

그래프의 표현 (1) - 인접 행렬: 2차원 배열

: 행렬의 각 성분이 두 정점의 연결관계를 나타냄

- 무방향 그래프에서는 인접 행렬이 항상 대칭행렬이다

그래프의 표현 (2) - 인접 리스트: 연결 리스트

인접 리스트 표현 예시

→ 정점의 수에 비해 간선의 수가 적은 희소 그래프의 경우, 인접 리스트 표현이 메모리를 절약할 수 있다.

→ 정점 사이의 관계(간선 유무)를 찾아야하는 경우, 인접 행렬 표현이 빠르다.

 

그래프 순회: 그래프의 모든 정점 방문

(1) 깊이 우선 탐색 (DFS: Depth First Search)

: 시작 정점에서 한 방향으로 갈 수 있는 곳까지 깊이 탐색을 진행하다가, 더 이상 갈 곳이 없으면 가장 최근에 만났던 갈림길 정점으로 돌아온다 (이진트리 전위순회)

 

*python dfs 구현 (순환호출을 통한 시스템 stack 사용)

#정점 리스트: vtx
#인접 행렬: adj
#시작 정점: s
#각 정점의 방문 여부를 기록하는 리스트: visited 

def dfs(vtx, adj, s visited):
	visited[s] = True 
    #시작 정점 방문 기록
    
    for v in range(len(vtx)): 
    #정점 s에 대해
    	if adj[s][v]!=0: 
        #간선이 존재하는 정점 v가 
        	if visited[v]==False: 
            #아직 방문하지 않은 정점일 경우,
            	dfs(vtx, adj, v, visited)
                #v에 대한 깊이 탐색을 진행한다.

 

(2) 너비 우선 탐색 (BFS: Breadth Frist Search)

: 가까운 정점부터 꼼꼼하게 살피고 먼 정점을 찾아간다 (이진트리 레벨순회)

 

*python bfs 구현 (반복구조, Queue 활용)

#정점 리스트: vtx
#인접 리스트: aList
#시작 정점: s

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

 

신장 트리

: 그래프 내 모든 정점을 포함하는 트리

: 정점을 모두 포함하면서 간선의 일부만을 포함해 사이클이 없어야 한다

: 정점의 개수가 n개일 때, 간선의 개수는 항상 n-1이다

: 깊이 우선 탐색, 너비 우선 탐색을 통해 찾을 수 있다

 

최소 비용 신장 트리(MST: Minimum Spanning Tree)

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

 

MST 찾기 - Prim 알고리즘

1번: 시작 정점을 선택하여 초기 트리(MST)를 만든다

2번: MST와 인접한 정점 중 간선의 가중치가 가장 적은 정점 v를 선택한다

3번: v와 v를 트리와 연결하는 정점을 트리에 추가한다

4번 모든 정점이 삽입될 때까지 2, 3번을 반복한다 

 

- 시간복잡도: (정점의 개수 n)^2

 

*python Prim 알고리즘 구현

#dist[]: 현재까지 구성된 MST와 정점 사이의 가중치(거리)를 저장. 인접 정점이 아닌 경우 INF.
#selected[]: 정점이 MST에 포함되었는지 저장.
#min: MST와의 가중치가 최소인 정점.
#mindist: mim 정점과 MST의 가중치.

INF = 999 
def getMinVertex(dist, selected):
	min = 0
    	mindist = INF
        #시작정점을 0으로 가중치를 INFINITE로 초기화.
    
    for v in range(len(dist)):
    #전체 정점 중에서
    	if selected[v] == False and dist[v] < mindist:
        	mindist = dist[v]
            min = v
        retrun min
         #아직 MST에 포함되지 않았고, MST와의 가중치가 최소인 정점을 반환함

 

def Prim(vertex, adj):
	n = len(vertex)
    dist = [INF] * n
    dist[0] = 0
    selected = [False] * n
    #dist[], selceted[] 초기화
    
    for _ i range(n):
    	u = getMinVertex(dist, selected)
        selected[u] = True
        #MST와의 가중치가 최소인 정점 u를 MST에 추가한다
        for v in range(n):
        	if adj[u][v] != INF and not selected[v]:
            	if adj[u][v] < dist[v]:
                	dist[v] = adj[u][v]
                    #MST와 인접 정점들 간의 가중치 갱신. 
                    #이전 값보다 작은 경우에만 갱신한다. 이전 값보다 클 경우, MST에 포함되지 않기 때문이다.

 

 

---

BJ 

백준/Bronze/1159. 농구 경기

 

2402-ECC-AlgorithmStudy/백준/Bronze/1159. 농구 경기 at main · daj33/2402-ECC-AlgorithmStudy

백준/Silver/1012. 유기농 배추

2402-ECC-AlgorithmStudy/백준/Silver/1012. 유기농 배추 at main · daj33/2402-ECC-AlgorithmStudy

백준/Silver/1260. DFS와 BFS

2402-ECC-AlgorithmStudy/백준/Silver/1260. DFS와 BFS at main · daj33/2402-ECC-AlgorithmStudy

백준/Silver/2606. 바이러스

2402-ECC-AlgorithmStudy/백준/Silver/2606. 바이러스 at main · daj33/2402-ECC-AlgorithmStudy