19. [JAVA] 그래프(Graph)

[ 참 조 블 로 그 ]

 

https://velog.io/@falling_star3/%EA%B7%B8%EB%9E%98%ED%94%84Graph-%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC%EA%B3%BC-%EC%9D%B8%EC%A0%91%EB%A6%AC%EC%8A%A4%ED%8A%B8

[자료구조] 그래프(Graph): 인접행렬과 인접리스트

 

 

---

 

 

[ Graph 란? ]

 

그래프란??

 

노드(Node) 와 간선(Edge)로 연결관계를 표현하는 자료구조 이다

노드는 정점(Vertex)라고 불리기도 한다

 

 

(1) 노드(node)

 

정점(vertex) 라고도 하며 데이터가 저장되는 그래프의 기본 원소

 

(2) 간선(edge)

 

링크라고도 하며 노드 간의 관계

 

 

 

[ 그래프의 종류 ]

 

 

 

[ 그래프의 구현 ]

 

그래프의 구현 방법에는 두 가지 방법이 있다

 

 

(1) 인접 행렬

 

노드의 개수가 n 이라면 n * n 형태의 2차원 배열로 그래프를 표현하는 것

 

간단하게 이야기하자면 arr [ i ] [ j ] 라는 배열이 있을 때

 

1 -> 2 이면 arr [1][2] 는 1이 되는 것이다

 

 

자세한 것은 위 사진을 보면 바로 이해할 수 있을 것 이다

 

 

 

[장점]

 

2차원 배열에 모든 노드들의 간선 정보가 있기 때문에, 두 노드를 연결하는 간선을 조회 할 때 O(1) 의 시간 복잡도를 가진다

 

[단점]

 

간선의 수와 무관하게 항상 n^2 크기의 2차원 배열이 필요하므로 메모리가 낭비된다

그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n^2)의 시간이 소요된다

 

 

 

 

 

 

(2) 인접 리스트(Adjacency List)

 

그래프의 각 노드에 인접한 노드들을 연결리스트로 표현하는 방법이다

 

즉, 노드의 개수만큼 인접 리스트가 존재하며, 각각의 인접리스트에는 인접한 노드 정보가 저장된다. 그래프는 각 인접 리스트에 대한 헤드 포인터를 배열로 가진다

 

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

 

 

 

[ 장 점 ] 

 

존재하는 간선만 관리하므로 보다 메모리 사용이 효율적이다

 

[ 단 점 ]

 

두 노드를 연결하는 간선을 조회하거나 노드의 차수를 알기 위해서는 노드의 인접 리스트를 탐색해야 하므로 노드의 차수만큼의 시간이 필요하다