본문으로 건너뛰기

Graph

  • 그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조
  • 정점은 데이터를 나타내는 노드이며, 간선은 정점 간의 관계
  • 단방향, 양방향, 가중치으로 나뉨
  • 루트, 부모 자식간의 개념이 없음
  • 사이클은 시작 정점과 끝 정점이 같은 경로
  • 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 그래프는 인접 리스트(Adjacency List) 또는 인접 행렬(Adjacency Matrix)을 사용하여 표현할 수 있음

인접 리스트​

const adjList = [
  [1, 2], // 0번 정점과 연결된 정점: 1, 2
  [0, 3, 4], // 1번 정점과 연결된 정점: 0, 3, 4
  [0, 4], // 2번 정점과 연결된 정점: 0, 4
  [1, 4], // 3번 정점과 연결된 정점: 1, 4
  [1, 2, 3, 5], // 4번 정점과 연결된 정점: 1, 2, 3, 5
  [4], // 5번 정점과 연결된 정점: 4
];

인접 행렬​

const matrix = [
  [0, 1, 1, 0, 0, 0], // 0번 정점과 연결된 정점: 1, 2
  [1, 0, 0, 1, 1, 0], // 1번 정점과 연결된 정점: 0, 3, 4
  [1, 0, 0, 0, 1, 0], // 2번 정점과 연결된 정점: 0, 4
  [0, 1, 0, 0, 1, 0], // 3번 정점과 연결된 정점: 1, 4
  [0, 1, 1, 1, 0, 1], // 4번 정점과 연결된 정점: 1, 2, 3, 5
  [0, 0, 0, 0, 1, 0], // 5번 정점과 연결된 정점: 4
];

그래프(Graph)의 탐색​

  • DFS
  • BFS