10장 그래프

 

연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성된 그래프 G를 G=(V, E)로 정의한다.

그래프는 간선의 방향성 유무에 따라서 방향 그래프와 무방향 그래프가 있고, 연결정도에 따라서 연결 그래프와 단절 그래프, 완전 그래프가 있다. 그리고 가중치를 가진 간선으로 이루어진 가중치 그래프가 있다.

 

 

그래프를 구현하기 위해서 표현하는 방법은 순차 자료구조 방식을 이용하는 2차원 배열의 인접 행렬 방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있다.

1. 인접 행렬

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다.

 

	A	B	C	D
A	0	1	0	1
B	0	0	1	1
C	0	0	0	1
D	0	0	0	0

2. 인접 리스트

인접 리스트는 그래프의 연결 관계를 vector의 배열(vector<int> adj[])로 나타내는 방식입니다. 이 때, vector<int>에는 노드의 번호가 직접 저장됩니다.

※ 순서는 의미가 없습니다