Javascript 자료구조 & 알고리즘 (1)

[1] 그래프 (Graph)

그래프

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
• 정점(Node) 집합과 간선(Edge) 집합으로 표현할 수 있음
  

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있음
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있음
• 간선은 가중치를 가질 수 있음
• 사이클이 발생할 수 있음 (탐색 시 무한루프 발생하지 않도록 해야 함)

무방향 그래프

• 간선으로 이어진 정점끼리는 양방향으로 이동이 가능
• 표현하기에(A, B)와 (B, A)는 같은 간선으로 취급
• ex) 양방향 통행 도로
  

방향 그래프

• 간선에 방향성이 존재하는 그래프
• 양방향으로 갈 수 있더라고 <A, B>와 <B, A>는 다른 간선으로 취급
• ex) 일방 통행
  

전체 그래프의 연결 상태에 따른 분류

1. 연결 그래프
   - 모든 정점이 서로 이동 가능한 그래프
   

2. 비연결 그래프
   - 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
   - ex) 친한 친구 설문 그래프
   

3. 완전 그래프
   - 모든 정점끼리 연결된 상태인 그래프
   - 한 정점의 간선 수 = (모든 정점 - 1)
   - 모든 간선의 수 = (모든 정점 - 1) * (정점 수)
   

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

그래프의 구현 방법
- 인접 행렬, 인접 리스트 두 가지 방식으로 그래프를 표현할 수 있음\

JavaScript에서 사용법

인접 행렬

• 정점의 크기만큼 이차원 배열을 만들고, 연결이 안된 상태로 초기화
• 행렬의 열부분을 시작 정점, 행 부분을 도착 정점으로 두고, true값을 넣어주면 간선이 연결된 것으로 침
• 간선에 가중치를 주고 싶다면 true/false가 아니라 null과 임의의 가중치 값을 넣어주면 됨
• 무방향그래프를 구현하고 싶다면 모든 값을 대칭으로 넣어주면 됨

const graph = Array.from(
  Array(5),
  () => Array(5).fill(false)
);

graph[0][1] = true    // 0 -> 1
graph[0][3] = true    // 0 -> 3
graph[1][2] = true    // 1 -> 2
graph[2][0] = true    // 2 -> 0
graph[2][4] = true    // 2 -> 4
graph[3][2] = true    // 3 -> 2
graph[4][0] = true    // 4 -> 0

인접 리스트

• 배열은 마지 연결리스트처럼 무한정 늘어날 수 있기 때문에
  정점의 수만큼 배열을 만든 후, 연결할 정점을 배열에 추가하면 됨

const graph = Array.from(
  Array(5),
  () => []
);

graph[0].push(1);    // 0 -> 1
graph[0].push(3);    // 0 -> 3
graph[1].push(2);    // 1 -> 2
graph[2].push(0);    // 2 -> 0
graph[2].push(4);    // 2 -> 4
graph[3].push(2);    // 3 -> 2
graph[4].push(0);    // 4 -> 0