[TIL] 그래프 1편 - 그래프 정의, 특징, 종류, 구성 요소

그래프 이론 지식 맵

그래프 이론의 지식맵

그래프를 본격적으로 공부하기 전에 지식 지도를 머리 속에 넣어두고 시작하자. 각 개념이 전체 그래프 이론에서 어떤 위치를 차지하고 있는지 이해할 수 있을 것이다. 오늘 다룰 내용은 그래프의 기본 개념과 구성 요소 Vertex(또는 Edge), Node(또는 Arc)이다.  

 

그래프(Graph)란?

그래프는 노드(또는 정점)와 엣지(또는 간선)의 집합으로 구성된 추상적인 자료구조이다. 하지만 그래프 단순히 데이터를 저장하는 구조로만 이해하면 안된다. 그래프는 복잡한 관계를 모델링하고 분석하는 도구로서 알고리즘 설계와 문제 해결에 광범위하게 사용되기 때문이다. 다음은 그래프의 활용 분야와 예시다. 

분야	예시	노드	엣지	활용
소셜 네트워크 분석	Facebook, LinkedIn	사용자	친구 관계	친구 추천, 영향력 있는 사용자 파악
교통 및 내비게이션	Google Maps, 네이버 지도	교차로	도로	최단 경로 찾기, 교통 흐름 분석
컴퓨터 네트워크	인터넷 라우팅	라우터	네트워크 연결	효율적인 데이터 전송 경로 설계
추천 시스템	Netflix, Amazon	사용자, 상품	선호도	사용자 취향 분석, 맞춤형 추천
생물학 연구	단백질 상호작용 네트워크	단백질	상호작용	질병 메커니즘 연구, 신약 개발
프로젝트 관리	PERT 차트	작업	작업 간 의존성	일정 관리, 중요 경로 분석
검색 엔진	Google PageRank	웹페이지	하이퍼링크	웹페이지 중요도 평가, 검색 결과 순위 결정
게임 개발	체스 AI, 미로 게임	게임 상태	가능한 이동	최적 전략 탐색, 경로 찾기

 

놀랍지 않은가? 그래프의 이러한 다양한 응용은 우리 주변의 복잡한 시스템을 이해하고 최적화하는 데 큰 도움을 준다. 특히 주목할 만한 점은 그래프가 단순히 정적인 구조를 표현하는 데 그치지 않고, 동적인 프로세스와 알고리즘의 기반이 된다는 것이다. 

 

예를 들어, 소셜 네트워크에서 그래프는 단순히 친구 관계를 저장하는 데 그치지 않는다. 이를 바탕으로 정보의 확산 과정을 시뮬레이션하거나, 커뮤니티 구조를 파악하는 등 복잡한 사회 현상을 분석할 수 있다.

 

그래프의 구성 요소

특성	Vertex (정점) / Node (노드)	Edge (간선)  / Arc (호)
정의	그래프의 기본 단위	두 정점 사이의 연결
역할	개체나 상태를 나타냄	정점 간의 관계나 연결을 표현
그래픽 표현	점이나 원으로 표시	선이나 화살표로 표시
특징	고유한 식별자 가능, 데이터나 속성 포함 가능	방향성 가능 (유향 그래프), 가중치 가능 (가중 그래프)
예시	소셜 네트워크의 사용자, 컴퓨터 네트워크의 기기	소셜 네트워크의 친구 관계, 컴퓨터 네트워크의 연결

 

* Vertex와 Node는 동의어로 같은 개념을 나타낸다. Vertex는 주로 수학에서 많이 쓰이고, 컴퓨터 과학에서는 Node를 더 많이 쓰는 경향이 있다. 

* Edge와 Arc는 기본적으로 동의어지만 Edge는 주로 방향성이 없는 그래프(무향 그래프)에서 사용되며, 방향성이 있는 그래프(유향 그래프)에서는 Arc가 사용되는 경향이 있다. 

 

그래프의 특징과 종류 

① 방향성이 있을 수도 있고 없을 수도 있다

엣지에 방향이 없어 양 방향으로 이동 가능한 그래프를 무향 그래프(Undirected Graph)라고 한다. 간선에 방향이 있어 한 방향으로만 이동 가능한 그래프를 유향 그래프(Directed Graph)라고 한다. 참고로, 엣지에 방향이 없으면 양방향으로 이동이 가능하다는 뜻이다.  

 

② 엣지에 가중치가 할당될 수 있다

가중치는 엣지에 할당된 값으로, 거리, 비용, 중요도 등을 나타낼 수 있다. 모든 엣지의 가중치가 동일하거나 무시되는 그래프를 비가중 그래프라고 한다. 각 엣지에 서로 다른 가중치가 할당되는 그래프를 가중 그래프라고 한다.  

 

③ 루프와 멀티플 엣지가 존재할 수다 

그래프에는 자기 자신으로 돌아오는 루프나 두 노드 사이에 여러 엣지가 있을 수 있다. 루프(Loop)는 한 노드에서 시작해 같은 노드로 돌아오는 엣지다. 멀티플 엣지(Multiple Edges)는 두 노드 사이에 여러 개의 간선이 존재하는 경우이다. 

 

④ 연결성이 있을 수도 있고 없을 수도 있다

연결성은 그래프의 모든 노드가 어떤 경로로든 서로 연결되어 있는지를 나타낸다. 모든 노드가 어떤 경로로든 연결되어 있든 연결 그래프(Connected Graph)라고 한다. 반대로 서로 연결되지 않은 부분 그래프가 존재하면 비연결 그래프(Disconnected Graph)라고 한다.

 

하나 알아두어야 할 점은 이러한 특징들은 서로 조합될 수 있다는 사실이다. 예를 들어, 유향이면서 가중치가 있는 그래프나, 무향이면서 다중 엣지를 가진 연결 그래프 등이 있을 수 있다. 

 

그래프 코드로 표현하기 (Python)

파이썬에서는 라이브러리를 활용하거나 리스트와 딕셔너리를 사용하여 쉽게 그래프를 표현할 수 있다. 여기서는 리스트와 딕셔너리를 사용하여 그래프를 표현하는 방법을 알아보자. 

예시) 3개의 노드 그래프

인접 행렬을 사용한 그래프 표현 (리스트 사용)

# 노드 정의
nodes = ['A', 'B', 'C']

# 인접 행렬
adjacency_matrix = [
    [0, 1, 1],  # A의 연결: B, C와 연결됨
    [1, 0, 1],  # B의 연결: A, C와 연결됨
    [1, 1, 0]   # C의 연결: A, B와 연결됨
]

2차원 리스트(리스트 안에 리스트가 포함된 형태)를 사용하여 노드 간의 연결을 표현한다. 0은 연결되지 않음을, 1은 연결됨을 나타낸다. 장점은 두 노드 간의 연결을 빠르게 확인할 수 있다는 점이다 (O(1) 시간 복잡도). 단점은 메모리 사용량이 많고, sparse graph(연결이 적은 그래프)에서는 비효율적이다. 

 

인접 리스트를 사용한 그래프 표현 (딕셔너리 사용)

# 인접 리스트 
adjacency_list = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

각 노드를 키로, 그 노드와 연결된 노드들의 리스트를 값으로 하는 딕셔너리를 사용한다. 장점은 메모리를 효율적으로 사용하며, 특히 sparse graph에 적합하다. 단점은 특정 두 노드 간의 연결을 확인하는 데 시간이 더 걸릴 수 있다 (최악의 경우 O(V) 시간 복잡도, V는 노드의 수) 

 

인접 행렬 vs 인접 리스트 간단 비교

특성	인접 행렬	인접 리스트
구조	2차원 배열	딕셔너리 또는 리스트
메모리	모든 경우 V^2	실제 간선 수에 비례
간선 확인	매우 빠름 O(1)	상대적으로 느림 O(V)
모든 간선 탐색	느림 O(V^2)	빠름 O(V+E)
노드 추가/제거	어려움	쉬움
적합한 경우	작고 밀집한 그래프	크고 희소한 그래프