그래프, DFS, BFS

그래프

정점(Vertex)와 간선(edge)의 집합으로 

객체들을 연결 시킨 것.

복잡한 사건들, 객체들 사이의 관계를 

나타낼 때 사용된다. 

방향이 없이 간선만 연결되 있는 그래프는 무방향 그래프.

화살표로 정점간의 방향을 나타내어 연결한 그래프를 방향 그래프라고 한다.

이제 모든 정점이 다 연결 되있는 상태를 

완전 그래프라고 한다. 

완전 그래프에도 역시 방향, 무방향 그래프가 존재한다.

여기서 간선의 수가 차이가 나는데,

방향의 경우 N(N-1). 여기서 N은 정점의 수다.

무방향의 경우 N(N-1) / 2.

그래프에서 정점의 연결상태를 나타내는 표현법이 있다.

인접 행렬과 인접 리스트가 있다.

인접 행렬은 자신과 연결되있는 정점을 행렬로 표현한 것이다.

연결이 되있는 정점은 1, 안 되있다면 0으로 표현한다.

특징은 대각선으로 0이 들어있다.

자기 자신과는 연결이 되있지 않기 때문.

방향 그래프의 경우 인접 행렬이 조금 달라진다. 

C의 경우 자신이 가리킨 정점이 없기에

모두 0으로 채워넣는다.

리스트로도 연결 상태를 표현할 수 있다.

정점 순서는 상관없이 그냥 연결되있는 것들만 리스트로 표현하면 된다.

더 이상 연결된 정점이 없다면 역시 NULL로 표현.

방향 그래프도 인접 행렬때와 마찬가지로 

C는 연결된 것이 없기에 비워둔다. 

이제 그래프에서의 탐색 방법을 알아보자.

아래의 그래프를 가지고 DFS와 BFS를 알아보자.

DFS(Depth First Search)는 

한 정점에 대해서 더 이상 파고들 곳(탐색)이 없을때 까지 

탐색을 한다하여 "깊이 우선 탐색"이라고 한다.

이미 탐색된 곳은 탐색하지 않는다. 

위의 순서대로 탐색을 수행한다.

스택(Stack) 구조를 사용하며 재귀를 통한 수행을 하며 인접 노드를 방문한다.

백 트래킹(Back Tracking)을 통해 더 이상 길이 없으면 뒤 돌아서 다른 곳으로 탐색.

BFS(Breadth First Search)는 

말 그대로 폭 넓게 탐색을 하는 알고리즘으로, 

큐를 사용한다. 최단 거리를 탐색하는데 유용함.

인접 / 형제 노드를 모두 방문한다.

위의 그림이 이해가 안 간다면 아래의 큐 상태 그림을 보자. 

왼쪽은 get한 노드.

오른쪽은 큐에 들어있는 노드이다. 

get을 하며 인접한 노드를 모두 큐에 집어넣는다. 

이 역시 큐에 들어있는 노드는 다시 탐색하지 않는다.