[자료구조] 그래프(Graph)란?

그래프(Graph)란?

그래프는 여러 개의 노드(node)(정점(vertex))와 이를 연결하는 간선(Edge)로 이루어진 비선형 자료구조이다.

비선형 구조: 데이터를 일렬으로 구성하지 않고, 자료 순서나 관계가 복잡한 자료구조

그래프 용어

용어

• 정점(Vertice)
  • 노드(node)라고도 하는 데이터가 저장되는 그래프의 기본 원소
• 간선(Edge)
  • 정점을 연결하는 선
• 인접 정점(Adjacent Vertex)
  • 특정 정점에 간선으로 직접 연결되어 있는 정점
• 단순 경로(Simple-path)
  • 시작 정점에서 끝 정점까지 가는 경로 중 어떤 정점도 두 번 이상 방문하지 않는 경로
• 차수(Degree)

    - 무방향 그래프에서 하나의 정점에 인접한 정점의 수(위 사진에서 3의 정점은 3(1, 4, 5와 연결됨))

• 진출 차수(Out-degree)
  • 한 정점에서 진출(나가는 간선)하는 간선의 수
• 진입 차수(In-degree)
  • 한 정점에 진입하는 간선의 수
• 사이클(Cycle)
  • 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 함
• 자기 루프(Self Loop)

• 정점에서 진출하는 간선이 바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 표현한다.
• 위 사진에서 B가 자기 루프이다.

그래프 종류

그래프 구현

그래프는 인접 행렬을 이용하여 구현하는 방식과 인접 리스트를 이용하여 구현하는 방식이 존재한다.

인접 행렬

2차원 배열을 이용하여 그래프를 구현하는 방식이다. 두 정점이 이어져 있다면 1, 이어져 있지 않다면 0으로 표현한다. 인접 행렬을 이용한 방식은 정점 간 관계 유무를 판단하고 가장 빠른 경로를 찾고자 할 때 주로 사용하여 O(1)의 시간 복잡도를 갖고 있다. 하지만 데이터가 커질 수록 2차원 배열도 커지기 때문에 많은 공간(메모리)를 차지하고 모든 정점 간의 간선 유무를 저장해야 하기 때문에 O(n^2)의 시간 복잡도를 갖는다.

인접 리스트

정점과 정점의 연결을 리스트 형태로 표현하는 방식이다. 특정 정점을 Key로 두고 해당 정점과 간선으로 연결된 정점을 Value로 두어 표시한다. 위 사진에서 정점 1은 2, 3, 4 정점과 연결되어 있고 정점 2는 1, 3 정점과 연결되어 있다.
인접 리스트를 이용한 방식은 인접 행렬을 이용한 방식보다 공간(메모리)를 적게 사용하고 연결 정보를 탐색할 때 O(n)의 시간 복잡도를 갖는 장점이 있다. 하지만 특정 점들이 연결되어 있는지 확인하려면 시간이 오래 걸리고 구현이 어렵다는 단점이 있다.

그래프 탐색 알고리즘

그래프를 이용한 탐색 알고리즘은 DFS와 BFS가 존재한다. 두 알고리즘은 추후 자세하게 공부할 것이므로 간단하게만 설명하겠다.

DFS(Depth-First Search) - 깊이 우선 탐색

시작 정점에서 출발하여 더 이상 연결된 노드가 존재하지 않을 때까지 자식 노드를 탐색한다. 계속 탐색하다 더 이상 노드가 존재하지 않는다면 한 단계 이전으로 돌아가서 다른 방향으로 다시 탐색을 실행하는 방식이다.

BFS(Breadth-First Search) - 너비 우선 탐색

시작 정점에 인접하는 자식 노드들은 모두 탐색한다. 연결된 자식 노드를 모두 탐색했다면 자식 노드 깊이로 내려가서 다시 인접하는 자식 노드들을 모두 탐색하는 방식이다.

출처

https://medium.com/depayse/kotlin-data-structure-graph-135edd3646ae
https://velog.io/@kwontae1313/%ED%8A%B8%EB%A6%AC%EC%99%80-%EA%B7%B8%EB%9E%98%ED%94%84%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90
https://velog.io/@vagabondms/DFS-vs-BFS