이번시간에는 그래프에 대해 공부해 보겠습니다.
그래프란 ?
그래프는 정점(Vertex)간의 관계를 표현하는 자료구조 입니다.
그래프 G = (V,E)로 정의하는데, V(Vertex)는 그래프에 있는 정점들의 집합을 의미하고 E(Edge)는 정점을 연결하는 간선들의 집합을 의미합니다.
사실 일상생활에서 그래프의 개념은 많이 사용되고 있습니다. 그 중에 가장 대표적인 것이 지하철노선도 인데요, 각 지하철역과 그 들을 연결하는 호선간의 관계를 그래프로 표현할 수 있습니다.
그래프와 트리의 차이
그래프의 종류
무방향 그래프(Undirected Graph)
무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 v1와 v2를 연결하는 간선을 [v1, v2]라고 하면, 이때 [v1, v2]와 [v2, v1]은 같은 간선이다.
방향 그래프(Directed Graph)
방향 그래프는 다이그래프(digraph)라고도 하는데, 간선에 방향이 있는 그래프이다. 정점 v1와 v2를 연결하는 간선을 [v1, v2]라고 하면, 이때 [v1, v2]와 [v2, v1]은 같을 수 없다, [v1, v2]는 정점 v1에서 v2로만 갈 수 있는 간선을 의미한다.
완전 그래프(Complete Graph)
완전 그래프는 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프다.
무방향 그래프에서의 최대 간선 수 : n(n-1)/2
방향 그래프에서의 최대 간선 수 : n(n-1)/1
부분 그래프(subgraph)
원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 의미한다.
가중 그래프(Weight Graph)
정점을 연결하는 간선에 가중치를 할당한 그래프를 의미한다.
그래프 용어
정점(Vertex) : 연결한 객체들을 의미
간선(Edge) : 정점들을 연결하는 선
차수(Degree) : 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입/진출 차수의 합
진입차수(In-Degree) : 방향 그래프에서 정점을 머리로 하는 간선의 수, 정점으로 들어오는 간선
진출차수(Out-Degree) : 방향 그래프에서 정점을 꼬리로 하는 건선의 수, 정점에서 나가는 간선
경로(Path) : 정점A에서 정점B까지 간선을 따라 갈 수 있는 길을 순서대로 나열한 것을 의미
사이클(Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로를 의미
인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
그래프 구현
그래프를 구현하기 위해서는 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 한다. 그래프를 표현하는 방법은 순차 자료구조 방식을 이용한 2차원 배열의 인접행렬(Adjacent Matrix)방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트(Adjacent List) 방법이 있다.
인접행렬(Adjacent Matrix)
그래프를 구성하는 정점에 대해서 두 정점을 연결한 간선의 유뮤를 저장하는 방법으로 정점의 수에 대한 정방 행렬을 사용한다.
하나의 정점에서 자기 자신으로의 자체 간선은 있을 수 없으므로 인접 행렬의 대각선의 값은 항상 0이다. 무방향 그래프에서는 A[a][b]와 A[b][a]값이 같이 때문에, 대각선을 기준으로 윗부분과 아랫부분이 대칭을 이룬다.
방향 그래프에서는 간선 [a, b]와 [b, a]가 서로 다른 간선이기 때문에 대칭을 이루지 않는다.
n개의 정점을 가지는 그래프를 n * n 인접행렬로 표현하면 간선의 개수에 상관없이 항상 n * n개의 메모리를 사용한다. 그래프에 간선이 많은 경우에는 큰 문제가 없겠지만, 정점의 개수에 비해 간선의 개수가 적은 희소 그래프인 경우에는 인접 행렬이 희소 행렬이 되므로 메모리 낭비 문제가 발생한다.
인접 리스트(Adjacent List)
그래프를 표현하는 방법은 각 정점에 대한 인접 정점들을 연결 리스트로 만드는 것이다. 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크필드로 구성한다.
그래프 탐색
하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색 이라고 한다. 그래프 탐색 방법은 깊이 우성 탐색과 너비 우선 탐색이 있다.
깊이 우선 탐색, DFS(Depth First Search) : 스택, 재귀함수 사용
깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회 방법이다.
너비 우선 탐색, BFS(Breath Frist Search) : 큐 사용
너비 우선 탐색은 시작 정점으로 부터 인접한 정점들을 모두 차례로 방문한 후, 발문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법으로, 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법이다.
탐색에 대한 자세한 내용은 이후에, [ 알고리즘 ]에서 다시 알아보겠습니다.
'computer science > 자료구조' 카테고리의 다른 글
| [자료구조] 힙(Heap) (0) | 2019.07.11 |
|---|---|
| [자료구조] 트리(Tree) (0) | 2019.07.02 |
| [자료구조] 큐(Queue) (0) | 2019.06.20 |
| [자료구조] 배열과 list(LinkedList, ArrayList) (0) | 2019.06.02 |
| [자료구조] 스택(Stack) (0) | 2019.06.01 |
