그래프 | Notion

그래프(Graph)는 다른 자료구조와 달리 **관계(relationship)**를 표현하는 데 강점이 있습니다. 단순히 데이터를 저장하는 게 아니라, **정점(Vertex)**과 **간선(Edge)**을 통해 데이터 간의 연결을 나타내죠.

📌 그래프 기본 개념

정점(Vertex): 데이터가 저장되는 노드
간선(Edge): 정점과 정점을 연결하는 선
방향 그래프(Directed Graph): 간선에 방향이 있음 (예: A → B)
무방향 그래프(Undirected Graph): 간선에 방향이 없음 (예: A—B)
가중치 그래프(Weighted Graph): 간선에 비용이나 거리 같은 값이 있음
인접(Adjacency): 두 정점이 간선으로 연결되어 있는 관계

📊 그래프 표현 방식

표현 방식	특징	예시 (JavaScript)
인접 행렬(Adjacency Matrix)	2차원 배열로 표현, 공간 많이 차지	`matrix[a][b] = 1`
인접 리스트(Adjacency List)	각 정점마다 연결된 정점 리스트	`graph[a].push(b)`

// 인접 리스트 예시
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"]
};

🔍 그래프 탐색 알고리즘

DFS (Depth First Search): 깊이 우선 탐색, 재귀/스택 활용
BFS (Breadth First Search): 너비 우선 탐색, 큐 활용

// BFS 예시
function bfs(graph, start) {
  let visited = new Set();
  let queue = [start];

  while (queue.length > 0) {
    let node = queue.shift();
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node); // 방문 처리
      queue.push(...graph[node]);
    }
  }
}

bfs(graph, "A"); // A → B → C → D

📌 그래프 기본 개념

📊 그래프 표현 방식

🔍 그래프 탐색 알고리즘

🌍 그래프 활용 예시