그래프 자료구조
그래프의 개념
그래프 구현
1. 그래프의 개념
1) 그래프란 ?
그래프는 정점(vertex)와 간선(edge)로 구성된 한정된 자료구조를 의미한다. 자료 구조는 그래프 그조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다.
그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하다. 하지만 실제 적용에 있어서 최적의 자료 구조는 이 두 구조의 조합된 형태를 띤다고 한다.
2) 그래프의 종류
•
무방향 그래프(Undirected Graph)
무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A) 동일하다.
Ex) 양방향 통행 도로
•
방향 그래프(Directed Graph)
간선에 방향성이 존재하는 그래프 A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B>는 <B, A>는 다르다.
Ex) 일방 통행
•
가중치 그래프
간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’ 라고도 한다.
Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등
•
연결 그래프(Connected Graph)
무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우이다.
Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
•
비연결 그래프(Disconnected Graph)
무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우이다.
•
사이클(Cycle)
단순 경로(Simple Path;경로 중에서 반복되는 정점이 없는 경우)의 시작 정점과 종료 정점이 동일한 경우이다.
•
비순환 사이클(Acyclic Graph)
사이클이 없는 그래프이다.
•
완전 그래프(Complete Graph)
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프이다. 무방향 완전 그래프의 정점 수가 n 이면 간선의 수는 n * (n-1) /2 이다.
3) 그래프의 특징
•
그래프는 네트워크 모델이다.
•
2개 이상의 경로(무방향/방향; 양방향)가 가능하다.
•
루트 노드라는 개념이 없다.
•
부모-자식 관계라는 개념이 없다.
•
순회는 DFS나 BFS로 이루어 진다.
4) 그래프와 트리의 차이
•
하나의 트리에는 두 개의 정점 사이에 하나의 경로 만 존재하는 반면 그래프는 노드 사이에 단방향 및 양방향 등의 경로를 가질 수 있다.
•
트리에는 정확하게 하나의 루트 노드가 있으며 모든 자식은 단 하나의 부모 만 가질 수 있다. 그래프는 루트 노드 개념이 없다.
•
그래프는 루프와 자체 루프가있을 수 있지만 트리는 루프와 자체 루프가있을 수 없다.
•
그래프는 루프와 자체 루프를 가질 수 있기 때문에 복잡하지만 트리는 그래프에 비해 단순하다.
•
트리는 선주문, 순차 및 후행 기술을 사용한다. 그래프는 BFS (Breadth First Search)와 DFS (Depth First Search)를 사용한다.
•
나무는 n-1 개의 정점을 가질 수 있다. 그래프는 미리 정의 된 수의 간선이 없으며 그래프의 종류에 따라 다르다.
•
트리는 계층 적 구조가 있지만 그래프는 네트워크 모델이 있다.
그래프와 트리는 복잡한 문제를 해결하는 데 사용되는 비선형 데이터 구조이다. 그래프는 간선이 한 쌍의 꼭지점을 연결하는 정점과 가장자리 그룹으로, 트리는 연결되어 있어야하고 루프가 없어야하는 최소 연결 그래프로 간주된다.
2. 그래프 구현
1) 행렬
•
발행 행렬(Incidence matrix)
그래프는 변을 열로 하고 꼭짓점을 행으로하는 행렬로 표현되며, 행렬은 변의 끝점에 대한 데이터를 가진다. 행렬의 크기는 (꼭짓점의 수 X 변의 수)로 나타낸다
•
인접 행렬(Adjacency matrix)
인접 행렬의 크기는 꼭짓점의 수로 나타낸다. 만약 꼭짓점 x에서 꼭짓점 y로 변이 존재하면 행렬 성분 x행 y열의 값은 1이고 그렇지 않으면 0이다. 이것은 부분그래프, 역그래프를 쉽게 찾게 해준다.
인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프의 경우 사용한다.
2) 리스트
•
발행 리스트(Incidence list)
변들은 변으로 연결된 두 꼭짓점(방향이 있다면 순서가 존재함)와 가중치(weight), 다른 특정 데이터들을 포함하는 배열로 표현된다. 변으로 연결된 두 꼭짓점은 서로 인접(adjacent)한 관계라고 일컫는다.
•
인접 리스트(Adjacency list)
발생 리스트와 비슷하게도, 각 꼭짓점이 인접한 꼭짓점들의 리스트를 가진다. 따라서 방향성을 가지지 않은 그래프에서는 불필요한 정보가 생기게 한다. 예를 들어 만약 A와 B가 인접하다면 A의 인접 리스트는 B를 포함하게 되며 동시에 B의 리스트에도 A가 포함된다. 추가적인 저장 공간에 대한 비용이 있다면 인접 정보를 얻는 것은 빨라진다.
인접 리스트는 그래프 내에 적은 숫자의 간선을 가지는 희소 그래프의 경우 사용한다.
3) 그래프의 탐색
•
깊이 우선 탐색
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
•
너비 우선 탐색
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
•
Ex)
지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
→ 깊이 우선 탐색 : 모든 친구 관계를 다 살펴봐야 할지도 모른다.
→ 너비 우선 탐색 : Ash와 가까운 관계부터 탐색한다.
