자료구조_10.그래프

그래프

그래프의 정의는 '연결되어 있는 객체 간의 관계를 표현하는 자료구조'이다.

그예로는 전에 알아본 Tree구조도 그래프의 특수한 경우이고, 지하철노선도 또한 그래프의 일종이다.

---

그래프의 정의와 용어

그래프는 정점(vertex)과 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V, E)로 표시한다.

• 정점(Vertices)
  • 여러 가지 특성을 가질 수 있는 객체
  • V(G) : 그래프 G의 정점들의 집합
  • 노드(node)이다.
• 간선(edge)
  • 정점들 간의 관계
  • E(G) : 그래프 G의 간선들의 집합
  • 링크(link)이다.
  • 종류
    • 무방향 그래프(undirected graph) : 간선을 통해서 양방향으로 갈수 있다.
    • 방향 그래프(directed graph) : 간선에 방향성이 존재하는 그래프로서 도로의 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있다.

네트워크

가중치 그래프를 네트워크라한다. 가중치 그래프는 간선에 비용(cost)나 가중치(weight)가 할당된 그래프이다.

 

부분그래프(subgraph)

어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프

 

정점의 차수

인접 정점(adjacent vertex)이란 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다.

정점의 차수는 그 정점에 인접한 정점의 수를 뜻한다. 하지만 그래프의 종류에 따라 정점의 차수가 다를 수 있다.

• 무방향 그래프의 차수
  • 하나의 정점에 연결된 다른 정점의 수
  • 하나의 간선이 두개의 정점에 인접하기 때문에 모든 정접의 차수를 합하면 간선 수의 2배가 된다.
• 방향 그래프의 차수
  • 집입 차수 : 외부에서 오는 간선의 수
  • 진출 차수 : 외부로 향하는 간선의 수

---

경로

단순 경로란 경로 중에서 반복되는 간선이 없는 경로이다.

사이클은 단순 경로의 시작 정점과 종료 정점이 동일한 경로를 뜻한다.

 

연결 그래프

무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되어있다고 하며, 연결 그래프라 부른다.

 

완전 그래프

모든 정점이 서로 연결되어 있는 그래프이다.

n개의 정점을 가진 무방향 완전그래프의 간선의 수 : n*(n-1)/2

---

그래프의 표현 방법

그래프를 표현하는 방법에는 다음과 같이 2가지의 방법이 있다.

• 인접행렬(idjacent matrix)방법
• 인접 리스트(adjacent list)방법

인접행렬

그래프의 정점 수가 n이라면 n*n의 2차원 배열인 인접 행렬 M의 각 원소를 한 정점으로부터 인접 정점의 유무를 할당함으로써 그래프를 메모리에 표현할 수 있다.

두 정점을 연결하는 간선의 존재 여부를 O(1)시간 안에 즉시 알 수 있는 장점이 있지만,

n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모리 공간이 필요해 경우에 따라 메모리 낭비가 크다는 단점이있다.

 

인접리스트

각 정점에 인접 정점들을 연결리스트로 표현한다.

각 연결 리스트의 노드들은 인접 정점을 저장하게 된다. 각 연결 리스트들은 헤더 노드를 가지고 있고 이 헤더 노드들은 하나의 배열로 구성되어 있다. 

---

그래프의 탐색

그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다.

그래프의 탐색 방법은 다음과 같이 2가지가 있다.

• 깊이 우선 탐색(DFS : depth first search)
• 너비 우선 탐색(BFS: dreath first search)

---

깊이 우선 탐색

깊이 우선 탐색은 트리에서 생각하면 이해하기 쉽다.

트리를 탐색할 때 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색을 진행한다.

이를 위해서는 되돌아가기 위해 스택이 필요하다.

 

깊이 우선 탐색을 구현하는 데는 2가지의 방법이 있다. 순환 호출을 이용하는 것이 첫 번째 방법이고 두 번째 방법은 명시적인 스택을 사용하여 인접한 정범들을 스택에 저장하였다가 다시 꺼내어 작업하는 것이다.

 

인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색

 

인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색

 

명시적 스택을 이용한 깊이 우선 탐색

---

너비 우선탐색

너비 우선 탐색은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐가 필요하다.

 

인접 행렬로 표현된 그래프에 대한 너비 우선 탐색

 

인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색