자료구조 10 그래프 | JS
그래프 | Graph
- vertex(정점)와 edge(간선)로 구성.
- edge는 vertex와 vertex를 연결
인접 리스트
- 그래프 내에 적은 숫자의 간선만을 가지는 경우에 용이함
- 각각의 정점에 인접한 정점들을 리스트로 표시
- 배열이나 연결리스트 등을 이용해서 구현이 가능
- 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구, 공간 효율성이 우수
- 각 정점들의 연결 여부 확인을 위해 O(v)의 시간 복잡도
인접 행렬
- 2차원 배열로 구현
- 그래프에 간선이 많이 존재하는 밀집 그래프의 경우에 용이함
- 선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요
- 특정 노드의 인접 노드들을 탐색하기위해선 모든 노드들을 확인해야 함
- 정점간의 연결여부 확인 시 O(1)의 시간을 요구
그래프 종류
- 무방향 그래프: 간선에 방향이 없는 그래프
- 방향 그래프: 간선에 방향이 있는 그래프(= 다이 그래프)
- 가중 그래프: 간선에 가중치가 있는 그래프(= 네트워크)
그래프 vs 트리
무방향 그래프 구현
class UndirectedGraph {
constructor() {
this.edges = {};
}
// 정점 추가하기
addVertex(vertex) {
this.edges[vertex] = {};
}
// 간선 추가하기
addEdge(vertex1, vertex2, weight = 0) {
this.edges[vertex1][vertex2] = weight;
this.edges[vertex2][vertex1] = weight;
}
// 간선 삭제하기
removeEdge(vertex1, vertex2) {
if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
delete this.edges[vertex1][vertex2];
}
if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
delete this.edges[vertex2][vertex1];
}
}
// 정점 삭제하기 (반대편 정점에서도 간선을 삭제해야함)
removeVertex(vertex) {
for (let adjacentVertex in this.edges[vertex]) {
this.removeEdge(adjacentVertex, vertex);
}
delete this.edges[vertex];
}
}
방향 그래프
class DirectedGraph {
constructor() {
this.edges = {};
}
// 정점 추가
addVertex(vertex) {
this.edges[vertex] = {};
}
// 간선 추가
addEdge(from, to, weight = 0) {
// 시작 정점, 도착 정점, 가중치
this.edges[from][to] = weight;
}
// 간선 삭제
removeEdge(vertex1, vertex2) {
if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
delete this.edges[vertex1][vertex2];
}
}
// 정점 삭제하기 (반대편 정점에서도 간선을 삭제해야함)
removeVertex(vertex) {
for (let adjacentVertex in this.edges[vertex]) {
this.removeEdge(adjacentVertex, vertex);
}
delete this.edges[vertex];
}
📚 참고
Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
[자료구조] 그래프 (자바스크립트/javascript)
Photo by Alain Pham on Unsplash
Author And Source
이 문제에 관하여(자료구조 10 그래프 | JS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@protect-me/자료구조-10-그래프-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)