그래프 운행(Graph Traversal)

그래프 운행

깊이 우선 검색(DFS)

너비 우선 검색(BFS)

그래프의 연결된 요소

그래프 운행(Graph Traversal)

그래프 운행이라는 것은 그래프에 있는 정점과 에지를 체계적으로 방문하는 것을 말한다. 그래프 운행은 크게 깊이 우선 검색(depth first search; DFS)과 너비 우선 검색(breadth first search; BFS)으로 나눌 수 있다. DFS는 스택 자료 구조를 이용하고 BFS는 큐를 이용한다.

깊이 우선 검색은 트리의 전순위 운행을 일반화한 것으로 생각할 수 있다. 그리고 너비 우선 운행은 트리의 레벨 순위 운행을 일반화한 것이다.

그래프 운행에서 인접 리스트로 그래프가 표현되어 있다고 가정한다. 인접 행렬로 표현되어 있을 때에는 주어진 정점에 인접한 정점을 찾는 부분을 수정하여야 한다.

깊이 우선 검색 I

깊이 우선 검색(DFS)은 처음에 정점 [eqn: v]에서 시작하여 방문한다. 다음으로 [eqn: v]에 인접한 정점 중에 아직 방문하지 않은 정점 [eqn: w]를 선택하여 그 [eqn: w]에 대해 다시 깊이 우선 운행을 수행한다.

각 정점 [eqn: v]를 방문할 때 향후 [eqn: v]에 인접한 다른 정점을 쉽게 찾기 위하여 [eqn: v] 및 그와 관련 정보를 스택에 저장한다. 인접한 정점을 모두 방문한 정점에 도달하게 되면 그 정점에서 더 이상 진행할 수 없으므로 스택에서 정점을 꺼내 위 과정을 반복한다.

DFS는 다음과 같이 순환을 이용하면 간단히 구현할 수 있다. 전역 변수 visited[MAX_VERTICES]는 FALSE로 초기화되어 있다고 가정한다. 해더 노드로 구성된 배열은 graph[]이며, 각 노드는 vertex 필드와 link 필드로 구성된다.

void DFS(int v)

{

node_pointer w;

visited[v] = TRUE;

printf("%d",v);

for (w = graph[v]; w; w = w->link)

if (!visited[w->vertex])

DFS(w->vertex);

}

DFS를 위해서 필요한 시간은 [eqn: O(n+m)]이다. [eqn: n]은 그래프의 정점 수이며 [eqn: m]은 에지 수이다. 만약 그래프가 인접 행렬로 표현되어 있다면 DFS을 어떻게 수정하여야 하며, 이 때 DFS를 위한 시간 복잡도는 얼마나 될까?

그래프 운행을 위한 예

너비 우선 검색

너비 우선 검색(BFS)에서는 시작 정점 [eqn: v]를 방문한 후, [eqn: v]에 인접한 모든 정점을 차례로 방문한다. 더 이상 방문할 정점이 없으면 [eqn: v]에 인접한 정점중에 처음으로 방문한 정점을 방문하게 되고, 그 다음으로 두 번째로 방문한 정점에 인접한 정점을 차례로 방문하게 된다.

이 과정을 구현하기 위해서는 각 정점이 방문될 때 그 정점에 인접한 정점이 모두 큐에 삽입되어야 하며, 다음으로 방문할 정점은 큐에서 꺼내서 다시 위 과정을 반복하게 된다.

void BFS(int v)

{

node_pointer w;

initialize Queue;

printf("%d",v);

visited[v] = TRUE;

addQ(v);

while (!empty(Queue)) {

v = deleteQ();

for (w = graph[v]; w; w = w->link)

if (!visited[w->vertex]) {

printf("%d",w->vertex);

visited[w->vertex] = TRUE;

addQ(w->vertex);

}

}

}

BFS에서는 시작 정점 [eqn: v]에서부터 거리가 가까운 정점부터 방문하게 된다. BFS의 시간 복잡도는 DFS와 마찬가지로 [eqn: O(n+m)]이다. 그래프가 인접 행렬로 표현되어 있다면 시간 복잡도가 얼마나 될까?

그래프의 연결된 요소

그래프의 연결된 요소는 DFS나 BFS를 이용하면 쉽게 찾을 수 있다. 여기서는 DFS를 이용하는 경우를 생각하여 보기로 한다.

같은 연결된 요소에 속한 정점을 찾기 위하여 임의의 정점에서 시작하여 DFS를 실행하고 방문이 되지 않은 정점이 남아 있으면 다시 임의로 하나의 정점을 선택하여 DFS를 반복한다.

void connected(void)

{

int k;

for (k=0; k<n; k++)

if (!visited[k]) {

DFS(k);

printf("\n");

}

}

시간 복잡도가 [eqn: O(n+m)]임을 설명하여 보시오. 만약 DFS 대신에 BFS를 이용한다면 어떻게 수정하여야 하며, 시간 복잡도는 얼마나 될까?