그래프

그래프

G = (V, E)
그래프는 vertex ( node , 정점 ) 와 edge ( link , 간선 ) 로 구성되어있다.

degree (분지수) : 한 정점에 인접한 엣지의 수
adjacent : 정점과 정점이 하나의 간선으로 인접한 상태
incident : 간선과 정점이 인접한 상태

sparse : 노드에 비해 엣지가 적다 ( 인접리스트에 적합 )
dense : 간선이 많은 경우 , sparse 반대 ( 인접행렬에 적합 )

path (경로) : 3→2→5 O | 3→2→1→2→5 X
cicle : 3→2→5→4→3 돌아오는 것

Tree : 두 노드를 잇는 경로가 오직 하나밖에 없다는 것
사이클이 없는 그래프

그래프 표현

adjacency matrix : 인접 행렬 ( 2차원 배열 )
adjacency list : 인접리스트 ( 1차원 배열에 1차원 연결 리스트 )

인접 행렬

메모리 : $O(n^2)$ 로 메모리 낭비, 사용하지 않는 공간이 많다

E에 포함되는지 서치 : $O(1)$ G[u][v] == 1 로 확인하면 된다

u에 인접한 모든 노드에 대해 : $O(n)$ ← for i for j G[i][j]

새 edge 삽입 : $O(1)$ ← G[u][v] = 1

삭제 : $O(1)$ ← G[u][v] = 0

인접 리스트

메모리 : $O(n+m)$

E에 포함되는지 서치 : $O(1)$ G[u].search(v)→ search 로 확인하면 된다

u에 인접한 모든 노드에 대해 : $O(인접한 노드 수)$

새 edge 삽입 : $O(1)$ ← G[u].pushFront(v)

삭제 : $O(n)$ ← x=G[u].search(v) G[u].remove(x)

MST ( Minimum Spanning Tree )

Spanning Tree = 신장 트리 : 그래프의 최소 연결 부분 그래프
( $n$ 개의 정점이 $n-1$ 개의 간선 으로 연결된 그래프 )

	1. 모든 정점이 연결되어 있어야 한다
	
	2. 사이클이 포함되어서는 안된다

	3. 가중치의 합이 최소여야 한다

Sparse Graph 는 Kruskal 이 적합하고, Dense Graph 는 Prim 이 적합하다

— Kruskal MST Algorithm

$O(elog2e)$

Greedy Method( 탐욕적인 )을 이용 각 정점의 최소 비용으로 연결

간선들을 (가중치) 오름차순 정렬

정렬된 리스트를 순차확인하며 사이클이 형성되지 않는 간선, 정점 집합에 포함

🎈 만약 같은 집합에 포함되어있다면 그것은 사이클

— Prim MST Algorithm

$O(n^2)$

단계적으로 확장하는 방법

시작 정점 트리에 추가

트리에 존재하는 노드와 존재하지 않는 노드 사이에 가중치가 최소인 간선을 찾아 트리에 추가

트리에 추가해서 최소 가중치를 찾는 방법을 사용하면 시간 복잡도가 O(n^2) 이지만

min_heap을 사용해서 최소 가중치를 찾으면 O(e log v) 이다

출발 노드를 배열에 저장하고 출발 노드에 연결된 간선들을 heap에 저장한다 (목적지, 가중치)

heap 에 top 목적 노드가 배열에 존재하다면 pop 존재하지 않다면 배열에 추가한다

— Dijkstra Algorithm

프림 과 비슷하지만, 시작 정점에서 정점 사이에 최단 경로를 연결하는 알고리즘 이면서 가중치가 음수인 경우에는 불가능

배열에 시작 정점을 0으로 시작 정점을 제외한 모든 정점에 (무한대)로 초기화

시작정점을 최단 경로에 추가

정점과 인접한 경로를 최단 경로에 추가를 하는데
🎈 여기서 가중치를 비교하는 거야 시작 정점으로 부터의 거리가 저장된 값보다 작으면 대체
아니면 폐기

모든 정점이 최단 경로에 추가가 되면 탈출

Bigartite Graph

이분 그래프 : 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프

임의의 변 (u,v)∈E 에 대하여, 만약 u∈V~i~ 이며 v∈V~j~ 라면, i≠j 이다.

💡 너비 우선 탐색 으로 이분 그래프를 반별할 때는 같은 레벨의 정점끼리 같은 색으로 포함


만약 같은 레벨인데 다른 색이라면 이분 그래프가 될 수 없다

📎 그래프를 탐색 → 정점에 방문할 때 마다 두가지 색 중 하나로 표시

📎 다음 인접한 정점 방문 → 이전 색과 다른 색으로 표시

📎 ↑ 만약 정점 색이 같은 색이면 이분 그래프가 아니라고 판별

📎 탐색이 끝났는데 ↑ 조건에 멈추지 않았다면 이분 그래프로 판별