그래프

그래프

그래프정의 그래프탐색 위상정렬 최소신장트리 최단경로검색

그래프의 정의

• 정점의 모음과 이 정점을 잇는 간선의 모음
• 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때, G = (V, E)이다
• 사이클 : 정점 하나를 두 번 이상 거치는 경로
• 인접 : 간선으로 연결 되어있는 두 정점의 관계 (이웃)
• 연결성(connectivity) :
  • 그래프의 연결성 : 그래프 내 각 정점들이 모두 연결되어 있을 때
  • 정점의 연결성 : 두 정점간 경로가 존재 할 때

그래프 표현

• 정점 간의 인접 관계를 어떻게 나타낼 것인가? → 2차원 배열 혹은 리스트

인접 행렬(Adjacency Matrix)

• N개의 정점이 있을 때, N x N 행렬에서 각 원소가 인접해있는 경우 1로, 아니면 0으로 표기
• 그래프가 무방향성을 띄는 경우 대각선에 대해 대칭
• 장 : 정점 간 인접 여부를 빠르게 파악 가능
• 단 : 메모리 양 사용이 많아짐

인접 리스트(Adjacency List)

• 각 정점에 인접하는 정점을 연결하는 리스트
• 장 : 정점과 간선이 삽입 빠르고 메모리 양 적음
• 단 : 인접 여부를 파악 느림 (리스트 순차 탐색)

그래프 순회

DFS

BFS

위상 정렬

• 위상 : 어떤 정점이 다른 정점과의 관계 속에서 가지는 위치
• 그래프에 방향성이 있어야 하고 사이클이 없어야 함 → DAG(Directed Acyclic Graph)
• 진입 간선(Incoming Edge), 진출 간선(Outgoing Edge)
• 진입 간선이 없는 정점을 리스트에 추가하고 해당 정점 자신과 진출 간선을 그래프에서 제거를 반복
• dfs 탐색중 끝 정점을 헤드로 입력 반복

최소 신장 트리

• 그래프에서 가중치(weight) 추가
• 신장 트리(Spanning tree) : 그래프의 모든 정점을 연결하는 트리. 그래프의 하위 개념

프림 알고리즘

• 임의의 정점으로부터 매 순간을 기준으로 가장 작은 가중치를 가진 간선을 선택하여 트리를 만들어 나가는 알고리즘
• 가장 작은 가중치를 구하기 위해 삽입삭제가 빠르고 최소 값을 찾는 것에 거의 비용이 들지 않는 우선순위 큐를 사용

크루스칼 알고리즘

• 그래프 내의 모든 간선의 가중치를 파악하여 최소 값을 가진 간선을 선택해 트리에 추가
• 사이클이 생기는 것을 어떻게 효율적으로 감지할 것인가?
  • 각 정점 별로 분리집합을 만들고 간선으로 이어진 정점을 합집합 수행
  • 만약 두 정점이 같은 집합에 속해 있다면 사이클 형성

최단 경로 탐색

다익스트라 알고리즘

• 프림 알고리즘과 비슷하지만 경로의 길이를 감안해서 간선을 연결한다는 차이점이 있음
• 사이클이 없는 방향성 그래프에 한해 사용 가능