인접행렬과 인접리스트

<인접행렬 인접리스트란?>

+

그래프 관련 문제를 풀 때 연결관계를 나타내는 두 가지 방식이 있다. 인접행렬과 인접리스트.

-인접행렬이란?

인접행렬은 이차원 배열로 그래프의 연결관계를 나타낸 방식입니다.

adj[][]를 인접행렬이라고 할 때 adj[i][j]는 노드 i에서 노드 j로 가는 간선이 있을 경우에 1, 간선이 없을 경우에 0 입니다.

간선의 유무 대신 가중치 값을 넣을 수도 있습니다.

+

방향 그래프에서 i->j 로 가는 간선이 존재할 경우엔 다음과 같이 표현 adj[i][j] =1

무방향 그래프에선 adj[i][j]=1; adj[j][i]=1; 로 값을 줘야한다.

+

인접 행렬 장점

노드i 와 노드 j 가 연결되어 있는지 확인 : O(1) //adj[i][j]

노드i 주변 노드 탐색 시간 복잡도 : O(V) // 노드 개수:V 할 때 노드 i에 연결된 노드를 찾을 때 adj[i][1] ~ adj[i][V]를 돌아야하므로

모든 노드를 방문하는 경우 : O(V*V) //한 노드에 대해 탐색할 떄 O(V)인데 V번 탐색해야하므로

è인접 행렬로 탐색을 할 때에 노드의 개수는 1만개이고 간선개수는 2개일 때 비효율적인 동작을 하게된다.

이를 보안한 그래프가 인접리스트 방식!

 

 

-인접리스트란?

인접리스트란 그래프를 vector 배열로 나타내는 방식이다.

vector <int> adj[] 인접리스트가 있을 때 adj[i]는 노드 i에 연결된 노드들을 원소로 갖는다.

간선에 가중치가 있다면 vector <pair<int,int,> > adj[]로 나타내고 pair의 첫번째는 노드 정보, 두번째 인자는 가중치를 저장하여 표현한다.

https://sarah950716.tistory.com/12

+

무향그래프 표현은 인접행렬때와 마찬가지로 adj[i].push_back(j) 정도와 adj[j].push_back(i) 정보를 저장하면 된다.

+

노드 i와 연결정보가 있는 노드 정보만 리스트에 저장된다.

원소 개수 합이 간선 개수와 같다.

전체 노드 탐색 시간 복잡도 : O(E) //인접행렬은 O(V*v)

노드 i와 노드 j가 연결되어 있는지 : O(V)  //인접행렬은 O(1)