문제 개요
자료구조를 공부해오며 그래프의 개념과 표현 방법, 그리고 몇 가지 탐색 알고리즘을 공부하였다. 이번에는 인접리스트를 사용하여 표현한 그래프에 대해 깊이 우선 탐색 알고리즘(DFS)을 이용하여 연결성 여부를 확인하는 알고리즘에 대해 구현해보았다.
그래프가 주어질 경우 아래와 같이 그래프의 연결성 여부를 확인하는 알고리즘을 설계해본다.
(1) 주어진 그래프가 연결되어 있는가?
(2) 주어진 그래프가 연결되어 있지 않다면, 연결 컴포넌트의 개수와 각 정점이 어느 컴포넌트에 포함되는 지를 확인한다.
위의 그림에서 볼 수 있듯이 n개의 정점과 e개의 간선으로 이루어진 그래프가 있을 때, 그래프의 정점을 방문하며 연결성 여부를 확인하고 이에 대한 컴포넌트 정보를 기록해두었다가 출력하는 과정이 요구된다.
자료구조 및 알고리즘 설계
인접행렬과 인접리스트 중 그래프 표현 방식으로 인접리스트를 채택한다. 그래프의 인접리스트 표현을 위하여 노드 구조체를 다음과 같이 정의한다.
define VERTEX 7
typedef struct node {
vertex
link
} Node
Node list[VERTEX]노드의 구조에서 vertex는 그래프의 정점을 의미하고 link는 연결리스트를 사용하여 다음 노드를 가리키는 포인터를 의미한다. list는 그래프의 정점 개수 n의 크기를 갖는 포인터 배열이며, list[i]는 정점 i에 인접한 정점들을 연결리스트로 표현한 헤더 포인터를 의미한다. 아래의 그림은 문제 개요에 첨부한 그래프를 인접리스트로 표현한 예를 보여준다.
아래의 내용은 알고리즘 설계와 관련된 내용이다.
문제를 해결하기 전, 먼저 그래프의 연결성 문제를 검토해보아야 한다. 앞서 문제 개요에서 예시로 주어진 그래프 그림을 참조해보면 다음과 같은 정보를 알 수 있다.
(1) 이 그래프는 연결되어 있지 않다.
(2) -1 이 그래프는 네 개의 컴포넌트를 갖는다.
(2) -2 각 정점이 포함되는 컴포넌트는 다음과 같다.
컴포넌트 1: (0)
컴포넌트 2: (1)
컴포넌트 3: (2, 3)
컴포넌트 4: (4, 5, 6)
이제 본격적으로 그래프의 연결성 문제를 해결하기 위한 방법을 서술해볼텐데, 앞에서도 언급했듯 이 과정에서 깊이 우선 탐색(DFS) 알고리즘을 적용한다. 또한 컴포넌트에 대한 정보를 출력해낼 수 있어야 하기 때문에 추가적으로 count 변수를 선언할 필요가 있다. 새로운 컴포넌트에서 DFS 알고리즘이 호출될 때마다 count 값을 1씩 증가한다. 위의 예시의 경우 DFS(0), DFS(1), DFS(2), DFS(4)에서 count 값이 1씩 증가하게 될 것이고 전체 컴포넌트의 개수는 4가 된다. 그런 다음, 그래프에서 각 정점이 어느 컴포넌트에 포함되는가를 기록해두어야 하는데 이는 dfs_visited 배열을 이용한다. dfs_visited 배열은 초기에 모두 0으로 설정되어 있다가 알고리즘 수행에 따라 한 정점을 방문하게 될 경우 count 값으로 0을 대체한다. 마지막 정점까지 탐색 알고리즘이 수행되면 dfs_visited 배열에는 각 정점이 어느 컴포넌트에 포함되는 지에 관한 정보가 저장된다. 아래의 표는 앞선 선보인 예시 그래프에 대하여 count 값을 dfs_visited에 적용한 결과이다.
아래의 알고리즘은 깊이 우선 탐색을 위한 과정을 가상코드로 기술한 알고리즘이다.
1. Algorithm Graph_dfs_connected(list, v, count)
2. Input: 그래프의 인접리스트(list), 시작 정점(v), 컴포넌트 수(count)
3. Output: DFS 방식으로 방문한 그래프의 정점들
4. w 변수 선언
5. dfs_visited[v] <- count
6. print v
7. for w <- list[v] to w = NULL do {
8. if (dfs_visited[w.vertex] = 0) then
9. Graph_dfs_connected(list, w.vertex, count)
10. }
11. end알고리즘에서 입력은 인접리스트로 표현된 그래프의 포인트 배열과 시작 정점, 컴포넌트 수 이다. 출력은 깊이 우선 방식에 따라 방문하여 출력된 정점들이다. 4번 줄에서 노드 포인터 변수 w를 선언해준다. 5번 줄의 dfs_visited 배열은 해당 정점이 방문 되었는지를 판단하기 위해 사용하는 배열로 초기값은 모두 0으로 설정되어 있는 배열이다. 정점 v가 방문될 경우 count 값을 할당한다. 6번 줄은 방문된 정점을 출력한다. 7~10번 줄은 인접리스트에서 시작 정점 v에 인접한 정점을 순환 호출한다. 위 반복문으로 모든 정점들을 방문하여 출력한다.
아래의 알고리즘은 앞서 기술한 Graph_dfs_connected 알고리즘을 사용하여 그래프의 연결 컴포넌트를 계산하기 위한 과정을 가상코드로 기술한 알고리즘이다.
1. Algorithm Graph_connected(list, n)
2. Input: 그래프의 인접리스트(list), 정점 개수(n)
3. Output: 그래프의 연결성(컴포넌트 개수, 정점의 소속 컴포넌트)
4. count <- 0
5. for i <- 0 to n-1 do {
6. if (dfs_visited[i] = 0) {
7. count <- count + 1
8. Graph_dfs_connected(list, i, count)
9. print “//” }
10. }
11. Component_print(count)
12. end알고리즘에서 입력은 인접리스트로 표현된 그래프와 정점의 전체 개수가 주어진다. 출력은 입력 그래프의 컴포넌트 개수와 각 정점이 어느 컴포넌트에 포함되었는지와 같은 그래프의 연결성에 대해 알려준다. 컴포넌트 수를 계산하기 위해 4번 줄에 count 변수를 선언하고 0으로 초기화한다. 5~10번 줄은 정점 0을 시작 정점으로 하여 n-1번째 정점까지 박복하여 Graph_dfs_connected 알고리즘을 호출한다. 7번줄은 시작 정점이 바뀌어서 DFS 알고리즘이 호출될 때마다 컴포넌트 개수를 의미하는 count 값이 1씩 증가함을 의미한다. 9번 줄은 출력 시 화면 상에서 컴포넌트끼리 구별하기 위한 형식적 호출이다. 11번의 Component_print 알고리즘에 대해서는 이어서 후술할 알고리즘을 참고하면 이해할 수 있다.
아래의 알고리즘은 앞서 기술한 Graph_connected 알고리즘에서 알아낸 그래프의 연결성 정보에 대해 화면 상에 출력하기 위한 과정을 가상코드로 기술한 알고리즘이다.
1. Algorithm Component_print(count)
2. Input: 컴포넌트 수(count)
3. Output: 그래프의 연결성(컴포넌트)에 대한 정보 출력
4. print “컴포넌트 개수” + count + “\n”
5. for i <- i to count do {
6. print “컴포넌트 “ + i
7. for j <- 0 to VERTEX -1 do {
8. if (dfs_visited[j] = i) then
9. print j }
10. print “\n”
11. }
12. end알고리즘에서 입력은 인접리스트로 표현한 그래프의 컴포넌트 수이며 출력은 그래프의 연결성에 대한 정보를 화면 상으로 출력해낸다. 4번 줄에서 컴포넌트의 총 개수를 출력하며, 5~11번 줄은 각 컴포넌트마다 인덱스와 해당되는 정점을 출력하는 반복문이다.
프로그램 구현 및 실행 결과
논의 사항
그래프의 연결 여부를 확인하고 연결 요소에 대해 알아보기 위한 알고리즘을 구상해보았다. 즉, 그래프가 연결되어있지 않을 경우에 컴포넌트의 개수와 각 정점이 어느 컴포넌트에 포함되는지를 확인할 수 있도록 알고리즘을 구현해보았다. 연결리스트와 DFS 알고리즘을 통해 위와 같이 구현해낼 수 있었다. 또한 기본적인 그래프 문제와 달리 dfs_visited 배열에 정점 v를 방문했을 때 단순히 방문 여부만을 판별하기 위해 1을 할당하는 것이 아닌, 해당 정점이 어느 컴포넌트에 포함되는지에 대한 정보를 저장할 수 있도록 count 값을 할당했다. 그리하여 최종적인 그래프의 연결성 정보에 대해 출력해내는 알고리즘까지 구현해보았다. 위 문제를 해결하기 위해 연결리스트와 DFS 방법을 채택했지만, BFS 방법으로도 추가적으로 구현해본다면 탄탄한 코딩 실력을 구축하는데 큰 도움이 될 것이라 생각한다.
코드
자세한 코드는 Github에서 확인할 수 있다.
