[자료구조] 그래프

알고리즘 문제를 풀면서 한번씩은 접하게 되는 개념이 BFS(너비 우선 탐색) / DFS(깊이 우선탐색)이다.

이 방식들은 그래프를 순회하는 방식을 의미한다. 

 

그래프

그래프란, 노드(정점)와 간선으로 이루어진 자료구조이다.

정확하게 설명하자면 정점간의 관계를 표현하는 조직도라고 볼 수 있다.

 

*트리와 그래프 
노드? 간선? 은 트리 구조에서도 나오는 개념이다.
트리는 그래프의 일종이라고 할 수 있다.
✔️ 트리와 다르게 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며
✔️ 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 

그래프는 네트워크 모델 즉 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 

실생활의 다양한 예를 그래프로 표현할 수 있다.

• 대표적으로 지하철 노선도,
• 도심의 도로 등이 있다.
• 그래서 문제도 다양하게 출제/알고리즘에서 많이 활용된다.
• 특히 그래프를 순회하는 방식인 DFS/BFS를 잘 알아두어야 한다. 

 

 

그래프 관련 용어

노드

데이터가 저장되는 곳

 

간선

노드를 연결한 선 

 

인접 정점

간선에 의해 직접 연결된 노드 

만약, 소깡 ➡️ 후리 ➡️ 황쥐 라고 할 때, 소깡의 인접 접점은 후리 / 후리의 인접 접점은 황쥐가 된다.

 

 

위의 이미지에서

✅ 정점은 무엇일까?

0, 1, 2, 3

 

✅ 간선은 무엇일까?

노드간의 관계

 

✅ 인접 정점은 무엇일까?

간선에 의해 연결된 정점으로 정점 0과 정점 1은 인접 정점이다. 

 

✅ 단순 경로

경로 중 반복되는 정점이 없는 것, 같은 간선을 지나가지 않는 경로를 말한다.

 

✅ 차수

무방향 그래프에서 하나의 정점에 인접한 정점의 수를 말한다.

정점 0의 차수는 3이다.

 

✅ 진출 차수

방향 그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수를 말한다.

 

✅ 진입 차수

방향 그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수를 말한다.

 

 

그래프 종류

방향 그래프

간선에 방향이 있는 그래프로 간선 그래프 방향으로만 갈 수 있다.

만약 집 -> 도서관 로 그래프가 이루어져 있다면 집 노드에서는 도서관 노드로 갈 수 있고 도서관 노드에서는 집 노드로 갈 수 없다.

 

 

무방향 그래프

간선에 방향이 없는 그래프로, 노드는 양방향으로 갈 수 있다.

집 - 도서관 로 되어 있다면 집 노드에서 도서관 노드로 갈 수 있고 도서관 노드에서 집 노드로 갈 수 있다. 

 

 

가중치 그래프 

노드를 이동할 때 드는 비용, 또는 가중치가 할당된 그래프이다.

집 - 10 -> 도서관 이라고 되어있다면, 집에서 도서관 노드로 이동하는데 발생하는 비용이 10이라는 것을 의미한다.

 

 

완전 그래프

모든 노드가 간선으로 연결된 그래프를 의미한다.

 

 

그래프 구현 방법 (표현 방법)

그래프를 구현하는 방법에는 인접 행렬과 인접 리스트 방법이 있다.

두개의 구현 방식은 각각 상반된 장단점을 갖고 있다. (보통 인접 리스트 방식을 많이 사용한다.)

 

인접 행렬 방식 

인접 행렬은 그래프의 노드를 2차원 배열로 만든 것이다.

각 노드에 다른 노드들이 인접 노드라면 1, 아니면 0을 넣어준다.

 

🟢 인접 행렬 방식의 장점 

• 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 인덱스(위치)만 알고 있다면 두 점에 대한 연결 정보를 조회할 수 있다. 그리고 이 때의 시간 복잡도는 O(1)이다.
• 구현이 비교적 간편하다.

 

🔴 인접 행렬 방식의 단점

• 모든 정점에 대한 간선 정보를 대입해야 하므로 O(n^2)의 시간 복잡도가 소요된다.
• 무조건 2차원 배열이 필요하기 때문에 필요한 정보 이상의 공간이 낭비될 수 있다.

 

인접 리스트 방식

그래프의 노드들을 리스트로 표현한 것이다.

정점의 리스트 배열을 만들어서 관계를 설정하는 방식으로 구현한다.

 

🟢 인접 리스트 방식의 장점 

• 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능하다. (n: 간선의 개수)
• 필요한만큼의 공간을 사용하기 때문에 공간의 낭비가 적다. 

 

🔴 인접 리스트 방식의 단점

• 특정 두 점이 연결되어 있는지 확인하기 위해서는 인접 행렬에 비해 search하는 속도가 느리다. 
• 구현이 비교적 어렵다. 

 

 

그래프 탐색

첫 정점부터 그래프에 존재하는 모든 정점들을 모두 한번씩 방문하는 것을 그래프 탐색이라고 한다.

그래프 탐색의 방법은 깊이 우선 탐색 방식과 너비 우선 탐색 방식이 있다.

 

 

깊이 우선탐색(DFS)

깊이 우선탐색 DFS는 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식

간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현한다. 

 

 

넓이 우선탐색(BFS)

넓이 우선탐색 BFS는 시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선방문하는 방법

일반적으로 QUEUE를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현한다.