Data Structure 공부 중 이해한 부분을 정리합니다. 각 자료구조의 구현은 JavaScript를 이용하였습니다.
노드(Node, 또는 정점-vertax-), 노드와 노드를 연결하는 간선(edge)로 구성됩니다.
그래프의 종류로는 무방향 그래프
와 방향 그래프
가 있습니다.
무방향 그래프
무방향 그래프는 방향이 없는 그래프로 간선을 통해 양 뱡향 모두 갈 수 있습니다.
방향 그래프
방향 그래프는 방향이 존재하는 그래프로 지정된 방향으로만 이동 할 수 있습니다.
(방향 그래프에서 진입 차수(in-dgree)는 외부에서 오는 간선의 수이며, 진출 차수(out-dgree)는 외부로 향하는 간선의 수 입니다.)
addNode(node) - 그래프에 노드를 추가합니다.
addEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 추가합니다.
removeNode(node) - 그래프에서 노드를 삭제합니다.
removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.
hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.
contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.
addNode(node) - 매개변수인 node의 인자로 들어오는 값을 key로 하고 value를 간선으로 이어진 노드를 추가할 빈 배열을 전체 그래프에 추가합니다.
addEdge(fromNode, toNode) - fromNode와 toNode의 value값인 배열에 각 toNode와 fromNode를 추가합니다.
removeNode(node) - graph의 key
removeEdge(fromNode, toNode) - graph의 fromNode와 toNode의 키의 value에서 각각toNode,fromNode값이 있는 인덱스를 찾아 splice를 이용해 제거합니다.
hasEdge(fromNode, toNode) - fromNode와 toNode의 value값에 각각 서로의 노드가 있으면 true를 return하고 아니면 false를 return 합니다.
contains(node) - graph의 key에 node가 있으면 true를 return하고 아니면 false를 return 합니다.
구현은 무방향 그래프, 인접 리스트 방식으로 구현하였습니다.
class Graph {
constructor() {
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
contains(node) {
return this.nodes.hasOwnProperty(node);
}
removeNode(node) {
for(let i of this.nodes[node]){
let index = this.nodes[i].indexOf(node);
this.nodes[i].splice(index,1);
}
delete this.nodes[node];
}
hasEdge(fromNode, toNode) {
if(this.nodes[fromNode].includes(toNode)){
if(this.nodes[toNode].includes(fromNode)){
return true;
}
}
return false;
}
addEdge(fromNode, toNode) {
if(!this.contains(fromNode) || !this.contains(toNode)){
return ;
}
this.nodes[fromNode].push(toNode);
this.nodes[toNode].push(fromNode);
}
removeEdge(fromNode, toNode) {
if(!this.contains(fromNode) || !this.contains(toNode)){
return ;
}
let toNodeindex = this.nodes[fromNode].indexOf(toNode);
let fromNodeindex = this.nodes[toNode].indexOf(fromNode);
this.nodes[fromNode].splice(toNodeindex,1);
this.nodes[toNode].splice(fromNodeindex,1);
}
}