-
Data Structure - Graph(그래프)Programming/Data Structure(자료 구조) 2019. 4. 7. 18:17
- Graph(그래프) -
- Graph(그래프)의 정의
- 노드(node)와 그 노드의 연결선인 엣지(edge)를 모아 놓은 자료 구조
- 연결되어 있는 객체간의 관계를 표현하기 위한 자료 구조
- 계층 관계인 트리와는 다르게 네트워크 관계이다 - Graph(그래프)와 Tree(트리)의 차이
- Graph(그래프)의 특징
- 네트워크 모델이다
- 2개 이상의 경로가 가능하다
- 트리처럼 root라는 개념이 없다
- 부모 - 자식 관계가 없다 - Graph(그래프)의 탐색 방법
1. DFS(깊이 우선 탐색)
- 그래프의 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중 아직 방문하지 않은 정점 u를 선택한다.
- 만약 그러한 정점이 없다면 탐색은 종료한다
- 만약 아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다.
2. BFS(너비 우선 탐색)
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하 는 순회 방법
- Pseudo - Code(의사 코드)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101// Graph(그래프)를 구현하기 위한 의사 코드// 노드와 엣지를 추가하고 삭제하는 메소드와// 탐색하는 메소드를 가지고있다const Graph = function() {1. 생성자2. value라는 키를 갖고 그안에 edge라는 키를 갖는다 -> 객체 안에 객체인 형태};Graph.prototype.addNode = function(node) {1. 새로운 노드를 추가하는 메소드};Graph.prototype.contains = function(node) {1. 노드를 순회하여 해당 노드가 있는지 탐색하는 메소드2. if문을 사용하여 작성};Graph.prototype.removeNode = function(node) {1. 해당 노드를 삭제하는 메소드2. 해당 노드가 삭제되면 연결된 edge도 삭제하도록 구현};Graph.prototype.hasEdge = function(fromNode, toNode) {1. edge가 있는지 탐색하는 메소드2. 두 노드가 연결되어 있는지를 탐색};Graph.prototype.addEdge = function(fromNode, toNode) {1. edge를 추가하는 메소드2. from과 to 노드에 각각 엣지가 동일하게 추가되어야한다};Graph.prototype.removeEdge = function(fromNode, toNode) {1. edge를 삭제하는 메소드2. 연결된 노드간의 edge를 다 삭제해야한다};Graph.prototype.forEachNode = function(cb) {1. callback함수의 형태로 작성2. 노드를 순회하며 각 노드의 값을 함수에 넣는 메소드};<------------------------------------------------------------------------->//실제 코드 구현const Graph = function() {this.value = {};this.value.edge = {};};Graph.prototype.addNode = function(node) {this.value[node] = node;};Graph.prototype.contains = function(node) {if(this.value[node] === node){return true;} else{return false;}};Graph.prototype.removeNode = function(node) {this.value[node] = undefined;if(this.value.edge.hasOwnProperty(node)){this.removeEdge(node, node);}for(let key in this.value.edge){if(this.value.edge[key] === node){this.removeEdge(null, key);}}};Graph.prototype.hasEdge = function(fromNode, toNode) {if(this.value.edge[fromNode] === toNode){return true;} else if(this.value.edge[toNode] === fromNode){return true;} else{return false;}};Graph.prototype.addEdge = function(fromNode, toNode) {this.value.edge[fromNode] = toNode;this.value.edge[toNode] = fromNode;};Graph.prototype.removeEdge = function(fromNode, toNode) {this.value.edge[fromNode] = undefined;this.value.edge[toNode] = undefined;};Graph.prototype.forEachNode = function(cb) {for(var key in this.value){if(typeof this.value[key] === 'number'){cb(this.value[key]);}}};cs 'Programming > Data Structure(자료 구조)' 카테고리의 다른 글
Data Structure - Hash Table(해시 테이블) (0) 2019.04.07 Data Structure - Tree / Binary Search Tree (0) 2019.04.07 Data Structure - Stack / Queue / Linked List 정리 (0) 2019.04.04 - Graph(그래프)의 정의