[JAVA] 자바 그래프와 인접행렬

그래프

 

 

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다.

그래프 G를 G=(V, E)로 표현하는데 V는 정점의 집합, E는 간선의 집합을 나타낸다.

강의에서는 1) 무방향 그래프 2) 방향 그래프 3) 가중치 그래프를 다룬다.

 

 

 

 

 

인접행렬, 인접리스트

 

출처 - https://velog.io/@falling_star3/그래프Graph-인접행렬과-인접리스트

 

 

그래프를 구현하는 방법에는 인접행렬(Adjacency Matrix)와 인접리스트(Adjacency List)가 있다.

• 인접행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

 

 

인접행렬(Adjacency Matrix)

노드의 개수가 n이라면 n*n 형태의 2차원 배열로 그래프의 연결 관계를 표현한다. 
인접 행렬에서 행과 열은 노드를 의미하며, 각각의 원소들은 노드 간의 간선을 나타낸다.
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

 

가중치가 없는 무방향 그래프
: 연결되어 있는 경우 행렬에서 1의 값을 가지고, 연결되지 않은 경우 0의 값을 가진다. 두 개의 노드에서 간선이 동시에 연결되어 있기 때문에 인접 행렬이 대칭적 구조를 가진다.

 

가중치가 있는 유방향 그래프
: 행렬에서 각 간선의 가중치 값이 저장된다. 이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 한다.

장점: 2차원 배열에 모든 노드들의 간선 정보가 있기 때문에, 두 노드를 연결하는 간선을 조회할 때 O(1) 시간복잡도를 가진다.
단점: 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.

 

 

 

인접리스트(Adjacency List)

그래프의 각 노드에 인접한 노드들을 연결리스트(Linked List)로 표현하는 방법이다.
즉, 노드의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 인접한 노드 정보가 저장된다. 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.

• 헤드포인터: 연결 리스트의 맨 처음 노드를 가리키는 포인터

 

가중치가 없는 무방향 그래프
: 그림과 같이 가중치 표현 없이 인접한 노드 정보가 저장된다.

 

가중치가 있는 유방향 그래프
: 종점 [노드 번호 | 간선의 가중치] 정보가 저장된다.

장점: 존재하는 간선만 관리하므로 보다 메모리 사용이 효율적이다.
단점: 두 노드를 연결하는 간선을 조회하거나 노드의 차수를 알기 위해서는 노드의 인접 리스트를 탐색해야 하므로 노드의 차수만큼의 시간이 필요하다.

 

 

 

 

 

1) 무방향 그래프

V(G1) = {1, 2, 3, 4, 5}, E(G1) = {(1, 2), (1, 3), (2, 4), (3, 4), (2, 5))}

1번과 2번은 서로 연결되어 있기 때문에 양방향이라고 볼 수도 있다. (1 -> 2, 2 -> 1)

 

 

G1의 인접행렬

1번 정점과 2번 정점이 연결되어 있기 때문에 1 -> 2, 2 -> 1 모두 표시해 줄 수 있다.

양방향의 특징을 지니기 때문에 인접행렬이 대칭적인 모양을 띄게 된다.

graph[a][b] = 1 혹은 0이라고 표현하는 것과 graph[b][a] = 1 혹은 0이라고 표현하는 것이 같은 것을 의미한다.

 

 

 

 

2) 방향 그래프

 

V(G2) = {1, 2, 3, 4, 5}, E(G2) = {<1, 2>, <1, 3>, <4, 2>, <3, 4>, <2, 5>)}

 

 

G2의 인접행렬

1번 정점과 2번 정점이 방향성을 가지고 연결되어 있기 때문에 1 -> 2라고만 표시해 줄 수 있다.

graph[a][b] = 1 혹은 0이라고 표현하는 것과 graph[b][a] = 1 혹은 0이라고 표현하는 것이 같은 것을 의미하지 않는다.

 

 

 

 

3) 가중치 그래프 ( 무방향, 방향 )

G3

W[1, 2] = 2

W[1, 3] = 4

W[4, 2] = 2

W[3, 4] = 5

W[2, 5] = 5

 

 

G3의 인접행렬

 

 

 

 

출처 : 인프런 자바 알고리즘 문제풀이 입문 : 코딩테스트 대비