정점 ?
노드(node)라고도 하며 정점에는 데이터가 저장된다.
간선 ?
링크라고도 하며 노드간의 관계를 나타낸다.
그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)과 인접리스트 방식(Adjacency List)이 있다. 두 개의 구현 방식은 각각의 상반된 장단점을 가지고 있으며 대부분 인접리스트 형식을 많이 사용한다.
그래프의 노드를 2차원 배열로 만든 것이다.
각 정점의 연결정보를 0과 1로 표현한다.
const graph = Array.from(new Array(7), () => new Array(7).fill(0));
graph[1][2] = 1;
graph[1][3] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[2][4] = 1;
graph[3][1] = 1;
graph[3][2] = 1;
graph[3][4] = 1;
graph[3][5] = 1;
graph[4][2] = 1;
graph[4][3] = 1;
graph[4][5] = 1;
graph[4][6] = 1;
graph[5][3] = 1;
graph[5][4] = 1;
graph[6][4] = 1;
for(let i = 1; i < graph.length; i++) {
console.log(graph[i].slice(1).join(' ')); // 0번 정점이 없으므로 제거
}
// 결과
// 0 1 1 0 0 0
// 1 0 1 1 0 0
// 1 1 0 1 1 0
// 0 1 1 0 1 1
// 0 0 1 1 0 0
// 0 0 0 1 0 0
2차원 배열 안에 모든 정점들의 간선 정보가 포함되므로 배열의 위치를 확인하면 두 정점의 연결 정보를 탐색할 때 O(1)의 상수 시간복잡도로 가능하다.
구현이 비교적 간단하다.
모든 정점에 대해 간선 정보를 대입해야 하므로 인접행렬 생성에 O(N^2)의 시간복잡도 소요.
무조건 2차원 배열이 필요하므로 메모리의 낭비가 심하다.
그래프의 노드들을 연결 리스트로 표현한다.
주로 정점의 연결 리스트 배열을 만들어 관계를 설정하여 구현한다.
const graph = Array.from(new Array(7), () => []);
graph[1].push(2);
graph[1].push(3);
graph[2].push(1);
graph[2].push(3);
graph[2].push(4);
graph[3].push(1);
graph[3].push(2);
graph[3].push(4);
graph[3].push(5);
graph[4].push(2);
graph[4].push(3);
graph[4].push(5);
graph[4].push(6);
graph[5].push(3);
graph[5].push(4);
graph[6].push(4);
console.log(graph); // 0번 정점은 없으므로 1 인덱스(정점) 배열부터 ~ 6까지의 연결정보
정점들의 연결 정보를 탐색할 때 O(n)의 시간복잡도. (n: 간선의 갯수)
필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적습니다.
특정 두 점이 연결되었는지 탐색하려면 인접행렬에 비해 시간이 오래 걸립니다. (배열보다 연결리스트가 탐색속도 느림)
구현이 비교적 어렵습니다.