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

말하기에 앞서 우선 그래프는 비선형 자료구조이다 

 

 

비선형자료구조

 

• 데이터를 일렬로 구성하지 않고 자료 순서나 관계가 복잡한 자료구조 
• 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태
• 트리와 그래프가 대표적이고 계층적 구조를 나타내기에 적절하다

---

💡그래프란?

 

• 여러 개의 노드(node)와 이 노드들을 연결하는 간선(edge) 으로 관계를 표현한 자료구조이다.
• 정확히는 정점(vertex) 간의 관계를 표현한 조직도 이다.

 

구성 요소

그래프 구성 요소

• 노드(node) : 정점(Vertice) 라고도 하는 데이터가 저장되는 그래프의 기본 원소
• 간선(edge) : 노드 간의 관계를 나타내는 선
• 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결되어 있는 정점 ex) 1 노드 기준으로 인접 정점은 0, 2, 3 이다
• 단순 경로(Simple-path) : 경로 중 반복되는 정점이 없는 것
• 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 ex) 3 노드의 차수는 3이다
• 진출 차수(Out-degree) : 한 정점에서 진출 하는 간선의 수 
• 진입 차수(In-degree) : 한 정점에서 진입 하는 간선의 수
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아 갈 수 있다면 사이클이다
• 자기 루프(Self Loop) : 정점에서 진출하는 간선이 바로 자기 자신에게 진입하는 경우 

 

 

그래프 특징

 

• 무방향성
  • 무방향 그래프는 간선에 방향이 없는 그래프를 말한다
  • 양쪽 방향으로 모두 이동할 수 있다

• 방향성 
  • 방향 그래프는 간선에 방향이 있는 그래프이다
  • 따라서 간선은 한 노드에서 다른 노드로 향하는 방향이 있다

• 가중치
  • 가중 그래프는 간선에 가중치가 부여된 그래프이다 즉, 간선에 가중치를 부여할 수 있다
  • 간선에 대한 추가 정보를 나타내고 각 간선의 가중치는 일반적으로 거리, 비용 또는 우선순위 등을 나타낸다
• 연결성
  • 그래프 내의 노드나 간선이 얼마나 서로 연결되어 있는지를 나타낸다
  • 네트워크나 시스템에서 중요한 속성 중 하나로 연결성이 높을 수록 정보나 자원의 흐름이 원할해질 수 있다

 

 

 

그래프 구현

 

그래프를 구현하는 방식에는 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 방식이 있다

 

 

인접 행렬 (Adjacency Matrix)

인접 행렬 예시

• 서로 다른 정점들이 인접한 상태인지를 표시한 2차원 배열 형태의 행렬이다.
• 이어져있다면 1(true), 그렇지 않다면 0(false)로 표시한다
• 인접 행렬은 정점 간 관계 유무를 파악하는데 주로 사용하며 이때의 시간 복잡도는 O(1)이다
• 가장 빠른 경로를 찾고자 할 때도 많이 사용된다
• 데이터가 커짐에 따라 2차원 배열도 계속 커지기 때문에 많은 공간을 낭비하고 모든 정점에 대한 간선 정보를 대입해야 해서 O(n^2)의 시간 복잡도가 소요한다

 

 

인접 리스트 (Adjacency List)

인접 리스트 예시

 

• 인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.
• 인접 리스트는 인접 행렬에 비해 공간 낭비가 적어서 메모리를 효율적으로 사용할 수 있다.
• 또한 연결 정보를 탐색할 때도 O(n)의 시간이면 충분하다.
• 다만 특정 점들이 연결되어 있는지 확인하려면 시간이 오래 걸리고, 구현이 비교적 어렵다는 단점이 있다

 

그래프 탐색 

그래프는 배열 처럼 정렬이 되어 있지 않아서 탐색을 하려면 특정한 방법으로 탐색해야한다

대표적인 탐색법으로는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)가 있다

 

DFS (Depth-First Search)

• DFS(깊이 우선 탐색)는 하나의 정점에서 시작해 해당 경로를 끝까지 탐색한 후, 다음 경로로 넘어가 탐색한다
• 재귀 호출 또는 스택을 사용하여 구현한다

 

BFS (Breadth-First Search)

• BFS(너비 우선 탐색)는 시작 정점을 방문한 후, 인접한 모든 정점을 방문한 하고, 시작 정점에서 인접한 모든 정점을 우선방문하는 방법이다
• 큐를 사용해서 현재 위치에서 갈 수 있는 것들을 큐에 넣고 빼면서 탐색하는 방식으로 구현한다