📕 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 특정한 정점에서 다른 정점으로 갈 수 있는지 없는지. 특정 도시에서 다른 도시로 갈 수 있는지 없는지
- 깊이 우선 탐색(DFS: depth first search)
트리처럼, 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
(1) 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다
(2) 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택한다.
(3) u를 시작 정점으로 해서 DFS를 다시 한다.
(4) 탐색이 끝나게 되면 다시 v에 인접한 정점들 중에서 방문하지 않은 정점을 찾는다
(5) 만약 없으면 종료하고, 있다면 다시 그 정점을 시작 정점으로 해 DFS
💡 자기 자신을 다시 호출하는 순환 알고리즘
방문한 기록은 한쪽에 모아둔다 = 백트래킹
- 인접 행렬 버전 구현
순환 호출을 이용하는 방법, 방문 여부를 기록하는 배열 visited
void rDFS(GraphType* G, int s)
{
visited[s] = TRUE;
printf("[%d] ", s);
for(int t=1;t<=G->n;t++)
if(G->adjMat[s][t]==1 && visited[t] ==FALSE)
rDFS(G, t);
}명시적인 스택을 이용한 깊이 탐색의 구현
(1) 스택을 하나 생성해 시작 정점을 스택에 넣는다.
(2) 이어서 스택에서 한 정점을 꺼내 탐색을 시작한다.
(3) 정점을 방문한 후에 정점의 모든 인접 정점들을 스택에 추가한다.
(4) 스택에 정점이 하나도 남으지 않을 때까지 반복한다.
void stackDFS(GraphType* G, int s)
{
StackType S;
initStack(&S);
push(&S, s);
visited[s]=TRUE;
while(!isStackEmpty(&S))
{
s=pop(&S);
printf("[%d] ", s);
for(int t = G->n;t>0;t--)
if(G->adjMat[s][t]==1 && visited[t]==FALSE)
{
visited[t] = TRUE;
push(&S, t);
}
}
}💡 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그랲의 경우 인접 리스트로 표현되어 있다면 시간 복잡도가 O(n+e)이고, 인접 행렬로 표현되었다면 O(n^2)이다. 희소 그래프인 경우 깊이 우선 탐색은 인접 리스트의 사용이 시간적으로 유리하다.
- 너비 우선 탐색(breath first search:BFS)
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
가까운 거리에 있는 정점들을 차례로 저장할 수 있는 자료구조 큐 필요하다.
큐에서 정점을 꺼내서 정점을 방문하고 인접 정점들을 큐에 추가한다. 큐가 소진될 때 까지 동일한 코드를 반복한다.
void BFS(GraphType* G, int s)
{
QueueType Q;
initQueue(&Q);
visited[s]=TRUE;
printf("[%d] ", s);
enqueue(&Q, s);
while(!isQueueEmpty(&Q))
{
s = dequeue(&Q);
for(int t=1;t<=G->n;t++)
if(G->adjMat[s][t]==1 && visited[t]==FALSE)
{
visited[t]=TRUE;
printf("[%d] ", t);
enqueue(&Q, t);
}
}
}인접 행렬 -> O(n^2)
인접 리스트 -> O(n+e)
리스트 버전 구현해보기
