자료구조-그래프

그래프

---

• 그래프는 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조입니다.
• 그래프는 정점(Vertex)과 간선(Edge)으로 구성되며, 이를 통해 객체들 간의 연결 관계를 나타냅니다.
• 그래프에서는 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기합니다.
• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냅니다.
• 행과 열은 각각 그래프의 정점을 나타내고, 행렬의 값은 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다

 A -- B
  |    |
  C -- D

이런 그래프가 존재한다면, 2차원 배열로 나타낼수 있다.

      A  B  C  D
  A   0  1  1  0
  B   1  0  0  1
  C   1  0  0  1
  D   0  1  1  0

 

 

 

BFS와 DFS

---

• BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 그래프를 탐색하는 두 가지 주요 알고리즘입니다.
• BFS는 그래프를 탐색할 때 너비를 우선으로 탐색하는 방법으로, 시작 정점에서 인접한 모든 정점을 먼저 방문한 이 후 해당 정점들과 인접한 정점들을 순차적으로 방문하는 것을 반복합니다..
• BFS는 큐(Queue) 자료구조를 사용하여 구현되며, 간선의 가중치가 모두 동일한 경우 최단 경로를 찾는 데에 유용합니다.

function bfs(graph, start) {
  const visited = []; // 방문한 정점들을 저장하기 위한 배열
  const queue = [start]; // 방문할 정점을 저장하기 위한 큐

  while (queue.length) {
    const vertex = queue.shift();
    if (!visited.includes(vertex)) {
      visited.push(vertex);
      queue.push(...graph[vertex].filter(v => !visited.includes(v)));
    }
  }
}

• DFS는 그래프를 탐색할 때 깊이를 우선으로 탐색하는 방법입니다.
• 시작 정점에서 인접한 정점을 하나 선택하여 계속해서 그 정점의 인접한 정점으로 이동하며 탐색합니다.
• 인접한 정점이 없을 때까지 계속 탐색한 후, 이전 정점으로 돌아와 다음 정점을 선택하여 탐색을 진행합니다.
• DFS는 재귀 함수 또는 스택(Stack) 자료구조를 사용하여 구현될 수 있으며, 그래프의 전체 구조를 파악하고자 할 때 유용합니다.

function dfs(graph, start) {
  const visited = []; // 방문한 정점들을 저장하기 위한 배열
  const stack = [start]; // 방문할 정점을 저장하기 위한 스택

  while (stack.length) {
    const vertex = stack.pop();
    if (!visited.includes(vertex)) {
      visited.push(vertex);
      stack.push(...graph[vertex].filter(v => !visited.includes(v)));
    }
  }
}