[자료구조] 그래프 구현

1. 그래프 구현 방법

• 인접 행렬(adjacent matrix) : 2차원 배열 사용
• 인접 리스트(adjacency list) : 연결리스트 사용 

1) 인접 행렬 방법

• if(간선 (i, j)가 그래프에 존재) M[i][j] = 1. 존재하지 않으면 M[i][j] = 0

 

2. 인접 행렬

• 행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법
• 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장
• n개의 정점을 가진 그래프 : n * n 정방 행렬
• 행렬의 행 번호와 열 번호 : 그래프의 정점
• 행렬값 : 두 정점이 인접되어 있으면 1, 인접되어있지 않으면 0

 

1) 인접 행렬 예

 

인접 행렬 예

 

무방향 인접 행렬 예

 

 

방향 인접 행렬 

 

2) 무방향 그래프

• 행 i의 합 = 열 i의 합 = 정점 i의 차수

 

3) 방향 그래프

• 행 i의 합 = 정점 i의 진출 차수(Out)
• 열 i의 합 = 정점 i의 진입 차수(In)

 

4) 단점

• n개의 정점을 가지는 그래프를 항상 n * n 개의 메모리 사용
• 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생

 

3. 인접 리스트(adjacent list)

• 각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트
• 각 정점의 차수만큼 노드를 연결
• 리스트 내의 노드들은 인접 정점에 대해 오름차순으로 연결

 

1) 노드

• 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성

(1) 정점의 헤드 노드

• 정점에 대한 리스트의 시작을 표현

 

2) n개의 정점과 e개의 간선을 가진 무방향 그래프의 인접 리스트

• 헤드 노드 배열의 크기 : n
• 연결하는 노드의 수 : 2e
• 각 정점의 헤드에 연결된 노드의 수 : 정점의 차수

 

3) n개의 정점과 e개의 간선을 가진 방향 그래프의 인접 리스트

• 헤드 노드 배열의 크기 : n
• 연결하는 노드의 수 : e
• 각 정점의 헤드에 연결된 노드의 수 : 정점의 진출 차수

 

4) 인접 리스트 예

 

(1) 무방향 인접 리스트

 

무방향 인접 리스트

 

(2) 방향 인접 리스트

 

 

방향 인접 리스트