그래프 간단 정리

그래프

EX) SNS 사용자와 사용자의 친구관계, 지하철 노선도

노드와 간선으로 이루어진

 

관련 용어

정점 (vertax) : 노드

간선 (edge) : 노드를 연결하는 선, 노드 간의 관계

인접 정점 : 하나의 간선에 의해 직접 연결된 정점

정점의 차수 : 정점에 연결되어 있는 간선의 갯수

 

구현

배열 : 인접행렬 (불필요한 공간 많이 차지)

연결리스트 : 인접리스트 ( 전체 정점을 표현한 후 각 노드별로 연결된 정점을 표현)

 

분류

[방향성에 따른 분류]

1. 방향 그래프 (A to B : <A, B> )

2. 무방향 그래프 ( A to B : (A, B) )

 

[연결에 따른 분류]

1. 연결 그래프 : 모든 정점 간의 경로가 존재하는 그래프

2. 비연결 그래프 : 무방향 그래프에서 특점 정점쌍 사이에 경로가 존재하지 않는 그래프

 

[사이클에 따른 분류]

1. 순환 그래프 : 순환이 존재하는 그래프

2. 비순환 그래프 : 순환이 존재하지 않는 그래프

 

[특수한 그래프]

1. 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프

2. 완전 그래프 : 모든 정점이 간선으로 연결된 그래프

3. 이분 그래프

 

---

 

그래프의 탐색

1. 깊이 우선 탐색 (DFS)

시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 탐색하다가 갈 곳이 없으면 되돌아가서 (백트래킹) 다시 먼 경로까지 탐색하는 방법

 

구현 : 스택 원리를 이용한 재귀

 

2. 너비 우선 탐색 (BFS)

시작 정점에서 인접한 정점을 모두 방문 후 다음 정점을 차례로 방문

 

구현 : 큐

 

 

신장트리와 최소  신장 트리

내용 채우기