그래프

그래프

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있는데 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다.

• 정점(Vertex) - 그래프에서 하나의 연결점
• 간선(Edge) - 두 정점을 잇는 선
• 차수(Degree) - 정점 하나에 연결된 간선의 수

✏️ V개 정점을 갖는 그래프의 최대 간선의 수는 V * (V-1) / 2 (무향 그래프 - 양방향)

무향그래프(undirected graph)

간선을 표현하는 두 정점의 쌍에 순서 즉 방향이 없는 그래프이다. 따라서 두 정점 V0와 V1을 잇는 간선 (V0, V1)과 (V1, V0)는 똑같은 간선을 나타낸다.

방향그래프(directed graph)

모든 간선을 순서가 있는 두 정점의 쌍으로 표현하는 즉, 간선이 방향을 가진 그래프다. 방향 그래프에서는 하나의 간선을 V0 -> V1을 <V0, V1>이라 표기하며 V0를 tail, V1를 Head라 한다. 또한 방향 그래프에서는 <V0, V1>과 <V1, V0>는 다른 간선이다. 방향 그래프에서는 이 간선을 아크(arc)라고도 한다.

진입차수(in-degree) / 진출차수(out-degree)

한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.

자기 루프(self loop)

정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.

사이클(cycle)

한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프다.

그래프의 표현방식

인접행렬(adjacency matrix)

• 0의 진출차수는 2개 입니다: 0 —> 3, 0 -> 1
  [0][1] === 1
  [0][3] === 1
• 1의 진출차수는 3개 입니다: 0 —> 3, 0 —> 1, 1 -> 2
  [1][0] === 1
  [1][3] === 1
  [1][2] === 1
• 2의 진출차수는 2개입니다: 2 —> 1, 2 -> 3
  [2][1] === 1
  [2][3] === 1

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다.

인접리스트 (adjacency list)

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현 한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.