자료구조 : Graph

rlask.rbs·2025년 7월 7일

Graph python 그래프 자료구조

[자료구조]

목록 보기

1/5

그래프(Graph)

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

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

그래프의 구성 요소

그래프의 정의에서 보았듯이, 그래프는 정점과 간선으로 이루어 져 있다.
정점은 그래프에서 가장 기본적인 구성 요소이며, 각 정점은 고유한 이름(identifier)을 가진다.
간선은 정점과 정점을 연결하는 선으로, 두 개의 정점을 연결하는 데 사용된다..

그래프의 특징

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

방향성(Directionality)
그래프의 간선은 방향성이 있을 수 있으며, 한쪽 방향으로만 이동할 수 있다.
이러한 그래프를 방향 그래프(directed graph) 또는 유향 그래프(digraph)라고 부른다.
가중치(Weight)
그래프의 간선에는 가중치(weight)를 부여할 수 있다.
가중치를 부여한 그래프를 가중치 그래프(weighted graph)라고 부르며, 보통은 거리, 비용, 우선순위 등을 나타내는 데 사용된다.
연결성(Connectivity)
그래프에서 노드와 노드 사이에 경로가 존재하면, 두 노드는 연결되었다고 말한다. 그래프가 연결되어 있는 경우 연결 그래프(connected graph)라고 부르며, 그렇지 않은 경우 비연결 그래프(disconnected graph)이다.
사이클(Cycle)
그래프에서한 노드에서 시작하여 경로를 따라가면서 마침내 자기 자신으로 돌아오는 경로를 사이클(cycle)이라고 부른다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph)라고 부르며, 사이클이 있는 그래프를 순환 그래프(cyclic graph)라고 부른다.

그래프 종류

무방향 그래프(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)
방향 그래프에서, 모든 노드 사이에 양방향 경로가 존재하는 그래프이다.

그래프 구현 방법

인접 행렬 방식 (Adjacency Matrix)

인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.

노드들 간에 직접 연결이 되어있으면 1을, 아니면 0을 넣어서 행렬을 완성시킨 것이다.
A와 A 끼리는 자기 자신이니 0으로 표현하고, 연결되어 있다면 1로, 아니라면 0으로 표현한다.

graph = [
    [0, 1, 1, 0], 
    [1, 0, 1, 1], 
    [1, 1, 0, 0], 
    [0, 1, 0, 0]
]

인접 행렬의 장점

2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다.
인접리스트에 비해 구현이 쉽다.

인접 행렬의 단점

모든 정점에 대해 간선 정보를 대입해야 하므로 O(n^2) 의 시간복잡도가 소요된다.
무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된

인접 리스트 방식 (Adjacency List)

인접리스트는 그래프의 노드를 리스트로 표현한 것이다.

인접리스트는 모든 노드에 연결된 노드들의 정보를 차례대로 기록하는 방식이다.
파이썬의 append()와 같은 메소드를 가지고 있음으로 배열과 연ㄱ려 리스트의 기능을 모두 제공한다.

graph = [[] for _ in range(4)]

# 노드 A
graph[0].append('B')
graph[0].append('C')

# 노드 B
graph[1].append('A')

...

graph = [['B', 'C'], ['A', 'C', 'D'], ['A', 'B'], ['B']]

인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 비교

특징	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
정의	2차원 배열을 사용하여 정점 간의 연결 상태를 표현	각 정점에 연결된 정점들을 리스트로 저장하여 표현
공간 복잡도	$O(V^2)$ (V는 정점의 개수)	$O(V+E)$ (V는 정점의 개수, E는 간선의 개수)
간선 추가/삭제	$O(1)$ (해당 위치에 값만 변경)	$O(deg(V))$ (해당 정점의 차수)
특정 간선 존재 여부 확인	$O(1)$ (배열 접근)	$O(deg(V))$ (리스트 순회)
모든 간선 확인	$O(V^2)$	$O(V+E)$
장점	- 간선 존재 여부 확인이 빠름. - 구현이 간단함.	- 희소 그래프(sparse graph)에 효율적. - 메모리 사용이 효율적.
단점	- 희소 그래프에서 메모리 낭비가 심함. - 정점 수가 많을 경우 비효율적.	- 간선 존재 여부 확인이 상대적으로 느림. - 구현이 복잡할 수 있음.
적합한 경우	- 밀집 그래프(dense graph) (간선이 정점 수의 제곱에 가까운 경우)	- 희소 그래프(sparse graph) (간선이 정점 수에 비해 적은 경우)

그래프의 장단점

장점

복잡한 관계를 직관적으로 표현할 수 있다.

네트워크 구조를 표현할 수 있어서 소셜 네트워크, 전력망, 노선도 등의 문제를 다룰 수 있다.

다양한 최적화 문제를 풀 수 있다.
예를 들어, 최단 경로 문제나 최소 신장 트리 문제 등 다양한 그래프 알고리즘을 사용하여 최적화 문제를 풀 수 있다.

단점

데이터의 규모가 커질수록 계산 비용이 증가한다. 대형 그래프에서는 탐색 비용과 알고리즘의 수행 시간 등이 중요한 문제가 될 수 있다.

그래프의 구성이 복잡하면 이를 이해하기 어려울 수 있다.

방향성 그래프에서는 경로의 유무가 중요하므로, 경로가 존재하지 않는 경우에는 이를 고려하여 알고리즘을 설계해야 한다.

rlask.rbs

KHU I.E 23

다음 포스트