06.그래프

그래프란

정점이라 불리는 데이터를 간선 혹은 링크로 연결한 형태의 자료구조를 말한다. 트리도 사실 그래프의 일종이다.

그래프는 사이클을 형성할 수 있고 이웃한 정점끼리 상하관계를 갖지 않는다.

 

그래프는 기본적으로 데이터간의 연결 관계를 표현하는 자료구조임

지하철 노선도 연결관계를 표현한 그래프라고 할 수 있음

 

자주 언급되는 그래프 유형

• 연결/비연결 그래프
• 방향/무방향 그래프
• 가중치 그래프
• 서브 그래프

가장 기본적인건 연결 그래프와 비연결 그래프가 있다. 

임의의  두 정점 사이를 잇는 경로가 있냐 없냐에 따라 나뉜다. 

연결그래프: 그래프 상에 있는 임의의 두 정점 사이의 경로가 존재하는 그래프 -> 2개의 아무 정점이나 골라서 간선으로 서로를 이을 수 있으면 연결 그래프임

비연결 그래프: 정점 사이에는 경로가 존재하지 않을 수도 있음

 

 

간선 방향이 있느냐 없느냐에 따라 그래프의 유형을 나눌 수 있음

방향 그래프: 간선에 방향이 있는 그래프

무방향 그래프: 방향이 없는 그래프

 

간선에 가중치가 부여된 그래프는 가중치 그래프라고 한다. 간선에 부여된 값인 가중치는 비용이라고함.

ex) 지하철 역을 정점 역과 역 이를 연결하는 경로를 간선으로 보는 그래프에선 역과 역 사이의 거리를 가중치로 부여할 수 있음

가중치는 얼마든지 음수가 될 수 있다. 간선에 부여할 수 있는 값이라면 양수,음수 모든 가능

 

서브그래프는 부분 그래프라고도 부른다. 특정 그래프의 1정점과 간선의 일부분으로 이루어진 그래프를 말한다.

 

 

h1,h2, h3은 그래프 G의 서브 그래프다.그래프 G의 정점과 간선의 일부분으로 구성되어 있기 때문임.

 

어떻게 구현하고 메모리에 저장하는가!!!!

방법이 크게 2가지가 있음

1. 그래프를 인접 행렬로 표현하는 방법

2. 인접 리스트로 표현하는 방법.

1번은 이차원 배열을 기반으로 그래프를 구현하고 2번은 연결 리스트를 기반으로 구현한다.

 

인접 행렬 기반 그래프 표현

인접 행렬 기반 그래프 표현은 N * N 크기의 행렬로 그래프를 표현하는 방법이다.

N은 정점의 개수를 말하며 N * N 행렬의 <행, 열> 값은  <출발 정점, 도착 정점>을 의미한다.

 

일반적으로 두 정점이 단순히 연결 되었을 때는 1, 연결되지 않았을때는 0으로 표기한다.

1행 2열이 1인 경우에는 첫 번째 정점에서 두 번째 정점 방향으로 그래프가 연결되었음을 나타낸다.

 

사진의 그래프는 정점의 개수가 4개이므로 4*4 크기의 이차원 배열로 나타낼 수 있다.

 

• 정점1이 정점2로 연결되어 있으므로 1행 2열을 1로 표기한다. 
• 정점3이 정점4로 연결되어 있으므로 3행 4열을 1로 표기한다 
• 정점4가 정점1로 연결되어 있으므로 4행 1열을 1로 표기한다.

그 외에 연결되지 않은 부분은 0으로 표기한다.

 

to \ from	1번	2번	3번	4번
1번	0	1	0	0
2번	0	0	0	0
3번	0	0	0	1
4번	1	0	0	0

 

 

무방향 그래프 일 경우도 보자 

 

무방향 그래프의 정점은 양방향으로 연결 되어 있다고 간주한다.

정점 1이 정점2로 연결된 동시에 정점2도 정점1과 연결되어 있다고 보는것이다.

 

• 정점 1은 정점 2로, 정점 2는 정점 1과 연결 되어 있다. 1행 2열과 2행 1열을 1로 표기한다.
• 정점 3은 정점 4로, 정점 4는 정점 3과 연결 되어 있다. 3행 4열과 4행 3열을 1로 표기한다.

다른 정점도 같은 방법으로 진행하여 이차원배열로 나타낼 수 있다.

to \ from	1번	2번	3번	4번
1번	0	1	0	1
2번	1	0	0	0
3번	0	0	0	1
4번	1	0	1	0

 

무방향 그래프를 표현한 인접 행렬의 특징을 알 수 있다.

행렬의 대각선 요소를 기준으로 연결 관계가 대칭을 이룬다.

 

가중치 그래프도 인접 행렬로 나타내보자.

지금까지는 0과 1로 인접행렬을 표기했지만 간선에 가중치가 부여된다면 행렬에 어느정도 연결 되었는지도 같이 표현되어야 한다. 

따라서 N*N 행렬의 <행,열> 값은 <출발 정점, 도착 정점>을 연결하는 가중치로 표기한다.

 

• 정점 1은 2의 가중치로 정점 2 방향으로 연결되어 있으므로 1행 2열은 2로 표기한다.
• 정점 3은 3의 가중치로 정점 4 방향으로 연결되어 있으므로 3행 4열은 3으로 표기한다.
• 정점 4는 4의 가중치로 정점 1 방향으로 연결되어 있으므로 4행 1열은 4로 표기한다.

아래와 같은 이차원 배열을 완성할 수 있다.

 

to \ from	1번	2번	3번	4번
1번	0	2	0	0
2번	0	0	0	0
3번	0	0	0	3
4번	4	0	0	0

 

 

인접 리스트 기반 그래프 표현

인접 리스트 기반 그래프 표현은 그래프의 특정 정점과 연결된 정점들을 연결 리스트로 표현하는 방법이다.

특정 정점에서 나가는 간선에 연결된 정점들을 연결 리스트의 노드로 삼는 다는 의미다.

 

• 정점 1에서 나가는 간선이 정점 2를 향하고 있으므로 정점 1 연결 리스트의 노드로 정점 2를 추가한다.
• 정점 2에서 나가는 간선이 정점 4를 향하고 있으므로 정점 2 연결 리스트의 노드로 정점 4를 추가한다.

같은 방법으로 연결 리스트의 노르를 추가하면 아래와 같은 연결리스트들이 만들어진다.

 

 

인접 리스트 기반 그래프 표현으로 무방향 그래프를 표현하는것은 인접 행렬을 이용한 그래프 표현과 유사하다. 양방향으로 연결한다고 생각하면 됨.

 

가중치 그래프 또한 인접 리스트로 표현할 수 있다. 

하나의 노드를 표현하는 정보에 가중치 정보까지 포함하면 된다.

 

쉽쥬

 

깊이 우선 탐색과 너비 우선 탐색

05.트리에서 모든 노드를 한번씩 방문하는 순회를 공부했는데

그래프의 모든 정점을 순회하는 탐색 방법에 대해서도 알아보자.

 

대표적인 순회 방법

• 깊이 우선 탐색
• 너비 우선 탐색

깊이 우선 탐색(DFS) (Depth-First Search)

그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법이다.

 

그래프의 모든 정점들을 깊이 우선 탐색으로 순회했을때는 a -> b -> e -> c -> f -> d가 될 것이다.

그래프는 사이클이 있기 때문에 트리는 아니다.

하지만 트리도 그래프의 일종이기 때문에 트리에 대한 깊이 우선 탐색과 너비 우선 탐색이 모두 가능하다.

 

정점 a부터 탐색을 시작해 인접한 정점이 2개 이상일 경우에는 알파벳 순으로 탐색한다고 가정하자.

아직 한번도 방문 하지 않은 정점은 미방문 정점이라고 지칭.

 

깊이 우선 탐색 알고리즘을 구현할 때 유용하게 사용되는 자료구조에는 배열과 스택이 있다.

• 배열은 특정 정점의 방문 여부를 확인하기 위해 사용한다.
• 스택은 방문 중 뒤로가기가 필요할 때 사용할 수 있다.

 

 

 

너비 우선 탐색(BFS) (Breadth-First Search)

최대한 넓게 탐색하기를 반복하는 방법이다.

너비 우선 탐색은 인접한 모든 정점들을 방문하고 방문한 정점들과 연결된 모든 정점을을 방문하고, 또 방문한 정점들과 연결된 모든 정점들을 방문하기를 반복하는 탐색방법이라고 할 수 있음.

그래프의 모든 정점들을 너비 우선 탐색으로 순회한다면

a -> b -> c -> d -> e -> f 순서가 될 것이다. 너비 우선 탐색 알고리즘의 경우 배열과 큐를 사용할 수 있다.

 

• 배열은 특정 점정의 방문을 여부를 확인하기 위해 사용
• 큐는 연결된 정점들을 저장하기 위해 사용

특정 정점과 인접한 모든 정점을 줄 세우듯 저장하고, 앞으로 어떤 정점에서 너비 우선 탐색을 할지 알기 위해 큐를 사용한다는 것.

 

최단 경로 알고리즘

한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고리즘이다.

최단 경로 알고리즘은 일상 속에 녹아 있는 알고리즘으로 대표적으로 지도 서비스에서 원하는 목적지까지 이르는 최단 거리를 알려주는 원리로도 사용된다.

 

다익스트라 알고리즘

간선의 가중치가 음이 아닌 수라는 가정하에 사용가능한 알고리즘으로 특정 정점에서 다른 모든 정점까지의 최단 거리를 구해 주는 알고리즘이다.

작동과정에서 특정 정점에 이르는 거리를 저장한 데이터가 함께 사용된다.

 

알고리즘의 작동 과정

1. 최단 거리 테이블 상에서 시작 정점을 제외한 정점들은 모두 충분히 큰 수로 초기화 한다.
2. (시작) 정점을 방문한다.
3. 방문한 정점과 인접한 정점들을 탐색한다.
4. 경로 상의 가중치 합과 최단 거리 테이블 상의 값을 비교한다.
5. 최단 거리 테이블을 갱신할 수 있다면 갱신한다.
6. 방문하지 않은 정점 중 최단 거리가 가장 작은 정점을 방문한다.
7. 더 이상 방문할 정점이 없을 떄까지 3~6의 과정을 반복하고 종료한다.

다익스트라 알고리즘의 시작 정점을 정점1로 삼고 나머지 정점들의 최단 거리를 구한다.

 

(풀이는 책 볼 것.)