[자료구조] 07 그래프

▶ 그래프 (Graph)

방향 그래프

무방향 그래프

완전 그래프

가중치 그래프

부분 그래프

 

 

▶

그래프 G의 정점 집합	V(G) = {A, B, C, D}
무방향 그래프 G의 간선 집합	E(G) = {(A, B), (A, C), (A, D)}
방향 그래프 G의 간선 집합	E(G) = {<A, B>, <A, C>, <D, A>}

 

 

▶ 구현 방법 (2가지)

: 인접 행렬 기반 그래프 (정방 행렬 활용)

: 인접 리스트 기반 그래프 (연결 리스트 활용)

 

 

▶ 탐색

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

너비 우선 탐색 (Breadth First Search) (BFS)

 

 

▶ 깊이 우선 탐색 (DFS)

: 한 사람에게만 연락을 취한다. (PUSH 떠나는 노드)

: 연락할 사람이 없으면,  자신에게 연락한 사람에게 이를 알린다. (POP)

: 처음 연락을 시작한 사람의 위치에서 연락이 끝난다.

스택	경로 정보의 추적을 목적으로 한다.
배열	방문 정보의 기록을 목적으로 한다.

: 맨 처음 노드 PUSH 하고

: 맨 마지막 노드 PUSH 하지 않음

 

 

▶ 너비 우선 탐색 (BFS)

: 자신과 연결된 모든 사람에게 연락을 취한다 (Enqueue)

: 이를 반복한다. (Dequeue 한 노드의 연결된 노드 Enqueue)

큐	방문 차례의 기록을 목적으로 한다.
배열	방문 정보의 기록을 목적으로 한다.

: 맨 처음 노드 Enqueue 하지 않고

: 맨 마지막 노드 Enqueue 함

 

---

 

▶ 단순 경로

: 중복 간선 존재하지 않음

 

 

▶ 사이클

: 단순 경로이면서 시작 노드와 끝 노드가 동일한 경로

 

 

▶ 신장 트리 (Spanning Tree)

: 사이클을 형성하지 않는 그래프

 

 

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

: 신장 트리의 모든 간선의 가중치 합이 최소인 그래프

 

 

▶ 최소 비용 신장 트리의 구성을 위한 알고리즘

크루스칼 (Kruskal) 알고리즘

프림 (Prim) 알고리즘

 

 

▶ 크루스칼 알고리즘

: 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식

 

: (방법1)

: 가중치를 기준으로 간선을 오른차순으로 정렬한다.

: 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.

: 사이클을 형성하는 간선은 추가하지 않는다.

: 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.

 

: (방법2)

: 가중치를 기준으로 간선을 내림차순으로 정렬한다.

: 높은 가중치의 간선부터 시작하여 하나씩 그래프에서 제거한다.

: 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않는다.

: 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.

 

 

▶ 프림 알고리즘

: 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식