패스트캠퍼스 JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 강의 4주차

ch.2 JavaScript 핵심 자료구조[그래프의 표현]

그래프란 ? 

그래프란 사물(vertex)의 정점과 간선(edge)은 표현하기위한 방법이다.

그래프는 두가지 방법으로 구현이 가능하다

• 인접행렬 : 2차원배열을 이용한 방법
• 인접 리스트 : 연결리스트를 이용한 방법

---

인접행렬

인접행렬 : 무방향 무가중치 그래프

무방향 무가중치 그래프는 모든 간선이 방향성과 가중치를 가지지 않는 그래프를 말한다.

 

인접 행렬의 장점은 구현이 쉽다는 점입니다. 

그리고, 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 O(1)이라는 시간 복잡도에 확인할 수 있다는 점이 있습니다. 

하지만, 치명적인 단점 또한 존재합니다. 전체 노드의 개수를 V개, 간선의 개수를 E개라고 해봅시다. 노드 i에 연결된 모든 노드들에 방문해보고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해보아야 하기 때문에 총 O(V)의 시간이 걸린다는 점입니다. 위의 그래프와 같은 경우 큰 차이가 느껴지지 않을 수도 있지만, 노드의 개수에 비해 간선의 개수가 훨씬 적은 그래프라면 이야기가 달라질 것입니다. 만약, 노드의 개수는 총 1억개인데 각 노드마다 연결된 간선이 많아봤자 2개인 그래프가 있다고 해봅시다. 그렇다면, 특정 노드와 연결된 노드들이 몇 번 노드인지 확인하기 위해 총 1억 개의 노드들을 모두 확인해봐야 하는 치명적인 문제가 발생하게 됩니다. 정작 연결된 노드는 많아봤자 2개 뿐일텐데 말입니다. (이러한 단점을 보완할 수 있는 연결 관계 표현 방식이 인접 리스트입니다.)

 

인접행렬 : 방향 가중치 그래프

방향 가중치 그래프는 모든 간선이 방향성과 가중치를 가지는 그래프를 말한다.

 

 

그렇다면, 위의 그래프처럼 간선에 방향이 있는 유향 그래프가 아닌, 간선에 방향이 없는 무향 그래프의 경우에는 어떻게 될까요?

노드 i에서 노드 j로 가는 간선이 있다는 말은 노드 j에서 노드 i로 가는 간선도 존재한다는 의미가 되겠죠? 따라서, 인접 행렬이 대각 성분(adj[i][j]에서 i와 j가 같은 원소들)을 기준으로 대칭인 성질을 갖게 됩니다. 위의 그래프의 간선들을 방향이 없는 간선으로 바꿔주면 아래와 같은 인접행렬을 갖게 됩니다.

---

---

https://fastcampus.co.kr/dev_online_upjscodingtest

UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.