TIL [자료 구조 - Graph]

dlrbwls0302·2021년 1월 21일
0

Graph의 개념

그래프란 자료 구조의 한 모델로 유한한 숫자의 노드(nodes)들과 그 노드들을 잇는 간선(edges)들로 이루어져 있다. 그래프에서는 노드를 다른 말로 정점(vertex)이라고 부르기도 하며 이는 양 정점이 한 개의 간선으로 연결되어 있음을 알 수 있다. 그래프는 실생활에서도 많이 쓰이는데 주로 네트워크의 개념들과 관련이 깊다. 네트워크는 주로 전화 통신망, 회로, 소셜 네트워크 서비스(페이스북 같은)를 의미한다.

소셜 네트워크 서비스 얘기가 나왔는데 페이스북을 예로 들면 유저 한 명 한 명이 노드(정점)을 의미하고 그 유저들이 다른 유저들과 연결된 것을 간선으로 연결되었다고 표현할 수 있겠다. 각 노드들은 유저의 id, 이름, 성별과 같은 정보들을 담고 있다고 할 수 있다.


Graph의 종류

그래프에도 종류가 두 가지가 있는데 이 둘이 크게 다른 것이 아니라 그래프의 방향성(direction)이 다르다고 표현하고 싶다.

1. Undirected Graph

무 방향 그래프에선 노드들이 양 방향성 간선(bidirectional edges)으로 이루어져 있다. 양 방향성이란 만약 A와 B노드가 연결이 되어있다고 하면 A에서 B를 갈 수 있고 B에서도 A로 갈 수 있다는 뜻이다.

2. Directed Graph

방향 그래프에선 노드들이 방향성 간선(directed edges)으로 이루어져 있다. 그림을 보면 간선들이 어떤 특정한 방향을 가지고 있고 그 방향으로 밖에 이동할 수 없다.


진입 차수와 진출 차수

1. 진입 차수(in-degree)

진입 차수는 방향 그래프에서 외부에서 오는 간선의 수를 의미한다.

이 그림에서 제일 가운데에 있는 노드의 진입 차수는 파란색 노드에서 오는 한 개이다.

2. 진출 차수(out-degree)

진입 차수의 반대로 방향 그래프에서 외부로 향하는 간선의 수를 의미한다.

제일 가운데 노드는 3개의 진출 차수를 가지고 있다.


인접 행렬

인접 행렬 그래프는 연결되어 있는 상태를 2차원 배열의 형태로 나타낸 그래프이다. [i][j] 는 i 노드에서 j노드가 이어져 있는지 확인하는데 이어져 있다면 1, 이어져 있지 않다면 0으로 표현한다. 그래프에서 1을 다 더하면 간선의 수와 같다는 것을 알 수 있다.


인접 리스트

링크드 리스트 처럼 계속해서 뒤에 원소를 붙일 수 있다. 뭔가 벡터보다 더 직관적인 것 같다.


그래프의 순회

1. 깊이 우선 탐색 (Depth First Search, DFS)

시작 정점에서 한 방향으로 게속 탐색하다가 막히면 가장 마지막 갈림길 간선이 있는 정점으로 돌아가서 다른 방향의 간선으로 가면서 탐색하는 방법

이렇게 생긴 그래프가 있다고 해보자. 이 그래프를 깊이 우선 탐색으로 모든 정점을 순회한다고 했을때 어떻게 하면 될까?

A -> B or C 중 오름차순에 따라 B 선택 -> D or E 중에 오름차순에 따라 D 선택 -> G 선택 -> E or F 중에 오름차순에 따라 E 선택 -> B or C 중에 B는 이미 순회했기 때문에 C 선택 -> C의 인접 정점은 모두 순회했으므로 다시 backtracking -> E의 인접 정점은 모두 순회했으므로 다시 backtracking -> G로 복귀 -> G의 인접 정점 중에 D는 이미 순회 했으므로 F로 이동

순서: A -> B -> D -> G -> E -> C -> E(backtracking) -> G(backtracking) -> F

깊이 우선 탐색의 특징

  1. 모든 정점을 순회 하고자 할 때 이 방법을 선택한다.

  2. 어느 정점을 방문했는지 체크하는 알고리즘이 있어야 한다.

2. 너비 우선 탐색 (Breadth First Search, BFS)

시작 정점에서 시작하여 인접한 정점들을 모두 순회하고 다음 인접한 정점으로 이동하는 방법

위와 같은 그래프를 너비 우선 탐색으로 모두 순회해 본다고 하자. A를 시작 정점으로 놓고 인접한 정점들을 하나씩 돌아본다.
A -> B -> C -> B의 인접한 정점 D -> E -> C의 인접한 정점 x -> 다시 D -> D의 인접한 정점 G -> G -> G의 인접한 정점 F

순서: A -> B -> C -> D -> E -> G -> F

profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글