그래프 이해하기 with JS

 

 

 

그래프는 정점(Vertex)과 이 정점들을 연결하는 간선(Edge)으로 구성된 비선형 자료구조입니다.

 

이는 다양한 실세계 문제를 모델링하기에 적합한 구조로, 컴퓨터 네트워크, 소셜 네트워크, 도시 간 교통 시스템 등을 표현할 수 있습니다.

 

---

그래프의 기본 구조

• 정점 집합과 간선 집합: 각 정점은 하나 이상의 간선과 연결될 수 있으며, 이 간선들은 정점 사이의 관계를 나타냅니다.
• 방향성: 그래프는 방향이 있는 간선을 포함하는 방향 그래프와 방향이 없는 간선을 포함하는 무방향 그래프로 나뉩니다.
• 가중치: 간선은 가중치를 가질 수 있어, 두 정점 사이의 거리, 비용 또는 이동 시간 등을 표현할 수 있습니다.
• 사이클: 일부 그래프는 시작점으로 돌아오는 경로인 사이클을 포함할 수 있습니다.

---

그래프의 유형

• 무방향 그래프: 각 간선은 양방향으로의 이동을 허용합니다. 예를 들어, 양방향 통행 도로를 생각할 수 있습니다.
• 방향 그래프: 각 간선은 한 방향으로만 이동을 허용합니다. 예를 들어, 일방 통행 도로가 이에 해당합니다.
• 연결 그래프 및 비연결 그래프: 연결 그래프는 모든 정점 간에 경로가 존재하는 반면, 비연결 그래프는 일부 정점 간에 경로가 존재하지 않습니다.
• 완전 그래프: 모든 정점이 서로 연결된 그래프입니다.

 

---

그래프의 구현

• 인접 행렬: 2차원 배열을 사용하여 각 정점 간의 연결 상태를 저장합니다. 간선이 존재하면 1, 존재하지 않으면 0을 저장합니다.
• 인접 리스트: 각 정점에 연결된 모든 정점의 리스트를 저장하여 메모리 사용을 최적화합니다.
•  

---

자바스크립트에서 그래프 사용하기

자바스크립트에서 그래프를 구현할 때는 주로 객체와 배열을 활용합니다. 인접 행렬 방식은 배열을 사용하고, 인접 리스트는 객체 내에 리스트로 표현됩니다. 다음은 인접 리스트를 사용하는 간단한 예제입니다:

 

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
}

let graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addEdge("A", "B");
console.log(graph);