Graph

2019. 02. 11 (Mon)

비선형 자료구조: element간 관계가 n개

아이템간 연결 관계를 표현하는 자료구조

정점(Vertex)

간선(Edge)

• V개 정점의 그래프의 최대 간선: V(V-1)/2

I. 표현법

1. 인접 행렬

최대 노드 번호만큼 n*n 행렬을 만들어 간선정보를 저장

메모리를 많이 소모

두 노드가 연결되어 있는지 정보를 빠르게 알 수 있음

2. 인접 리스트

리스트에 각 노드의 연결 정보를 저장

행렬로도 작성 가능

한 노드의 모든 연결정보를 빠르게 알 수 있음

II. 순회

모든 노드를 빠짐없이 빠르게 조사하는 방법

1. DFS

stack 이용

사용자 정의 stack

시스템 정의 stack: 재귀

• performance가 떨어지고, stack overflow 발생 가능

시작 노드에서 가장 깊은곳 까지 방문하고, 다시 갈림길로 돌아와 재방문하며 모든 노드 방문

stack, visited 자료구조 필요

사용자 정의 stack 구현 방법

1. 시작 정점 v를 방문
2. v에서 인접한 정점 중에
   1. 방문하지 않은 정점 w가 있으면, 정점 v를 stack에 push하고 정점 w 방문. 이를 v로 하여 반복.
   2. 방문하지 않은 정점이 없으면 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 반복.
3. stack이 공백이 될 때 까지 2.를 반복

• 일단 방문, visited 처리, push(자기 자신), 인접행렬 찾고, 다시 방문
• 자기처리 먼저, 다음에 이웃처리
• 이웃이 없다? pop() 하여 인접행렬 찾기

(2) BFS

queue 이용

depth가 같은 level의 노드를 먼저 순회

1. 구현 방법

1. 시작노드 enqueue
2. 노드를 dequeue
   1. 만약 방문한 노드라면 continue
   2. 노드에 대해 연산
   3. 인접 노드 중 방문하지 않은 노드를 enqueue
3. 반복

---

• ← Previous Post
• Next Post →