그래프, 그래프탐색(DFS, BFS) 이론정리

그래프

연결되어 있는 객체 간의 관계를 표현하는 자료구조

그래프 용어

• 정점(vertex)과 간선(edge)
• 방향그래프: a→b <a, b>
• 무방향그래프: a↔b (a, b)
• 차수(Degree): 정점에 인접한 정점의 수 (진입차수, 진출차수)
• 경로: 시작정점부터 도착점까지의 정점들을 나열
  • 단순경로: 경로상의 정점들이 모두다름
  • 일반적인경로: 중복하여 방문하는 경우도 포함
  • 싸이클: 시작점과 도착점이 같은 단순경로 (트리는 사이클 안됨)
• 연결성분: 그래프에서 정점들이 서로 연결되어 있는 부분
• 가중치 그래프: 가중치 부여된 그래프, 음수가중치도 있음
• 부분그래프
• 트리: 싸이클이 없는 그래프
  • 신장트리(spanning tree): 하나의 연결성분, 모든 정점들을 싸이클 없이 연결하는 부분그래프
• 네트워크: 간선에 비용or가중치가 할당된 그래프 =가중치그래프

그래프 자료구조

• 인접 행렬: NxN 2차원배열, a[i][j]=0 or 1(가중치그래프는 1대신 가중치값 저장)

인접행렬 예시

• 인접 리스트: 각 정점마다 1개의 연결리스트를 이용하여 인접한 정점을 노드에 저장

  

  인접리스트 예시

• 희소그래프: 정점들간의 서로 연결된게 적게 연결 →인접리스트 표현 좋음.
• 조밀그래프: 간선의 수가 최대 간선수에 근접한 그래프 →인접리스트로 표현하면 조금 복잡해짐, 따라서 인접행렬이 나음

---

그래프 탐색

• 깊이우선탐색(DFS)-스택기반
• 너비우선탐색(BFS)-큐기반

깊이우선탐색(DFS)

임의의 정점에서 시작해서 이웃하는 하나의 정점방문!

방금 방문한 정점의 이웃 정점을 방문

이웃 정점을 모두 방문하면 이전 정점으로 되돌아가서 탐색 수행

수행시간: O(N+M) 정점N 간선M

너비우선탐색(BFS)

임의의 정점 s에서 시작해서 모든 이웃정점들 방문하고 방문한 정점들의 이웃정점들 모두 방문하는 방식

수행시간: O(N+M)

 

탐색예제

수행결과예시(0노드에서 시작한다고 가정)

DFS:0→2→3→9→8→1→(방문안한노드중맨앞)4→5→7→6 (모든노드방문, 끝)

0, 2, 3, 9, 8, 1, 4, 5, 7, 6

BFS:0→2→1→3→9→8→(방문안한노드중맨앞)4→5→7→6(모든노드방문,끝)

0, 2, 1 ,3, 9, 8, 4, 5, 6, 7