그래프(Graph)구현 : 인접행렬과 인접리스트

컴퓨터에서 그래프를 다룰때 대표적인 자료구조로는 인접행렬과 인접리스트가 있다.

 

📝목차

1. 인접행렬 (Adjacency Matrix) 2. 인접리스트 (Adjacency List)

---

 

1. 인접행렬 (Adjacency Matrix)

https://ko.wikipedia.org/wiki/%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC

인접행렬 - 위키백과, 우리 모두의 백과사전

• 2차원 배열을 사용해서 그래프를 표현하는 방식
• 노드의 개수가 n이라면 n*n 형태의 2차원 배열로 그래프의 연결관계를 표현
• edge와 상관없이 모든 node를 표현해야 하기 때문에  희소 그래프의 경우 메모리 낭비가 큼
• adj[i][j] : 노드 i에서 노드 j로 가는 엣지가 있으면 1, 없으면 0 
• 모든 노드들의 엣지 정보가 2차원 배열에 저장되어 있기 때문에 두 노드 간에 엣지의 유무를 존재할때 O(1)의 시간복잡도를 가진다.
• 그래프의 모든 간선 수를 알아내려면 2차원 배열 전체를 확인해야 하기 때문에 O(n^2)의 시간이 걸린다.

 

인접행렬을 이용한 그래프 

출처 : https://suyeon96.tistory.com/32

 

• (a), (b)는 무방향그래프로 두 개의 노드가 엣지에 동시에 연결되어 있어 대칭적 구조를 가진다.
• (c)는 유방향그래프로 i -> j로 가는 곳만 값이 들어가 있다.
• 가중치그래프의 경우 1대신 가중치를 넣어주면 된다. 이때 가중치가 0인것과 엣지가 없는 것은 구별되어야 한다.

 

 

2. 인접리스트 (Adjacency List)

https://en.wikipedia.org/wiki/Adjacency_list

Adjacency list - Wikipedia

• 연결리스트(Linked List)로 그래프를 표현하는 방식
• 노드의 개수가 n이라면 인접리스트가 n개 존재해서 각 노드마다 인접한 정점 정보 저장
• 그래프는 각 인접리스트에 대한 헤드포인터를 배열에 갖는다
• 실제 연결된 엣지만 저장하기 때문에 인접행렬보다 메모리 사용 효율적
• 두 노드 간에 엣지의 유무를 확인할 때 인접리스트를 탐색하므로 노드의 차수만큼  O(V) 시간 소요

 

인접리스트을 이용한 그래프

출처 : https://velog.io/@falling_star3/

• 가중치가 없는 무향 그래프에서는 인접한 노드의 정보를 저장
• 가중치가 있는 유향 그래프에서는 인접한 노드와 가중치 정보를 저장 ( 주로 vector<pair<int,int>> 로 구현) 

 

---

 

참고

https://iancoding.tistory.com/328

그래프 3) 인접행렬과 인접리스트의 차이

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): 인접행렬과 인접리스트