[알고리즘] 그래프 - JavaScript

그래프? 

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다. 

정점 집합과 간선 집합으로 표현할 수 있다. 

 

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다. 
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다. 
• 간선은 가중치를 가질 수 있다. 
• 사이클이 발생할 수 있다. 

무방향 그래프

간선으로 이어진 정점끼리 양방향으로 이동이 가능한 그래프이다. 

표현에 ( A, B )와 ( B, A )는 같은 간선으로 취급한다. 

 

방향 그래프

간선에 방향성이 존재하는 그래프이다.

양방향으로 갈 수 있더라도 ( A, B )와 ( B, A )는 다른 간선으로 취급한다. 

 

JavaScript에서 사용하기

인접 행렬 

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

graph[0][1] = true;  // 0 => 1 
graph[0][3] = true;  // 0 => 3
graph[3][4] = true;  // 3 => 4

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 

여기서 만약 가중치를 주고 싶다면 false와 true가 아닌 0, 1, 2, 3, ... 같이 가중치를 넣어주면 된다. 

 

인접 리스트 

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

graph[0].push(1); // 0 => 1

자바스크립트에서는 배열이 연결 리스트와 같은 역할을 하기 때문에 마찬가지로 배열을 통해서 

구현이 가능하다. 

 

정점의 수만큼 배열을 만들고 각 배열에 연결된 정점을 넣어주면 된다.