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

그래프 (Graph)

• 노드(Node, Vertex), 간선 (Edge)의 집합
• 객체 사이의 연결 관계를 표현하는 자료구조
• 가장 표현력이 우수한 자료구조로, 현실세계의 다양한 문제를 효과적으로 모델링하는 목적
• 트리는 계층구조가 아닌 일반적인 관계는 나타낼 수 없다는 한계를 지님

​

그래프 종류

구분	종류	설명
간선의 방향성	무방향 그래프	방향X
	방향 그래프	방향O
간선의 가중치	가중 그래프	간선에 가중치 할당
구조적 특징	완전 그래프	연결 가능한 최대 간선 수 가짐
	부분 그래프	원래 그래프의 일부분
	다중 그래프	중복된 간선 포함

​

1. 무방향 그래프

• 간선에 방향이 없는 그래프

무방향 그래프 A

노드 : V(A) = { A, B, C, D, E}

간선 : G(A) = {(A,B), (B, D), (C,D), (D,E), (C,E), (A,C)}

​

​

2. 방향 그래프

• 간선에 방향이 있는 그래프

방향 그래프

노드 : V(A) = { A, B, C, D, E}

간선 : G(A) = {<A,B>, <B, D>, <C,D>, <D,E>, <E,C>, <A,C>}

​

3. 가중 그래프

• 간선에 가중치 할당
• 가중치 종류 : 비용, 거리 등
• 무방향 가중 그래프 : 무방향 그래프 + 가중치
• 방향 가중 그래프(네트워크) : 방향 그래프 + 가중치

방향 가중 그래프(네트워크)

​

4. 완전 그래프 (Complete Graph)

• 그래프 내의 모든 노드가 1:1 간선으로 연결된 경우
• 연결 가능한 최대 간선 수를 가진 그래프

​

5. 부분 그래프 (Sub Graph)

• 원래 그래프에서 일부 노드, 간선을 제외하여 만든 그래프

​

6. 다중 그래프 (Multi Graph)

• 중복된 간선을 포함하는 그래프

​

​

그래프 관련 용어

용어	설명
인접	- 2개의 노드를 연결하는 간선이 존재하는 경우, 서로 인접했다고 한다.
부속	- 2개의 노드를 연결하는 간선이 존재하는 경우, 해당 간선은 두 노드에 각각 부속되었다고 한다.
차수	- 노드에 연결된 간선의 개수
경로	- 노드 A에서 B까지에 이르는 간섭들의 인접 노드를 순서대로 나열한 리스트
동일성	- 서로 다른 2개의 그래프가 서로 같은지를 판단 - 시각적 표현이 달라도 노드, 간선의 집합이 같으면 같은 그래프
루프	- 임의의 노드에서 자기 자신으로 이어지는 간선

​