2024. 1. 13. 00:12ㆍ프로그래밍 공부/Data Structure
13.1 그래프 추상 데이터 타입
그래프(graph)
= 물체들의 쌍들 사이에 존재하는 관계를 표현하는 방법
= 정점이라고 불리는 물체들의 집합과 그들 사이의 쌍대 연결들의 집합
그런데 이 "그래프"의 개념은 막대 차트 및 함수 그림과 혼동되어서는 안 된다.
이러한 종류의 "그래프들"은 이 장의 주제와 무관하기 때문이다.
그래프는 매핑, 운송, 전기 공학 및 컴퓨터 네트워크를 포함한 여러 도메인에 응용된다.
그래프 G: 단순히 V개의 정점(vertex)의 집합과 V개의 정점들 쌍들의 모임 E이며, 이를 간선(edge)이라고 한다.
→ 그래프는 어떤 집합 V개의 객체 쌍들 사이의 연결 또는 관계를 나타내는 방법
덧붙여서, 어떤 책들은 그래프에 대해 다른 용어를 사용하고,
우리가 정점을 노드(node)라고 부르는 것과 간선을 호(arc)라고 부르는 것을 언급한다.
우리는 "정점(vertices)"과 "가장자리(edges)"라는 용어를 사용한다
그래프에서 간선들은 방향을 잡거나(directed) 방향을 잡지 않는다(undirected).
만약 쌍 (u, v)의 순서가 정해지면 간선 (u, v)는 u에서 v로 향하고(directed), u는 v보다 앞선다고 한다.
만약 쌍 (u, v)의 순서가 정해지지 않으면 간선 (u, v)는 방향을 잡지 않는다(undirected)고 한다.
방향을 잡지 않은 간선들은 집합 표기법으로 {u,v}로 표기하기도 하지만,
단순화를 위해 쌍 표기법 (u, v)을 사용하며,
방향을 잡지 않은 경우 (u, v)는 (v, u)와 같다는 점에 주목한다.
그래프는 일반적으로 정점들을 타원이나 직사각형으로 그리고
간선들을 타원과 직사각형의 쌍을 연결하는 세그먼트 또는 곡선으로 그려서 시각화한다.
다음은 방향을 가진 그래프와 방향을 잡지 않은 그래프의 예이다.
예제 13.1:
정점 - 연구자 자신
간선 - 논문이나 책을 공저한 연구자와 연관된 정점의 쌍
다음의 그래프를 구성함으로써
특정 분야의 연구자들 간의 공동 작업을 시각화할 수 있다.
(그림 13.1 참조) 공동저자 상태는 대칭(symmetric) 관계이므로 이러한 간선은 지시되지 않는다.
즉, A가 B와 어떤 것을 했다면, B는 반드시 A와 어떤 것을 공동 제작한 것이다.
그림 13.1: 일부 저자 간의 공동 저작 그래프.
예제 13.2: 정점이 프로그램에 정의된 클래스를 나타내고,
그 간선이 클래스 간 상속을 나타내는 그래프를 객체 지향 프로그램과 연결할 수 있다.
만약 v에 대한 클래스가 u에 대한 클래스를 확장한다면, 정점 v에서 정점 u로의 간선이 존재한다.
상속 관계가 한 방향으로만 진행되기 때문에 그러한 간선들은 방향을 향한다.
무향 그래프(undirected graph): 모든 간선이 무향인 그래프
유향 그래프(directed graph): 모든 간선을 가진 그래프
혼합 그래프(mixed graph): 방향 간선과 무향 간선을 모두 가진 그래프
무향 또는 혼합 그래프는 모든 무향 간선을 쌍대 간선 (u,v)와 (v,u)로 대체함으로써
방향 그래프로 변환될 수 있다.
그러나, 그러한 그래프는 다음의 예시와 같은 여러 가지 응용이 있기 때문에,
무방향 및 혼합된 그래프를 그대로 유지하는 것이 종종 유용하다.
예제 13.3: 도시 지도는 교차점이나 막다른 골목을 꼭짓점으로 하고,
교차점이 없는 도로들이 늘어서 있는 그래프로 모델링할 수 있다.
이 그래프는 양쪽 도로들이 늘어서 있는 경우에 해당하는 무방향 간선들과,
한쪽 도로들이 늘어서 있는 경우에 해당하는 방향 간선들을 가진다.
→ 도시 지도를 모델링하는 그래프는 혼합된 그래프이다.
예제 13.4: 건물의 전기배선 및 배관망에 그래프의 물리적인 예가 존재한다.
이러한 네트워크는 그래프로 모델링될 수 있다.
꼭짓점: 각 커넥터, 고정구 또는 배출구
모서리: 전선 또는 배관의 중단되지 않은 신축
이러한 그래프는 실제로 훨씬 큰 그래프, 즉 국부적인 전력 및 물 분배망의 구성요소이다.
관심을 가지는 이러한 그래프의 특정 측면에 따라,
그 가장자리를 무방향 또는 방향으로 간주할 수 있는데,
왜냐하면 원칙적으로 물은 배관 내에서 흐를 수 있고
전류는 어느 방향으로든 도선 내에서 흐를 수 있기 때문이다.
간선의 끝점(end vertices or endpoints): 간선으로 연결된 두 개의 정점
만약 간선이 방향을 가진다면,
그것의 첫 번째 끝점은 그것의 원점(origin)이고 다른 하나는 간선의 목적지(destination)이다.
끝점이 u와 v인 간선이 존재한다 → 두 개의 정점 u와 v는 인접하다(adjacent).
정점이 간선의 끝점 중 하나 → 간선은 한 정점에 부속된다(incident).
정점의 나가는 간선들(outgoing edges): 그 정점이 원점이 되는 방향을 가진 간선들
정점의 들어오는 간선들(incoming edges): 그 정점이 목적지가 되는 방향을 가는 간선들
정점 v의 차수(degree) = deg(v) = v의 입사 간선들의 수
정점 v의 in-degree = indeg(v) = v의 들어오는 간선들의 수
정점 v의 out-degree = outdeg(v) = v의 나가는 간선들의 수
예제 13.5: 비행 네트워크를 만들어서 항공교통을 연구할 수 있다.
비행 네트워크(flight network): 정점이 공항과 연관되고 간선이 비행과 연관되는 그래프 G
(그림 13.2 참조) 그래프 G에서 간선들은 주어진 비행편이
(기점 공항에서 목적지 공항까지) 특정한 이동 방향을 가지므로 방향을 향한다.
G에서 간선 e의 끝점들 - 각각 e에 해당하는 비행의 출발지와 도착지
두 공항 사이를 비행하는 비행편이 있는 경우 G에서는 두 공항이 인접하고,
e에 해당하는 비행편이 v에 대해 공항을 오갈 때 간선 e는 G에서 정점 v에 결합된다.
정점 v의 나가는 간선들 - v의 공항에서 나가는 비행편
정점 v의 들어오는 간선들 - v의 공항으로 가는 들어오는 비행편
G의 정점 v의 in-degree - v의 공항으로 들어오는 들어오는 비행편의 수
G에서 정점 v의 out-degree - v의 공항에서 나가는 비행편의 수
그래프의 정의는 집합(set)이 아닌 컬렉션(collection)으로 간선들의 그룹을 가리킨다.
병렬 간선(parallel edge) or 다중 간선(multiple edge):
두 개의 방향 없는 간선들이 같은 말단 정점들을 가질 수 있다.
두 개의 방향된 간선들이 같은 출발지와 같은 목적지를 가질 수 있다.
ex) 비행 네트워크(예:13.5)
이 경우 같은 정점 쌍 사이의 다중 간선들은
같은 경로에서 하루 중 다른 시간에 운행되는 다른 비행들을 나타낼 수 있다.
자기 루프(self-roop):
정점과 자신을 연결하는 간선
즉, 두 끝점이 일치하는 경우 (방향이 없거나 방향이 있는) 간선
ex) 도시 지도(예: 13.3)와 관련된 그래프
여기서 "원"(시작점으로 되돌아오는 곡선 거리)에 해당할 수 있다.
몇 가지 예외를 제외하고 그래프는 병렬 간선이나 자기 루프를 갖지 않는다.
이러한 그래프는 단순하다(simple)고 할 수 있다.
따라서 단순한 그래프의 간선들은 (단순한 컬렉션이 아니라)
정점 쌍의 집합(set)이라고 일반적으로 말할 수 있다.
이 장 전체에 걸쳐 특별한 언급이 없는 한 그래프는 단순하다고 가정한다.
그림 13.2: 비행 네트워크를 나타내는 유향 그래프의 예이다.
간선 UA 120의 끝점: LAX와 ORD, LAX와 ORD는 인접한다.
DFW의 in-degree: 3이고,
DFW의 out-degree: 2이다.
그래프의 몇 가지 중요한 성질
명제 13.6: G가 m개의 간선을 갖는 그래프라면
정당화: 간선 (u,v)는 위의 합에서 두 번 계산된다;
한 번은 끝점 u에 의해 그리고 한 번은 끝점 v에 의해 계산된다.
정점들의 차수에 대한 간선들의 총 기여도 = 간선들의 개수 * 2
명제 13.7: G가 m개의 간선을 가지는 방향 그래프라면
정당화: 방향 그래프에서 간선 (u,v)는 원점 u의 차수에 한 단위, 목적지 v의 차수에 한 단위를 기여한다.
간선들의 정점들의 차수에 대한 기여도의 총합 = 간선들의 수
차수들에 대한 기여도의 총합 = 간선들의 수
n개의 정점을 갖는 단순 그래프가 O(n^2)개의 간선을 갖는다는 것을 다음에 보여준다.
명제 13.8: G를 n개의 정점과 m개의 간선을 갖는 단순 그래프라고 하자.
G가 방향이 없으면 m≤ n(n - 1)/2이고, G가 방향이 있으면 m≤ n(n - 1)이다.
정당화:
G가 방향성이 없다고 가정하자.
어떤 두 간선도 같은 끝점을 가질 수 없고 자기 루프가 없으므로,
G에 있는 정점의 최대 차수: n - 1
→ 명제 13.6에 의해 2m ≤ n(n - 1)
이제 G가 방향성을 갖는다고 가정하자.
어떤 두 간선도 같은 출발점과 도착점을 가질 수 없고 자기 루프가 없으므로,
G에 있는 정점의 최대 차수: n - 1
→ 명제 13.7에 의해 m ≤ n(n - 1)
경로(path): 정점에서 시작하여 정점에서 끝나는 교대 정점과 간선의 시퀀스
각 간선이 이전 및 후속 정점에 입사되도록 한다.
사이클(cycle): 시작점과 끝점이 같은 적어도 하나의 간선을 가지는 경로
경로의 각 정점이 서로 다르다 → 경로는 단순하다
사이클의 각 정점이 처음과 마지막을 제외하고는 서로 다르다 → 사이클은 단순하다
유항 경로(directed path): 모든 간선이 방향을 가지며 그 방향을 따라 가로지르도록 하는 경로
유향 사이클(directed cycle)도 이와 유사하게 정의된다.
예를 들어 그림 13.2에서 (BOS, NW 35, JFK, AA 1387, DFW)는 유향 단순 경로에 있고
(LAX, UA 120, ORD, UA 877, DFW, AA 49, LAX)는 유향 단순 사이클에 있다.
경로 P나 사이클 C가 단순 그래프라면 P나 C의 간선을 생략할 수 있는데,
이 경우 P는 인접한 정점들의 리스트이고 C는 인접한 정점들의 사이클이다.
예제 13.9:
도시 지도를 나타내는 그래프 G가 주어졌을 때 (예시 13.3 참조),
→ 한 커플이 G를 통해 길을 건널 때 추천된 식당에서 저녁을 먹는 모형을 만들 수 있다.
만약 그들이 길을 알고 있고, 우연히 같은 교차점을 두 번 지나가지 않는다
→ 그들은 G 안에서 단순한 경로를 건넌다.
마찬가지로, 커플이 집에서 식당까지 그리고 돌아오는 전체 여행을 사이클로 모형화할 수 있다.
만약 그들이 식당에서 집까지 가는 방식과 완전히 다른 방식으로,
심지어 같은 교차점을 두 번도 거치지 않는다면,
→ 그들의 전체 왕복 여행은 단순한 사이클이다.
마지막으로, 만약 그들이 전체 여행 동안 일방통행로를 따라 이동한다면,
→그들의 밤을 유향 사이클로 모형화할 수 있다.
그래프 G의 부분 그래프(subgraph):
정점과 간선이 각각 G의 정점과 간선의 부분집합인 그래프 H
예시) 그림 13.2의 비행 네트워크에서
정점 BOS, JFK, MIA와 간선 AA 903, DL 247은 부분 그래프를 이룬다.
G의 신장 부분 그래프(spanning subgraph):
그래프 G의 모든 정점을 포함하는 G의 부분 그래프
연결된(connected) 그래프:
그래프는 임의의 두 정점에 대하여, 그들 사이에 경로가 존재하는 그래프
G의 연결된 구성요소(connected component):
만약 그래프 G가 연결되지 않았다면, 그 그래프의 최대 연결 부분 그래프
포레스트(forest): 사이클이 없는 그래프
트리(tree) = 연결된 포레스트 = 사이클이 없는 연결된 그래프
트리의 이러한 정의는 7장에서 설명한 것과는 다소 다르다는 것에 주목하라.
즉, 그래프의 맥락에서 트리는 루트가 없다.
모호성이 있을 때마다 7장의 트리들을 루트가 있는 트리(rooted tree)라고 부르고,
이 장의 트리들을 자유 트리(free tree)라고 불러야 한다.
포리스트의 연결된 구성요소: (자유) 트리
그래프의 신장 트리(spanning tree): (자유) 트리인 신장 부분 그래프
예제 13.10:
오늘날 가장 많이 이야기되는 그래프는 아마도 인터넷일 것인데,
이 그래프는 다음과 같이 구성된 그래프이다.
꼭짓점 - 컴퓨터
가장자리 - 인터넷 상의 컴퓨터 쌍 사이의 통신 연결
인터넷의 부분 그래프: wiley.com 처럼 하나의 도메인에 있는 컴퓨터와 컴퓨터 사이의 연결
만약 이 부분 그래프가 연결되어 있다
→ 이 도메인에 있는 컴퓨터의 두 사용자는
자신의 정보 패킷이 도메인을 떠나지 않고도 서로에게 이메일을 보낼 수 있다.
이 부분 그래프의 가장자리가 신장 트리를 형성한다고 가정하자.
만약 연결이 한 번이라도 중단된다
(예를 들어 누군가가 이 도메인에 있는 컴퓨터의 뒷면에서 통신 케이블을 꺼내기 때문에),
→ 이 부분 그래프는 더 이상 연결되지 않을 것임을 의미한다.
트리, 포레스트, 연결된 그래프의 단순한 속성은 여러 가지가 있다.
명제 13.11:
G: n개의 정점과 m개의 간선을 갖는 무향 그래프
• G가 연결되어 있으면 m ≥ n - 1이다.
• 만약 G가 트리라면 m = n-1 이다.
• G가 포레스트이면 m ≤ n-1이다.
13.1.1 그래프 ADT
추상적 자료형으로서 그래프:
그래프의 위치(position), 즉 꼭짓점과 간선에 저장되는 요소들의 컬렉션
따라서 요소들을 그래프의 꼭짓점이나 꼭짓점에 저장할 수 있다.
자바에서 이것은 Position 인터페이스를 확장하는
Vertex와 Edge 인터페이스를 각각 정의할 수 있다는 것을 의미한다.
이제 무방향 그래프의 꼭짓점과 간선 위치,
즉 간선이 모두 방향이 없는 그래프에 적합한 다음의 단순화된 그래프 ADT를 소개하자.
방향이 있는 간선을 처리하기 위한 추가적인 방법은 13.4절에서 논의한다.
vertices ():
그래프의 모든 정점에 대한 반복 가능한 컬렉션을 반환한다.
edges ():
그래프의 모든 모서리의 반복 가능한 컬렉션을 반환한다.
incidentEdges(v):
정점 v에 결합된 반복 가능한 간선 컬렉션을 반환한다:
opposite(v,e)
꼭짓점 v와 구별되는 간선 e의 끝 정점을 반환한다.
만약 e가 v에 입사하지 않으면 오류가 발생한다.
endVertices(e):
간선 e의 끝점을 저장하는 배열을 반환한다.
areAdjacent(v,w):
꼭짓점 v와 w가 인접해 있는지 테스트한다.
replace(v,x):
정점 v에 저장된 원소를 x로 대체한다.
replace(e,x):
모서리 e에 저장된 요소를 x로 대체한다.
insertVertex(x):
새 정점 저장 요소 x를 삽입하고 반환한다.
insertEdge(v, w,x):
끝 정점 v와 w가 있고 원소 x를 저장하는 새로운 방향 없는 간선을 삽입하고 반환한다.
removeVertex(v):
정점 v와 그 부속된 모든 간선을 제거하고 v에 저장된 요소를 반환한다.
removeEdge(e):
가장자리 e를 제거하고 e에 저장된 요소를 반환한다.
그래프 ADT를 실현하는 방법에는 여러 가지가 있다.
다음 절에서 그러한 세 가지 방법을 탐구한다.
13.2 그래프의 자료 구조
이 절에서는 일반적으로
1) 간선 리스트(edge list) 구조,
2) 인접 리스트(adjacency list) 구조,
3) 인접 행렬(adjacency matrix)
이라고 불리는 그래프를 표현하는 세 가지 일반적인 방법에 대해 논의한다.
세 가지 표현 모두에서 그래프의 정점을 저장하기 위해 컬렉션을 사용한다.
간선에 관해서는 처음의 두 구조와 나중의 구조 사이에 근본적인 차이가 있다.
1) 간선 리스트 구조와 2) 인접 리스트 구조는 그래프에 실제로 존재하는 간선만을 저장하는 반면,
3) 인접 행렬은 모든 정점 쌍에 대한 자리 표시자를 저장한다.
이 절에서 설명하겠지만,
이 차이는 n개의 정점과 m개의 간선을 갖는 그래프 G에서
1) 간선 리스트 또는 2) 인접 리스트 표현의 공간 사용은 O(n+m)이지만
3) 인접 행렬 표현의 공간 사용은 O(n^2)이다.
13.2.1 간선 리스트 구조
간선 리스트(edge list) 구조:
가장 효율적인 것은 아니지만 가장 단순한 그래프 G의 표현
원소 o를 저장하는 G의 정점 v는 정점 객체에 의해 명시적으로 표현된다.
이러한 모든 정점 객체들은 (배열 리스트 또는 노드 리스트와 같은) 집합 V에 저장된다.
예시) V가 배열 리스트이면 자연스럽게 정점들에 번호가 매겨지는 것으로 생각한다.
정점 객체
정점 v 저장 요소 o에 대한 정점 객체는 다음에 대한 인스턴스 변수를 갖는다:
• o에 대한 참조.
• 집합 V에서 정점-객체의 위치(또는 엔트리)에 대한 참조.
간선 리스트 구조의 구별되는 특징 - 간선들을 표현하는 방법
요소 o를 저장하는 G의 간선 e는 간선 객체에 의해 명시적으로 표현된다.
간선 객체들은 일반적으로 배열 리스트 또는 노드 리스트일 것인 집합 E에 저장된다.
간선 객체
간선 e 저장 요소 o에 대한 간선 객체는 다음에 대한 인스턴스 변수를 가진다:
• o에 대한 참조.
• e의 끝점 정점과 연결된 정점 객체에 대한 참조.
• 집합 E에서 간선-객체의 위치(또는 엔트리)에 대한 참조.
간선 리스트 구조 시각화
그림 13.3에서 그래프 G에 대한 간선 리스트 구조의 예를 보여준다.
그림 13.3:
(a) 그래프 G;
(b) G에 대한 간선 리스트 구조의 개략적인 표현.
우리는 원소 객체에 대한 실제적인 참조 대신에,
정점과 간선 객체에 저장된 원소들을 원소 이름으로 시각화한다.
이 구조를 간선 리스트 구조라고 부르는 이유
간선 집합 E의 가장 단순하고 일반적인 구현이 리스트와 함께 있기 때문이다.
그럼에도 불구하고,
간선과 관련된 특정 객체를 편리하게 탐색하기 위해서는
이것을 " 간선 리스트"이라고 부르지만,
E를 (요소를 키로, 간선을 값으로 저장하는) 딕셔너리로 구현하고자 할 수도 있다.
또한 같은 이유로 집합 V를 딕셔너리로 구현하고자 할 수도 있다.
여전히 전통에 따라 이 구조를 간선 리스트 구조라고 부른다.
간선 리스트 구조의 주요 특징
간선으로부터 입사되는 정점으로의 직접적인 접근을 제공한다.
이를 통해 endVertice(e) 및 opposite(v, e) 메소드에 대한 간단한 알고리즘을 정의할 수 있다.
간선 리스트 구조의 성능
그러나 간선 리스트 구조에 비효율적인 한 가지 메소드는 정점에 부속된 간선에 접근하는 것이다.
이 정점들의 집합을 결정하기 위해서는 집합 E의 모든 간선 객체들에 대한 철저한 검사가 필요하다.
→ 정점 v에 부속된 간선들을 결정하기 위해서는 간선 리스트의 모든 간선들을 검사하고,
각 간선들이 v에 부속된 것인지 확인해야 한다.
메소드 incidentEdges(v):
정점 v의 차수에 비례하는 시간이 아니라
그래프의 간선 수에 비례하는 시간으로 실행된다.
메소드 areAdjacent(v,w):
말단 정점 v와 w를 갖는 간선을 찾는 전체 간선 집합을 탐색해서
실제로 두 정점 v와 w가 인접하는지를 확인한다.
메소드 removeVertex:
게다가 정점을 제거하는 것은 부속된 간선들을 모두 제거하는 것을 포함하므로,
간선 집합 E를 완전히 탐색해야 한다.
표 13.1은 집합 V와 E가 이중 연결 리스트로 실현된다는 가정 하에서
그래프의 간선 리스트 구조 구현의 성능을 요약한 것이다(섹션 6.4.2).
표 13.1:
간선 리스트 구조로 구현된 그래프의 메소드의 실행 시간.
사용된 공간: O(n + m), n: 정점의 수, m: 간선의 수
| 연산 | 시간 |
| vertices | O(n) |
| edges | O(m) |
| endVertices, opposite | O(1) |
| incidentEdges, areAdjacent | O(m) |
| replace | O(1) |
| insertVertex, insertEdge, removeEdge | O(1) |
| removeVertex | O(m) |
그래프 ADT의 선택된 메소드에 대한 세부 정보는 다음과 같다:
• 메소드 vertices()과 edges()는 각각 V.iterator()와 E.iterator()를 호출하여 구현된다.
• 메소드 incidentEdges과 areAdjacent은 모두 O(m) 시간이 걸리므로,
정점 v에 결합된 간선을 결정하기 위해서는 모든 간선을 검사해야 한다.
• 집합 V와 E는 이중 연결 리스트로 구현된 리스트이므로,
O(1) 시간 내에 정점을 삽입하고, 간선을 삽입 및 제거할 수 있다.
• v에 발생하는 모든 간선을 찾아 제거하기 위해 모든 간선을 검사해야 하기 때문에
업데이트 메소드 removeVertex(v)는 O(m) 시간이 걸린다.
따라서, 간선 리스트 표현은 간단하지만 상당한 한계가 있다.
13.2.2 인접 리스트 구조
그래프 G에 대한 인접 리스트(adjacency list) 구조:
각 정점의 입사된 간선에 대한 직접적인 접근을 지원하는 간선 리스트 구조에 추가 정보를 추가한다.
이 접근법은 인접 리스트 구조를 사용하여
그래프의 정점과 간선의 수에 비례하는 양의 공간을 사용하더라도
간선 리스트 구조에서 가능한 것보다
훨씬 빠르게 그래프 ADT의 여러 방법을 구현할 수 있게 한다.
인접 리스트 구조는 간선 리스트 구조의 모든 구조적 구성 요소와 다음을 포함한다:
• 정점 객체 v는 v의 발생 집합이라고 불리는 집합 I(v)에 대한 참조를 보유하고 있으며,
이 집합의 원소들은 v에 결합된 간선들에 대한 참조를 저장한다.
• 말단 정점 v 및 w를 갖는 간선 e에 대한 간선 객체는
입사 컬렉션 I(v) 및 I(w)에서 간선 e와 연관된 위치(또는 엔트리)에 대한 참조를 보유한다.
이와 같은 그래프를 인접 리스트(adjacency list) 구조라고 부르는 이유
전통적으로 정점 v에 대한 입사집합 I(v)는 리스트이기 때문이다.
인접 리스트 구조는 간선에서 정점으로, 정점에서 입사 간선으로 직접 접근할 수 있다.
그림 13.4에서 그래프의 인접 리스트 구조를 보여준다.
그림 13.4:
(a) 그래프 G;
(b) G의 인접 리스트 구조를 도식적으로 나타낸다.
그림 13.3과 같이, 이름으로 컬렉션의 요소를 시각화한다.
인접 리스트 구조의 성능
O(1) 시간에 간선 리스트 구조로 구현할 수 있는
그래프 ADT의 모든 메소드도 본질적으로 동일한 알고리즘을 사용하여
인접 리스트 구조로 O(1) 시간에 구현할 수 있다.
또한 정점과 간선 사이의 접근을 양방향으로 제공할 수 있으므로
간선 리스트 구조 대신 인접 리스트 구조를 사용하여
다수의 그래프 메소드의 성능을 향상시킬 수 있다.
표 13.2는 그래프의 인접 리스트 구조 구현의 성능을 요약한 것으로,
집합 V와 E 및 정점의 발생 집합이 모두 이중 연결 리스트로 구현된다고 가정한 것이다.
정점 v에 대해 v의 발생 집합이 사용하는 공간은 v의 정도(degree),즉 O(deg(v))에 비례한다.
→ 명제 13.6에 의해 인접 리스트 구조의 공간 요구 조건: O(n + m)
표 13.2:
인접 리스트 구조로 구현된 그래프의 메소드의 실행 시간.
사용된 공간: O(n + m), n: 정점의 수, m: 간선의 수
| 연산 | 시간 |
| vertices | O(n) |
| edges | O(m) |
| endVertices, opposite | O(1) |
| incidentEdges(v) | O(deg(v)) |
| areAdjacent(v,w) | O(min(deg(v),deg(w))) |
| replace | O(1) |
| insertVertex, insertEdge, removeEdge | O(1) |
| removeVertex | O(deg(v)) |
간선 리스트 방식의 작업과 달리 인접 리스트 구조는 다음 메소드에 대해 향상된 실행 시간을 제공한다.
• 메소드 incidentEdges(v) - v의 입사 정점의 수에 비례하는 시간, 즉 O(deg(v)) 시간을 취한다.
• 메소드 areAdjacent(u,v) - u의 입사 수집과 v의 입사 수집 중 하나를 검사하여 수행할 수 있다.
둘 중 작은 것을 선택함으로써 O(min(deg(u),deg(v)) 실행 시간을 얻는다.
• 메소드 removeVertex(v) - O(deg(v)) 시간이 걸린다.
13.2.3 인접 행렬 구조
그래프의 인접 행렬(adjacency matrix) 구조:
인접 리스트 구조와 마찬가지로 추가적인 성분으로 간선 리스트 구조를 확장한다.
일정한 시간에 정점들의 쌍들 사이의 인접 관계를 결정할 수 있는
행렬(이차원 배열) A로 간선 리스트을 확장한다.
인접 행렬 표현
정점: 집합 {0,1,..., n - 1}의 정수
간선: 그러한 정수들의 쌍
이를 통해 2차원 n × n 배열 A의 셀들에 간선들에 대한 참조를 저장할 수 있다.
인접 행렬 표현은 구체적으로 다음과 같이 간선 리스트 구조를 확장한다 (그림 13.5 참조):
• 꼭짓점 객체 v는 v의 인덱스라고 불리는 0,1,..., n - 1 범위의 고유한 정수 i를 저장한다.
• 2차원 n × n 배열 A를 유지해서 셀 A[i,j]가 존재한다 → 간선 (v, w)에 대한 기준을 유지한다.
v: 인덱스가 i인 정점, w: 인덱스가 j인 정점
그러한 간선이 존재하지 않는다 → A[i,j] = null
그림 13.5:
(a) 평행 모서리가 없는 그래프 G;
(b) G에 대한 단순화된 인접 행렬 구조의 도식적 표현.
인접 행렬 구조의 성능
평행 간선을 갖는 그래프의 경우
(인접 행렬 표현을 확장하여 A [i, j]가 연관된 간선 (v, w)에 대한 포인터를 저장하는 대신)
v에서 w까지의 모든 간선을 저장하는 입사집합 I (v, w)에 대한 포인터를 저장해야 한다.
우리가 고려하는 대부분의 그래프는 단순하기 때문에 여기서는 이 문제를 고려하지 않을 것이다.
메소드 areAdjacent(v, w):
(단순한) 인접 행렬 A를 통해 O(1) 시간에 수행할 수 있다.
이 실행 시간은 정점 v와 w에 접근하여 각각의 인덱스 i와 j를 결정한 다음,
A[i, j]가 null인지 아닌지를 테스트함으로써 달성된다.
메소드 areAdjacent의 최적 성능은 공간 사용의 증가로 상쇄되지만,
현재 O(n^2)인 다른 방법들의 실행 시간에 대응된다.
메소드 incidentEdges(v):
이제 배열 A의 전체 행 또는 열을 검사하여 O(n) 시간에 실행할 것을 요구한다.
모든 정점 삽입 또는 삭제:
이제 크기가 더 크거나 더 작은 전체 배열 A를 생성해야 하며,
이는 O(n2) 시간이 걸린다.
표 13.3은 그래프의 인접 행렬 구조 구현의 성능을 요약한 것이다.
이 표를 통해 인접 행렬 구조가 공간상 인접 행렬보다 우수하며,
메소드 areAdjacent을 제외한 모든 메소드에서 시간적으로 우수함을 알 수 있다.
표 13.3: 인접 행렬로 구현된 그래프의 실행 시간.
| 연산 | 시간 |
| vertices | O(n) |
| edges | O(m) |
| endVertices, opposite, areAdjacent | O(1) |
| incidentEdges(v) | O(n + deg(v)) |
| replace, insertEdge, removeEdge | O(1) |
| insertVertex, removeVertex | O(n^2) |
역사적으로 부울 인접 행렬은 그래프에 사용된 첫 번째 표현이었다
(A[i, j] = (i, j가 간선인 경우에만 참임).
그러나 인접 행렬은 수학적 구조로서 자연스러운 매력을 가지고 있기 때문에
(예를 들어, 무향 그래프는 대칭 인접 행렬을 가지고 있다),
인접 리스트 구조는 대부분의 알고리즘에서 더 빠른 방법과 공간 효율성으로 인해
컴퓨팅에서 자연스러운 매력을 가지고 있다.
우리가 조사하는 그래프 알고리즘은 대부분 인접 리스트 표현을 사용하여
저장된 그래프에 작용할 때 효율적으로 실행될 것이다.
그러나 경우에 따라 트레이드오프가 발생하는데,
여기서 간선이 적은 그래프는 인접 리스트 구조로 가장 효율적으로 처리되고,
간선이 많은 그래프는 인접 행렬 구조로 가장 효율적으로 처리된다.
13.3 그래프 횡단면
순회(traversal): 그래프의 모든 꼭짓점과 모서리를 조사하여 체계적으로 그래프를 탐색하는 절차
13.3.1 깊이 우선 탐색
깊이 우선 탐색(DFS)의 활용
깊이 우선 탐색은 한 정점에서 다른 정점으로 가는 경로가 있는지,
그래프가 연결되어 있는지 여부 등 그래프의 여러 특성을 테스트하는 데 유용하다.
방향이 없는 그래프 G에서 깊이 우선 탐색은
길을 잃지 않고 줄과 물감통을 들고 미로를 헤매는 것과 유사하다.
1. G의 특정한 시작 정점에서 시작하는데,
이를 초기화하기 위해 문자열의 한쪽 끝을 s로 고정하고 s를 "visited"된 것으로 페인트한다.
정점 s: 현재의 정점 u
2. 현재의 정점 u에 결합된 (임의) 간선 (u,v)를 고려하여 G를 횡단한다.
2-1) 간선 (u,v)가 이미 방문한 (즉, 그림을 그린) 정점 v로 인도한다면 → 즉시 정점 u로 되돌아간다.
2-2) 간선 (u,v)가 방문하지 않은 정점 v로 인도한다면
→ 문자열을 풀고 v로 간다.
v를 "visited"된 것으로 페인트하고 나서 위의 계산을 반복하면서 현재의 정점으로 만든다.
3. 결국 우리는 "데드-엔드", 즉 현재의 정점 u에 도달하여
우리에 결합된 모든 간선들이 이미 방문한 정점들로 이어질 것이다.
4. u에 결합된 임의의 간선을 취하는 것은 우리를 u로 되돌아가게 할 것이다.
5. 이 난국에서 벗어나기 위해,
우리는 문자열을 뒤로 젖히고,
우리를 u로 가져온 간선을 따라 이전에 방문했던 정점 v로 되돌아간다.
6. 그런 다음 현재 정점 v를 만들어서
이전에 보지 못한 v에 결합된 간선에 대해 위의 계산을 반복한다.
7. 만일 v에 결합된 모든 간선이 방문된 정점으로 이어진다면,
우리는 다시 문자열을 걷어 올려 v에 도달하기 위해 온 정점으로 되돌아가고,
그 정점에서 절차를 반복한다.
8. 따라서 아직 탐험되지 않은 간선을 찾을 때까지 지금까지 추적한 경로를 따라 뒤로 되돌아가고,
그러한 간선 하나를 선택하여 순회를 계속한다.
9. 이 과정은 다시 시작 정점 s로 되돌아가고,
s에 결합된 더 이상 탐험되지 않은 간선이 없을 때 종료된다.
이 간단한 과정은 G의 모든 모서리를 가로지른다. (그림 13.6 참조)
그림 13.6: 정점 A에서 시작하는 그래프에서 깊이 우선 탐색 순회의 예를 보여준다.
발견 간선은 실선으로 표시되고, 뒤 간선은 점선으로 표시된다:
(a) 입력 그래프;
(b) A에서 뒤 간선 (B,A)가 타격될 때까지 추적되는 발견 간선의 경로;
(c) 막다른 골목인 F에 도달;
(d) C로 역추적하고, 간선 (C,G)로 재개하고, G로 역추적한 후 또 다른 막다른 골목인 J;
(e) G로 역추적한 후
(f) N으로 역추적한 후.
탐색 간선 및 후면 간선
DFS의 순회를 시각화할 수 있는데,
이는 새로운 정점을 발견하는 데 사용되는 간선들인
발견 간선(discovery edge) 또는 트리 간선(tree edge)을
역행 간선(back edge)이라고 부르는 간선들과 구분하는 것이다.
발견 간선(discovery edge): 문자열을 순회할 때 푸는 간선
역행 간선(back edge): 문자열을 열지 않고 바로 돌아오는 간선
앞으로 보게 되겠지만,
발견 간선들은 시작 정점 s의 연결된 구성 요소의 신장 트리를 형성한다.
우리는 트리가 시작 정점에 루트를 두고 있다고 가정할 때,
그러한 간선들은 각각 트리의 한 정점에서 트리의 조상들 중 하나로 되돌아가기 때문에
이 트리에 없는 간선들을 "역행 간선"이라고 부른다.
정점 v에서 시작하는 DFS 순회에 대한 의사 코드는 문자열과 페인트를 사용한 우리의 유추를 따른다.
우리는 문자열 유추를 구현하기 위해 재귀를 사용하고,
정점이나 간선이 탐색되었는지 아닌지를 결정하고,
간선을 발견 간선 또는 역행 간선으로 라벨링하는 메커니즘(페인트 유추)을 가지고 있다고 가정한다.
이 메커니즘은 추가적인 공간을 필요로 하며, 알고리즘의 실행 시간에 영향을 줄 수 있다.
재귀적 DFS 알고리즘에 대한 의사 코드 설명은 코드 조각 13.1에 나와 있다.
코드 조각 13.1: DFS 알고리즘.
Algorithm DFS(G, v):
Input: A graph G and a vertex v of G
Output: A labeling of the edges in the connected component of v as discovery
edges and back edges
label v as visited
for all edge e in G.incidentEdges(v) do
if edge e is unvisited then
w ← G.opposite(v,e)
if vertex w is unexplored then
label e as a discovery edge
recursively call DFS(G,w)
else
label e as a back edge
깊이 우선 탐색 알고리즘에 대해 우리가 할 수 있는 많은 관찰이 있는데,
그 중 많은 것은 DFS 알고리즘이 무향 그래프 G의 간선을
발견 간선와 역행 간선의 두 그룹으로 분할하는 방식에서 비롯된다.
예를 들어,역행 간선들은 항상 정점 v와 이전에 방문한 정점 u를 연결하기 때문에,
각각의 역행 간선은 U에서 v까지의 발견 간선과 뒤의 간선 (u, v)으로 구성된 G에서의 순환을 의미한다.
명제 13.12:
G: 정점 s에서 시작하는 DFS 순회가 수행된 무방향 그래프
그러면 순회는 s의 연결된 성분의 모든 정점을 방문하고,
발견 간선들은 s의 연결된 성분의 신장 트리를 형성한다.
정당화: s의 연결된 성분이 방문하지 않은 꼭짓점이 적어도 하나 있다고 하고,
s에서 v로 가는 어떤 경로의 첫 번째 방문하지 않은 꼭짓점이 w라고 하자.
w는 이 경로의 첫 번째 방문하지 않은 꼭짓점이므로 방문한 이웃 u가 있다.
그러나 u를 방문했을 때 우리는 간선 (u,w)를 고려했음에 틀림없으므로
w가 방문하지 않은 것은 옳을 수 없다.
따라서 s의 연결된 성분에는 방문하지 않은 꼭짓점이 없다.
방문하지 않은 꼭짓점에 갈 때는 꼭짓점만 표시하기 때문에,
절대 발견 꼭짓점들과 사이클을 형성하지 않을 것이다.
게다가 이것은 방금 본 것처럼,
깊이 우선 탐색이 s의 연결된 성분의 각 꼭짓점을 방문하기 때문에 신장 트리이다
실행 시간의 관점에서 깊이 우선 탐색은 그래프를 가로지르는 효율적인 방법이다.
DFS는 각 정점에서 한 번씩 정확히 호출되고,
모든 간선은 각 정점에서 한 번씩 정확히 두 번 검사된다.
따라서 ns개의 정점과 ms개의 간선이 연결된 정점 s의 구성요소에 있다면,
다음 조건들이 만족된다면, s에서 시작하는 DFS는 O(ns + ms) 시간으로 실행된다:
• 그래프는 다음 메소드를 활용한 자료 구조로 표현된다.
- incidentEdges(v): 반복 가능한 컬렉션을 생성 및 반복하는 데 O(degree(v)) 시간이 걸리고,
- opposite(v,e): O(1) 시간이 소요된다.
인접 리스트 구조는 그러한 구조 중 하나이지만 인접 행렬 구조는 그렇지 않다.
• 탐색된 정점이나 간선을 "표시"하고,
정점이나 간선이 O(1) 시간에 탐색되었는지를 시험하는 방법이 있다.
다음 절에서 이 목표를 달성하기 위해 DFS를 구현하는 방법에 대해 논의한다.
위의 가정들을 고려할 때, 여러 흥미로운 문제들을 해결할 수 있다.
명제 13.13:
G: n개의 정점과 m개의 간선을 갖는 그래프로 인접 리스트
G의 DFS 순회는 O(n + m) 시간에 수행될 수 있고,
O(n + m) 시간에 다음 문제를 해결하는 데 사용될 수 있다:
• G가 연결되었는지 테스트 중이다.
• G가 연결되어 있다면, G의 신장 트리를 계산하는 것이다.
• G의 연결된 구성 요소를 계산한다.
• 주어진 G의 두 꼭짓점 사이의 경로를 계산한다.
• G 안의 사이클을 계산하거나 G가 사이클이 없다는 것을 보고한다.
명제 13.13의 정당성은 약간의 알고리즘을 사용하는 것에 기초한다
DFS 알고리즘을 서브루틴으로 수정한 버전이다.
13.3.2 깊이 우선 탐색 구현
앞서 언급한 바와 같이 그래프를 표현하기 위해 사용하는 자료 구조는
DFS 알고리즘의 성능에 영향을 미친다.
예시1)
인접 리스트를 사용하면
n개의 정점과 m개의 간선을 갖는 그래프를 통과할 때
O(n + m)의 실행 시간을 얻을 수 있다.
예시2)
인접 행렬을 사용하면
n개의 incidentEdges 메소드로 호출하는 데 각각 O(n) 시간이 걸리므로
O(n^2)의 실행 시간이 발생한다.
그래프의 밀도가 높은(dense) 경우 = O(n^2)개의 간선에 가까운 경우,
이 두 선택의 차이는 O(n^2) 시간에 실행되므로 작다.
그러나 그래프가 희박한(sparse) 경우 = O(n)개의 간선에 가까운 경우,
인접 행렬 접근 방식이 인접 리스트 접근 방식보다 훨씬 느릴 것이다.
정점과 간선이 표현되는 방식
특히 정점과 간선을 방문했거나 방문하지 않은 것으로 표시하는 방법이 필요하다.
간단한 해결책은 두 가지가 있지만 각각 단점이 있다:
• 해결책1: DFS 알고리즘은 explored 필드를 포함하도록 정점과 간선 객체를 구축할 수 있으며,
이를 마킹에 사용할 수 있다.
장점: 이 접근법은 매우 간단하고 일정한 시간 마킹과 비마킹을 지원한다.
단점: 1) DFS를 염두에 두고 그래프를 설계한다고 가정하지만 항상 유효하지는 않을 것이다.
2) 불필요하게 DFS를 explored 필드를 갖는 정점을 갖는 그래프로 제한한다.
→ 임의의 그래프를 입력으로 사용할 수 있는 일반적인 DFS 알고리즘을 원한다면 한계가 있다.
• 해결책2: DFS 알고리즘을 수행하는 동안
탐색된 모든 정점과 간선을 저장하기 위해 보조 해시 테이블을 사용할 수 있다.
장점: 그래프의 위치에 특별한 필드를 필요로 하지 않는다는 점에서 일반적이다.
단점: 1) 정점의 간선을 표시하고 표시하지 않는 최악의 경우 일정한 시간을 달성하지 못한다.
2) 일정한 예상 시간에서의 표시(삽입) 및 테스트(찾기) 연산만을 지원한다(9.2절 참조).
다행히 이 두 극단 사이에는 중간 지대가 존재한다.
데코레이터 패턴
DFS 순회에서 탐색된 정점들을 표시하는 것은
데코레이터(decorator) 소프트웨어 엔지니어링 디자인 패턴의 한 예이다.
이 패턴은 기존의 객체들에 장식(decoration)(=속성(attribute))을 추가하는 데 사용된다.
각각의 장식은 이 장식을 식별하는 키와 그 키와 연관된 값에 의해 식별된다.
장식의 사용은 그러한 변수들을 정상적으로 갖지 않는 객체들에
추가적인 변수들 또는 임시 스크래치 데이터를 추가하기 위한
일부 알고리즘들 및 데이터 구조들의 필요에 의해 동기부여된다.
→ 장식: 객체에 동적으로 부착될 수 있는 키-값 쌍
DFS 예에서, 탐색된 장식과 부울 값을 갖는 "장식 가능한" 정점들과 간선들을 갖기를 원한다.
그래프 꼭짓점 장식 가능으로 만들기
어떤 위치에 대한 장식자 패턴을 장식할 수 있게 함으로써 구현할 수 있다.
이것은 예를 들어 필요로 할 라벨의 종류를 미리 알 필요 없이
꼭짓점과 모서리에 라벨을 추가할 수 있게 해준다.
단순히 정점과 가장자리가 위치 ADT와 맵 ADT를 모두 상속하는
장식 가능한 위치(decorable position) ADT를 구현하도록 요구할 수 있다(9.1절).
즉, 장식 가능한 위치 ADT의 메소드는 위치 ADT와 맵 ADT의 방법의 결합,
즉 size() 및 is Empty() 메소드 외에도 장식 가능한 위치는 다음을 지원할 것이다:
element():
이 위치에 저장된 요소를 반환한다.
put(k,x):
장식 값 x를 키 k에 매핑하고,
k에 대해서는 이전 값을 반환하거나,
k에 대해서는 새로운 값이면 null을 적용한다.
get(k):
k에 할당된 장식 값 x를 가져오거나, k에 대한 매핑이 없으면 null을 얻는다.
remove(k):
k에 대한 장식 매핑을 제거하고, 이전 값을 반환하거나, 없으면 null이다.
entries():
이 위치에 대한 모든 키-장식 쌍을 반환한다.
장식 가능한 위치 p의 맵 메소드는 p의 장식에 접근하고 설정하는 간단한 메커니즘을 제공한다.
p.get(k) - 키 k인 장식의 값을 얻는다.
p.put(k,x)- 키 k인 장식의 값을 x로 설정
또한 키 k는 DFS 알고리즘이 생성할 수 있는 특별한 explored 객체를 포함하여 모든 객체가 될 수 있다.
코드 조각 13.2에서 이러한 ADT를 정의하는 자바 인터페이스를 보여준다.
요소와 맵을 저장하는 객체로 장식 가능한 위치를 구현할 수 있다.
원칙적으로, 장식 가능한 위치의 메소드들의 실행 시간은 기본 맵의 구현에 의존한다.
그러나, 대부분의 알고리즘들은 작은 일정한 수의 장식들을 사용한다.
따라서, 장식 가능한 위치 메소드들은 O(1) 최악의 경우 시간에서 실행될 것이다.
코드 조각 13.2:
장식 가능한 위치에 대한 ADT를 정의하는 인터페이스이다.
장식의 종류를 미리 알 수 없고
많은 다른 종류의 객체를 장식으로 허용하기를 원하기 때문에
상속된 맵 메소드에 대해 일반 매개 변수화된 타입을 사용하지 않는다는 점에 유의하자.
public interface DecorablePosition<E>
extends Position<E>, Map<Object,Object> {
} // no new methods needed - this is a mixture of Position and Map
전체 DFS 순회 알고리즘은 코드 조각 13.3과 같이 장식 가능한 위치를 사용하여
더 상세하게 설명할 수 있다.
코드 조각 13.3: 모서리와 꼭짓점을 장식할 수 있는 그래프의 DFS.
Algorithm DFS(G, v, k):
Input: A graph G with decorable vertices and edges, a vertex v of G, and a
decoration key k
Output: A decoration of the vertices of in the connected component of v with
key k and value VISITED and of the edges in the connected component of
v with key k and values DISCOVERY and BACK, according to a depth-first
search traversal of G
v.put(k, VISITED)
for all edge e in G.incidentEdges(v) do
if e.get(k) = null then
w ← G.opposite(v,e)
if w.get(k) = null then
e.put(k, DISCOVERY)
DFS(G,w,k)
else
e.put(k, BACK)
Java에서의 일반적인 DFS 구현
코드 조각 13.4 및 13.5에서는
일반 클래스인 DFS를 사용한 일반적인 깊이 우선 검색 순회의 자바 구현을 보여준다.
execute 메소드는 그래프, 시작 정점 및 필요한 보조 정보를 입력으로 가져온 다음 그래프를 초기화하고
재귀적 메소드인 dfsTraversal을 호출하여 DFS 순회를 활성화한다.
우리의 구현은 정점과 간선이 장식 가능한 위치라고 가정하고,
정점과 간선이 방문되었는지 여부를 구분하기 위해 장식을 사용한다.
DFS 클래스는 DFS 순회 중에 특별한 작업을 수행할 수 있도록
다음과 같은 메소드를 포함한다:
• setup(): dfsTraversal()에 대한 DFS 순회 호출을 수행하기 전에 호출된다.
• initResult(): dfsTraversal() 실행 시작 시 호출된다.
• startVisit(v): v의 방문을 시작할 때 호출된다.
• traverseDiscovery(e,v): v를 벗어난 발견 간선이 순회할 때 호출된다.
• traverseBack(e,v): v를 벗어난 역행 간선이 순회될 때 호출된다.
• isDone(): 순회를 조기에 종료할지 여부를 결정하기 위해 호출된다.
• finishVisit(v): v에서 탐색이 끝나면 호출된다.
• result(): dfsTraversal의 출력을 반환하기 위해 호출된다.
• finalResult(r): dfsTraversal의 출력 r이 주어지면 execute 메소드의 출력을 반환하기 위해 호출된다.
코드 조각 13.4-13.5:
일반적인 DFS 순회를 수행하는 클래스 DFS의 인스턴스 변수 및 지원 메소드.
visit, unVisited, 그리고 isVisited 메소드는
장식 가능한 위치에 사용되는 V 매개변수 또는 E 매개변수와 일치할 수 있는
와일드카드 기호 "?"를 사용하여
매개변수화된 장식 가능한 위치를 사용하여 구현된다.
그래프의 일반적인 DFS 순회를 수행하는 클래스 DFS의 주 템플릿 메소드 dfsTraversal.
/** Generic DFS traversal of a graph using the template method pattern.
* Parameterized types:
* V, the type for the elements stored at vertices
* E, the type for the elements stored at edges
* I, the type for the information object passed to the execute method
* R, the type for the result object returned by the DFS
*/
public class DFS<V, E, I, R> {
protected Graph<V, E> graph; // The graph being traversed
protected Vertex<V> start; // The start vertex for the DFS
protected I info; // Information object passed to DFS
protected R visitResult; // The result of a recursive traversal call
protected static Object STATUS = new Object(); // The status attribute
protected static Object VISITED = new Object(); // Visited value
protected static Object UNVISITED = new Object(); // Unvisited value
/** Mark a position (vertex or edge) as visited. */
protected void visit(DecorablePosition<?> p) { p.put(STATUS, VISITED); }
/** Mark a position (vertex or edge) as unvisited. */
protected void unVisit(DecorablePosition<?> p) { p.put(STATUS, UNVISITED); }
/** Test if a position (vertex or edge) has been visited. */
protected boolean isVisited(DecorablePosition<?> p) {
return (p.get(STATUS) == VISITED; }
}
/** Setup method that is called prior to the DFS execution. */
protected void setup() { }
/** Initializes result (called first, once per vertex visited). */
protected void initResult() { }
/** Called when we encounter a vertex (v). */
protected void startVisit(Vertex<V> v) { }
/** Called after we finish the visit for a vertex (v). */
protected void finishVisit(Vertex<V> v) { }
/** Called when we traverse a discovery edge (e) from a vertex (from). */
protected void traverseDiscovery(Edge<E> e, Vertex<V> from) { }
/** Called when we traverse a back edge (e) from a vertex (from). */
protected void traverseBack(Edge<E> e, Vertex<V> from) { }
/** Determines whether the traversal is done early. */
protected boolean isDone() { return false; /* default value */}
/** Return a result of a visit (if needed). */
protected R result() { return null; /* default value */}
/** Return the final result of the DFS execute method. */
protected R finalResult(R r) { return r; /* default value */}
/** Execute a depth final search traversal on graph g, starting
* from a start vertex s, passing in a information object (in) */
public R execute(Graph<V, E> g, Vertex<V> s, I in) {
graph = g;
start = s;
info = in;
for(Vertex<V> v: graph.vertices()) unVisit(v); // mark vertices an unvisited
for(Edge<E> e: graph.edges()) unVisit(e); // mark edges an unvisited
setup(); // perform any necessary setup prior to DFS traversal
return finalResult(dfsTraversal(start));
}
/** Recursive template method for a generic DFS traversal. */
protected R dfsTraversal(Vertex<V> v) {
initResult();
if (!isDone())
startVisit(v);
if (!isDone())
visit(v);
for(Edge<E> e: graph.incidentEdges(v)) {
if (!isVisited(e)) {
// found an unexplored edge, explore it
visit(v);
Vertex<V> w = graph.opposite(v, e);
if (!isVisited(w)) {
// w is unexplored, this is a discovery edge
traverseDiscovery(e, v);
if (isDone()) break;
visitResult = dfsTraversal(w); // get result from DFS-tree child
if (isDone()) break;
}
else {
// w is explored, this is a back edge
traverseBack(e, v);
if (isDone()) break;
}
}
}
}
if (!isDone())
finishVisit(v);
return result();
}
} // end of the DFS class
DFS용 템플릿 메소드 패턴 사용
DFS 클래스는 템플릿 메소드 패턴에 기초한 것으로,
특정 단계를 재정의함으로써 특화될 수 있는 일반적인 계산 메커니즘을 설명한다(섹션 7.3.7 참조).
순회하는 동안 이미 방문한 정점과 간선을 식별하는 메소드: isVisited, visit, unVisit
흥미로운 일을 하기 위해서 DFS를 확장하고 보조 메소드들 중 일부를 재정의해야 한다.
이 접근 방식은 템플릿 메소드 패턴과 일치한다.
코드 조각 13.6부터 13.9까지에서 DFS 순회의 일부 응용 프로그램을 보여준다.
클래스 ConnectivityDFS(코드 조각 13.6):
그래프가 연결되어 있는지 여부를 테스트한다.
정점에서 시작하는 DFS 순회에 의해 도달할 수 있는 정점들을 카운트하고
이 수를 그래프의 전체 정점 수와 비교한다.
코드 조각 13.6: 그래프가 연결되어 있는지 테스트하기 위한 클래스 DFS의 전문화.
/** This class specializes DFS to determine whether the graph is connected. */
public class ConnectivityDFS<V, E> extends DFS <V, E, Object, Boolean> {
protected int reached;
protected void setup() { reached = 0; }
protected void startVisit(Vertex<V> v) { reached++; }
protected Boolean finalResult(Boolean dfsResult) {
return new Boolean(reached == graph.numVertices());
}
}
클래스 ComponentsDFS(코드 조각 13.7):
그래프의 연결된 컴포넌트를 찾는다.
데코레이터 패턴을 사용하여
각 정점에 연결된 컴포넌트 번호를 라벨링하고
찾은 연결된 컴포넌트의 수를 반환한다.
코드 조각 13.7: 연결된 컴포넌트들을 계산하기 위한 DFS의 전문화.
/** This class extends DFS to compute the connected components of a graph. */
public class ConnectivityDFS<V, E> extends DFS <V, E, Object, Boolean> {
protected int reached;
protected void setup() { reached = 0; }
protected void startVisit(Vertex<V> v) { reached++; }
protected boolean finalResult(Boolean dfsResult) {
for (Vertex<V> v : graph.vertices()) // check for any unvisited vertices
if (v.get(STATUS) == UNVISITED) {
compNumber += 1; // we have found another connected component
dfsTraversal(v); // visit all the vertices of this component
}
return compNumber;
}
}
클래스 FindPathDFS(코드 조각 13.8):
주어진 시작 정점과 대상 정점의 쌍 사이의 경로를 찾는다.
시작 정점에서 시작하는 깊이 우선 탐색 횡단을 수행한다.
시작 정점에서 현재 정점까지의 탐색 간선의 경로를 유지한다.
탐색되지 않은 정점을 만나면 → 경로의 끝에 추가한다.
정점 처리를 마치면 → 경로에서 제거한다.
대상 정점을 만나면 → 순회가 종료되고, 경로는 반복 가능한 정점과 간선의 집합(그래프의 두 가지 위치)으로 반환된다.
이 클래스에 의해 발견된 경로는 탐색 간선으로 구성된다.
코드 조각 13.8:
시작 정점과 대상 정점 사이의 경로를 찾기 위한 클래스 DFS의 전문화.
/** Class specializing DFS to find a path between a start vertex and a target
* vertex. It assumes the target vertex is passed as the info object to the
* execute method. It returns an iterable list of the vertices and edges
* comprising the path from start to info. The returned path is empty if
* info is unreachable from start. */
public class FindPathDFS<V, E>
extends DFS <V, E, Vertex<V>, Iterable<Position>> {
protected PositionList<Position> path;
protected boolean done;
/** Setup method to initialize the path. */
public void setup() {
path = new NodePositionList<Position>();
done = false;
}
protected void startVisit(Vertex<V> v) {
path.addLast(v); // add vertex v to path
if (v == info)
done = true;
}
protected void finishVisit(Vertex<V> v) {
path.remove(path.last()); // remove v from path
if (!path.isEmpty()) // if v is not the start vertex
path.remove(path.last()); // remove discovery edge into v from path
}
protected void traverseDiscovery(Edge<E> e, Vertex<V> from) {
path.addLast(e); // add edge e to the path
}
protected boolean isDone() {
return done;
}
public Iterable<Position> finalResult(Iterable<Position> r) {
return path;
}
}
클래스 FindCycleDFS(코드 조각 13.9):
if 역행 간선이 발견되면 →
끝나는 v에서 깊이 우선 탐색 순회를 수행하여
주어진 정점 v의 연결된 구성 요소에서 사이클을 찾는다.
찾은 역행 간선에 의해 형성된 사이클에서 정점과 간선의 반복 가능한 집합을 반환한다.
코드 조각 13.9: 시작 정점의 연결된 컴포넌트에서 사이클을 찾기 위한 클래스 DFS의 전문화.
/** This class specializes DFS to find a cycle. */
public class FindCycleDFS<V, E>
extends DFS <V, E, Object, Iterable<Position>> {
protected PositionList<Position> cycle; // sequence of edges of the cycle
protected Vertex<V> cycleStart;
public void setup() {
path = new NodePositionList<Position>();
done = false;
}
protected void startVisit(Vertex<V> v) { cycle.addLast(v); }
protected void finishVisit(Vertex<V> v) {
cycle.remove(cycle.last()); // remove v from cycle
if (!cycle.isEmpty()) cycle.remove(cycle.last()); // remove edge into v from cycle
}
protected void traverseDiscovery(Edge<E> e, Vertex<V> from) {
cycle.addLast(e); // add edge e to the path
}
protected void traverseBack(Edge<E> e, Vertex<V> from) {
cycle.addLast(e); // back edge e to the path
cycleStart = graph.opposite(from, e);
cycle.addLast(cycleStart); // first vertex completes the cycle
done = true;
}
protected boolean isDone() { return done; }
public Iterable<Position> finalResult(Iterable<Position> r) {
// remove the vertices and edges from start to cycleStart
if (!cycle.isEmpty())
for (PositionList<Position> p: cycle.positions()) {
if (p.element() == cycleStart)
break;
cycle.remove(p); // remove vertex from cycle
}
}
return cycle; // list of the vertices and edges of the cycle
}
}
13.3.3 너비 우선 탐색
이 절에서는 너비 우선 탐색(BFS) 순회 알고리즘에 대해 알아본다.
BFS는 DFS와 마찬가지로 그래프의 연결된 부분을 순회하며,
이를 통해 유용한 신장 트리를 정의한다.
그러나 BFS는 DFS보다 덜 "모험적"이다.
BFS: 그래프를 라운드로 진행하고 정점을 레벨(level)로 나눈다.
BFS는 문자열과 페인트를 사용하는 순회라고 생각할 수도 있으며,
BFS는 문자열을 더 보수적으로 풀어낸다.
BFS는 레벨 0인 정점 s에서 시작하여 우리의 문자열에 대한 "앵커"를 정의한다.
1. 첫 번째 라운드에서, 하나의 간선의 길이만큼 문자열을 내보내고
더 이상 문자열을 펼치지 않고 도달할 수 있는 모든 정점을 방문한다.
이 경우, 우리는 시작 정점 s에 인접한 정점을 방문하여 "방문"한 것으로 그림을 그리는데,
이 정점들은 레벨 1에 배치된다.
2. 두 번째 라운드에서, 두 개의 간선의 길이만큼 문자열을 펼치고
더 이상 문자열을 펼치지 않고 도달할 수 있는 모든 새로운 정점을 방문한다.
레벨 1의 정점에 인접하여 이전에 레벨에 할당되지 않은
이 새로운 정점들은 레벨 2 등에 배치된다.
3. BFS 횡단은 모든 정점을 방문하면 종료된다.
정점 s에서 시작하는 BFS에 대한 의사 코드는 코드 조각 13.10에 나타나 있다.
보조 공간을 사용하여
간선에 라벨을 붙이고, 방문한 정점을 표시하며, 레벨과 연관된 컬렉션을 저장한다.
즉, 컬렉션 L0, L1, L2 등은 레벨 0, 레벨 1, 레벨 2 등에 있는 정점을 저장한다.
이러한 컬렉션은 예를 들어 큐로 구현될 수 있다.
또한 BFS가 비재귀적일 수 있도록 한다.
코드 조각 13.10: BFS 알고리즘.
Algorithm BFS(s):
initialize collection L0 to contain vertex s
i ← 0
while L1 is not empty do
create collection L(i+1) to initially be empty
for all vertex v in Li do
for all edge e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.opposite(v,e)
if vertex w is unexplored then
label e as a discovery edge
insert w into L(i+1)
else
label e as a back edge
i ← i + 1
그림 13.7에 BFS 횡단을 예시한다.
그림 13.7: 너비 우선 검색 순회의 예로,
한 정점에 부속된 간선을 인접한 정점의 알파벳 순서로 탐색한다.
발견 간선은 실선으로 표시되고
교차 간선은 점선으로 표시된다:
(a) 횡단 전 그래프;
(b) 레벨 1의 발견;
(c) 레벨 2의 발견;
(d) 레벨 3의 발견;
(e) 레벨 4의 발견;
(f) 레벨 5의 발견.
BFS 접근법의 좋은 특성 중 하나는
BFS 순회를 수행할 때
각 정점을 시작 정점에서 가장 짧은 경로의 길이(간선의 수 기준)로
레이블을 지정할 수 있다는 것이다.
특히, 정점 v가 정점에서 시작하는 BFS에 의해 레벨 i에 놓이면,
s에서 v로의 최단 경로의 길이가 된다.
DFS와 마찬가지로, BFS의 순회를 시각화할 수 있는데,
이는 순회 중에 탐색되는 방향을 따라 간선을 배향하고,
발견 간선과 교차 간선을 구별함으로써 가능하다.
발견 간선(discovery edge): 새로운 정점을 발견하는 데 사용되는 간선
교차 간선(cross edge): 정점으로 이어지는 간선
(그림 13.7f 참조)
BFS 트리: BFS에서 발견 간선이 형성하는 신장 트리
이 경우에는 트리가 아닌 간선을 "역행 간선"라고 부르지 않지만,
어느 간선도 하나의 정점을 그것의 조상 중 하나에 연결하지 않기 때문이다.
모든 트리가 아닌 간선은 하나의 정점 v를 v의 조상도 그 후손도 아닌 다른 정점에 연결한다.
BFS 순회 알고리즘은 몇 가지 흥미로운 속성을 가지고 있으며,
그 중 일부는 다음 명제에서 탐구한다.
명제 13.14:
G: 정점에서 시작하는 BFS 순회가 수행된 무방향 그래프
• 순회는 s의 연결된 성분의 모든 정점을 방문한다.
• 발견 간선들은 s의 연결된 구성요소인 BFS 트리라고 부르는 신장 트리 T를 형성한다.
• 레벨 i의 각각의 정점 v에 대하여,
s와 v 사이의 BFS 트리 T의 경로는 i개의 간선을 가지며,
s와 v 사이의 임의의 다른 G의 경로는 적어도 i개의 간선을 가진다.
• 만약 (u, v)가 BFS 트리에 없는 간선이라면, u와 v의 레벨 수는 많아야 1만큼 다르다.
BFS의 실행시간에 대한 분석은 DFS의 실행시간에 대한 분석과 유사하며,
이는 다음과 같은 의미를 내포하고 있다.
명제 13.15: G: 인접 리스트 구조로 표현된 n개의 정점과 m개의 간선을 갖는 그래프
G의 BFS 순회 시간: O(n+m)
또한 다음과 같은 문제들을 위해 BFS 기반의 O(n+m) 시간 알고리즘이 존재한다:
• G가 연결되었는지 테스트 중이다.
• G가 연결되어 있다면, G의 신장 트리를 계산하는 것이다.
• G의 연결된 구성 요소를 계산한다.
• G의 시작 정점들이 주어졌을 때, G의 모든 정점 v에 대하여,
s와 v 사이의 최소 간선 수를 가지는 경로 또는 그러한 경로가 존재하지 않음을 보고하는 계산이다.
• G 안의 사이클을 계산하거나 G가 사이클이 없다는 것을 보고한다.
'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 14장 메모리 (0) | 2024.01.19 |
|---|---|
| 13장 그래프(2) (1) | 2024.01.14 |
| 12장 텍스트 처리 (1) | 2024.01.10 |
| 11장 집합, 정렬, 선택(2) (2) | 2024.01.07 |
| 11장 정렬, 집합, 선택(1) (1) | 2024.01.05 |