그래프의 정의와 특징
정의
그래프는 정점(Vertex) 과 그 정점을 연결하는 간선(Edge) 으로 구성됩니다. 이러한 정점과 간선의 집합으로 이루어진 자료구조를 그래프라고 합니다.
특징
- 방향성: 그래프는 방향성이 있을 수도 있고, 없을 수도 있습니다. 방향성이 있는 그래프를 유향 그래프(Directed Graph), 없는 그래프를 무향 그래프(Undirected Graph) 라고 합니다.
- 가중치: 간선에 가중치가 할당되어 있을 수 있습니다. 이를 가중 그래프(Weighted Graph) 라고 합니다.
- 루프와 다중 간선: 그래프에는 자기 자신으로 돌아오는 루프나 두 정점 사이에 여러 간선이 있을 수 있습니다.
- 연결성: 모든 정점이 어떤 경로로든 연결되어 있으면 연결 그래프(Connected Graph) 라고 합니다.
사용 예
- 네트워크 디자인: 컴퓨터 네트워크, 전화 네트워크 등
- 경로 찾기: 지하철 노선도, 지도 앱
- 소셜 네트워크: 친구 관계, 팔로우 관계 등
- 탐색 알고리즘: 웹 크롤러, 검색 알고리즘
- 작업 스케줄링: 작업 간의 의존성 표현
C와 Python에서의 비교
C
C에서는 주로 인접 리스트나 인접 행렬을 이용해서 그래프를 구현합니다. 구조체와 배열, 포인터를 사용하여 복잡하게 메모리를 관리해야 하며, 간선 추가나 삭제에 있어서도 직접 코드를 작성해야 합니다.
typedef struct {
int vertex;
struct Node* next;
} Node;
typedef struct {
Node* head;
} AdjList;
typedef struct {
int numVertices;
AdjList* array;
} Graph;Python
Python에서는 라이브러리를 활용하거나 리스트와 딕셔너리를 사용하여 쉽게 그래프를 표현할 수 있습니다. 특히 networkx와 같은 라이브러리를 이용하면 고급 그래프 알고리즘을 쉽게 적용할 수 있습니다.
# 인접 리스트를 이용한 예
graph = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'E'], 'D': ['B'], 'E': ['C']}정리
C는 메모리 관리와 저수준의 작업이 필요하지만, 성능 측면에서 이점이 있을 수 있습니다. Python은 사용이 간편하고 라이브러리가 풍부하여 빠르게 프로토타입을 개발할 수 있습니다.
추가
"arc"는 그래프 이론에서 주로 "간선(Edge)"와 같은 의미로 사용되며, 보통 유향 그래프(Directed Graph)에서 간선을 지칭할 때 사용됩니다. 즉, 유향 그래프에서는 시작 정점(Vertex)에서 끝 정점까지의 방향성이 있는 연결선을 "Arc"라고 부릅니다.
간선(Edge)과 Arc의 주된 차이점은 다음과 같습니다:
- 간선(Edge): 무향 그래프(Undirected Graph)에서 두 정점을 연결합니다. 방향성이 없어, 정점 A와 정점 B를 연결하는 간선은 "A-B"나 "B-A"로 동일하게 표현됩니다.
- Arc: 유향 그래프(Directed Graph)에서 두 정점을 연결합니다. 방향성이 있어, 정점 A에서 정점 B로의 Arc와, 정점 B에서 정점 A로의 Arc는 다르게 취급됩니다.
이러한 Arc는 네트워크 플로우, 작업 스케줄링, 방향성이 있는 관계를 모델링하는 데 주로 사용됩니다.
