그래프(Graph)에 대해 알아보자

그래프는 대표적인 비선형 자료구조이다. 선형자료구조와 다르게 데이터 요소들이 계층적으로 연결되어 있다.

그렇다면 비선형 자료구조란 무엇일까?

비선형자료구조란?

비선형 자료구조(Non-linear Data Structure)란 데이터를 일렬으로 구성하지 않고, 자료 순서나 관계가 복잡한 자료구조를 말한다.

• 비선형 자료구조는 자료를 계층적으로 구성한 자료구조로, 데이터가 일렬로 연결되는 선형 자료구조와 달리 분기점이나 사이클 등이 존재하여 비선형적인 구조를 가지고 있다.

• 비선형 자료구조는 선형 자료구조보다 복잡한 구조를 가지기 때문에 구현 및 관리가 어려울 수 있지만, 적절하게 활용하면 다양한 문제를 해결할 때 도움이 된다.

대표적인 비선형 자료구조로는 트리, 그래프, 맵, 해시테이블 등이 있다.

😀이번 포스팅에서는 대표적인 비선형 자료구조 중 그래프에 대해서 알아보자.

그래프란?

그래프는 여러 개의 노드(node)와 이들을 연결하는 간선(Edge)으로 이루어진 자료구조이다.

노드(node)는 정점(Vertex)으로 표현될 수 있다.

그래프의 구성 요소

그래프의 정의에서 보았듯이, 그래프는 정점과 간선으로 이루어 져 있다.

정점은 그래프에서 가장 기본적인 구성 요소이며, 각 정점은 고유한 이름(identifier)을 가집니다.

간선은 정점과 정점을 연결하는 선으로, 두 개의 정점을 연결하는 데 사용됩니다.

😀예를들어 V라는 장소에서 U라는 장소로 무엇(인도, 차도, 육교, 철도 등)을 통해 간다고 했을 때 V나 U와 같은 장소는 정점(or노드)이 되고, 무엇에 해당하는 수단이 간선이 된다.

정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 점점의 indegree라고 한다.

그래프의 특징

😀그래프는 여러가지 특징을 가질 수 있다. 다만 하나의 그래프가 모든 특징을 가지는 것이 아니라 특징을 가짐에 따라 그래프의 종류도 나뉘어 진다.

• 무방향성(Unidirectionality)
  그래프의 간선은 방향성이 없을 수 있으며, 양쪽 방향으로 모두 이동할 수 있습니다.
  이러한 그래프를 무방향 그래프(undirected graph)라고 부른다.
  😀양쪽의 방향으로 이동할 수 있지만, 무방향 그래프라고 부른다. 무방향의 의미가 방향의 강제하는 일방통행이 없다는 의미라고 생각할 수 있다.

• 방향성(Directionality)
  그래프의 간선은 방향성이 있을 수 있으며, 한쪽 방향으로만 이동할 수 있다.
  이러한 그래프를 방향 그래프(directed graph) 또는 유향 그래프(digraph)라고 부른다.

• 가중치(Weight)
  그래프의 간선에는 가중치(weight)를 부여할 수 있다.
  가중치를 부여한 그래프를 가중치 그래프(weighted graph)라고 부르며, 보통은 거리, 비용, 우선순위 등을 나타내는 데 사용된다.

• 연결성(Connectivity)
  그래프에서 노드와 노드 사이에 경로가 존재하면, 두 노드는 연결되었다고 말한다. 그래프가 연결되어 있는 경우 연결 그래프(connected graph)라고 부르며, 그렇지 않은 경우 비연결 그래프(disconnected graph)이다.

• 사이클(Cycle)
  그래프에서 한 노드에서 시작하여 경로를 따라가면서 마침내 자기 자신으로 돌아오는 경로를 사이클(cycle)이라고 부른다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph)라고 부르며, 사이클이 있는 그래프를 순환 그래프(cyclic graph)라고 부른다.

• 차수(Degree)
  그래프에서 한 노드에 인접한 간선의 수를 차수(degree)라고 부른다. 무방향 그래프에서는 노드의 차수가 연결된 노드의 수와 같으며, 방향 그래프에서는 인접한 노드의 수와 나가는 노드의 수로 구분된다.

그래프의 종류

😀그래프의 종류는 그래프가 가지는 구조와 특징에 따라서 구분된다.

• 무방향 그래프(Undirected Graph)

  • 간선에 방향이 없는 그래프이다
    노드와 간선으로 이루어져 있으며, 노드 사이의 관계는 양방향이다.

• 방향 그래프(Directed Graph)

  • 간선에 방향이 있는 그래프이다.
    노드와 간선으로 이루어져 있으며, 노드 사이의 관계는 일방향이다.

• 가중치 그래프(Weighted Graph)

  • 간선에 가중치(weight)가 있는 그래프이다.
    가중치는 간선의 비용, 거리, 시간 등을 나타낸다.

• 이분 그래프(Bipartite Graph)

  • 무방향 그래프에서, 노드를 두 그룹으로 나누었을 때, 같은 그룹 내의 노드는 서로 인접하지 않고, 다른 그룹의 노드와만 인접하는 그래프이다.

• 비순환 그래프(Acyclic Graph)

  • 사이클이 없는 그래프이다.
    방향 그래프에서, 유향 비순환 그래프(Directed Acyclic Graph, DAG)라고도 한다.

• 완전 그래프(Complete Graph)

  • 모든 노드가 서로 연결된 그래프이다.
    노드 수가 n일 때, 간선 수는 n(n-1)/2 입니다.
  • 완전 그래프는 항상 연결그래프를 포함한다.

• 부분 그래프(Subgraph)

  • 주어진 그래프의 일부 노드와 간선으로 이루어진 그래프이다.

• 연결 그래프(Connected Graph)

  • 무방향 그래프에서, 모든 노드 사이에 경로가 존재하는 그래프이다.

• 비연결 그래프(Disconnected Graph)

  • 무방향 그래프에서, 연결 그래프가 아닌 그래프이다.

• 강결합 그래프(Strongly Connected Graph)

  • 방향 그래프에서, 모든 노드 사이에 양방향 경로가 존재하는 그래프이다.

그래프의 장단점

😀일반적으로 그래프를 사용하였을 때 장점과 단점이 존재한다. 이에 대해 알아보고 보완할 방법을 생각해보자

장점

• 복잡한 관계를 직관적으로 표현할 수 있다.
• 네트워크 구조를 표현할 수 있어서 소셜 네트워크, 전력망, 노선도 등의 문제를 다룰 수 있다.
• 다양한 최적화 문제를 풀 수 있다.
  예를 들어, 최단 경로 문제나 최소 신장 트리 문제 등 다양한 그래프 알고리즘을 사용하여 최적화 문제를 풀 수 있다.

단점

• 데이터의 규모가 커질수록 계산 비용이 증가한다. 대형 그래프에서는 탐색 비용과 알고리즘의 수행 시간 등이 중요한 문제가 될 수 있다.
• 그래프의 구성이 복잡하면 이를 이해하기 어려울 수 있다.
• 방향성 그래프에서는 경로의 유무가 중요하므로, 경로가 존재하지 않는 경우에는 이를 고려하여 알고리즘을 설계해야 한다.

단점의 보완

• 분할 정복, 동적 계획법 등의 최적화 알고리즘을 사용하여, 계산 비용을 줄일 수 있다.
• 복잡해진 그래프를 시각화하는 방법을 고민하여, 데이터의 시각적 이해를 돕는 방법이 있다.
• 그래프를 단순화하여, 경로가 존재하지 않는 경우에도 유용한 결과를 도출할 수 있도록 만든다.
  예를 들면, 가중치를 조절하여 일정 이하의 가중치를 가진 간선들은 무시하는 방법을 생각할 수 있다.

참고자료(출처)
깃허브io 괭이쟁이 포스팅 [자료구조 1] 그래프(Graph) 이해하기
Velog tomato2532 포스팅 [자료구조] 그래프
깃허브io 권희정 포스팅 [자료구조] 그래프(Graph)란
Velog zion9948 포스팅 자료구조 트리와 그래프에 대해..
티스토리 이진섭 포스팅 [자료구조] 그래프(Graph)의 개념 설명
Velog kasterra 포스팅 핵심 자료구조 - 그래프 : 정의 및 표현