그래프 (Graph)

Jun 2k (Jun2)·2023년 9월 27일

CS지식 WIL cs공부 자료구조&알고리즘

자료구조&알고리즘

목록 보기

9/19

그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.
정점 집합과 간선 집합으로 표현 가능하다. 정점은 node, 간선은 edge라고도 부른다.

출처: 이선협 강사님 데브코스 강의 자료

실제 사례로 쓰이는 경우는 지하철 노선도 같은 지도나 페이지 랭크에서 쓰인다.

그래프의 특징

정점은 여러 개의 간선을 가질 수 있다.
방향 그래프와 무방향 그래프로 나눌 수 있다.
간선은 가중치를 가질 수 있다.
예) 역과 역 사이의 거리
사이클이 발생할 수 있다.
사이클 : 탐색 시 루프가 가능한 구역
무한 루프에 빠지지 않도록 사이클을 잘 찾아야 한다.

무방향 그래프

간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
(A, B)와 (B, A)는 같은 간선으로 취급된다.
예) 양방향 통행 도로

출처: 이선협 강사님 데브코스 강의 자료

방향 그래프

간선에 방향성이 존재하는 그래프이다.
양방향으로 갈 수 있어도 <A, B>와 <B, A>는 다른 간선으로 취급된다.
예) 일방 통행 도로

출처: 이선협 강사님 데브코스 강의 자료

연결 그래프

모든 정점이 서로 이동 가능한 상태의 그래프
어느 한 정점이라도 동 떨어져 있으면 안된다.

출처: 이선협 강사님 데브코스 강의 자료

비연결 그래프

특정 정점쌍 사이에 간선이 존재하지 않는 그래프

출처: 이선협 강사님 데브코스 강의 자료

완전 그래프

모든 정점끼리 연결되어 있는 그래프
완전 그래프의 간선 갯수 : 정점의 갯수가 n개 일 때 n(n-1)개

출처: 이선협 강사님 데브코스 강의 자료

사이클

그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

출처: 이선협 강사님 데브코스 강의 자료

그래프의 구현 방법

인접 행렬, 인접 리스트 두 가지 방식으로 그래프를 표현 가능하다.
인접 행렬은 2차원 배열 구현 가능하며 인접 리스트는 연결 리스트로 구현 가능하다.

JavaScript에서의 구현

인접 행렬

const graph = Array.from(
  Array(5),
  () => Array(5).fill(false)
);
// 각 간선을 연결하면 true로 표현
// 가중치를 두고 싶으면 null과 특정 값을 부여하면 된다.
// 무방향 그래프일 경우에는 배열 값을 대칭적으로 추가한다.
graph[0][1] = true;
graph[0][3] = true;
graph[1][2] = true;
graph[2][0] = true;
graph[2][4] = true;
graph[3][2] = true;
graph[4][0] = true;

출처: 이선협 강사님 데브코스 강의 자료

인접 리스트

배열을 만든 후 간선을 배열에 추가하면 된다.

const graph = Array.from(
  Array(5),
  () => []
);
// 각 간선을 각 정점 배열에 추가한다.
graph[0].push(1);
graph[0].push(3);
graph[1].push(2);
graph[2].push(0);
graph[2].push(4);
graph[3].push(2);
graph[4].push(0);