IMMERSIVE - #5. Graph

geonhwiΒ·2019λ…„ 7μ›” 24일
1
post-thumbnail

자료 ꡬ쑰 쀑 Graph에 λŒ€ν•΄μ„œ μ•Œμ•„λ΄…λ‹ˆλ‹€. πŸ˜€

이전 μž₯인 Tree ꡬ쑰λ₯Ό κ³΅λΆ€ν•˜κ³  λ‚œ λ’€ 보면 μ’‹μŠ΅λ‹ˆλ‹€! μš©μ–΄κ°€ λΉ„μŠ·ν•΄μš”~


πŸ“Š Graph

1. κ°œλ…

κ·Έλž˜ν”„λŠ” λ…Έλ“œμ™€ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” 간선을 ν•˜λ‚˜λ‘œ λͺ¨μ•„놓은 자료 κ΅¬μ‘°μž…λ‹ˆλ‹€.

μ§€ν•˜μ²  노선도λ₯Ό μƒκ°ν•˜μ‹œλŠ”κ²Œ μ’‹μŠ΅λ‹ˆλ‹€ :)

μš©μ–΄λ₯Ό λͺ‡κ°€μ§€ μ •λ¦¬ν•΄λ΄…μ‹œλ‹€.

  1. Vertex(정점) : νŠΈλ¦¬μ—μ„œμ˜ λ…Έλ“œ(node)와 κ°™μŠ΅λ‹ˆλ‹€.
  2. Edge(κ°„μ„ ) : νŠΈλ¦¬μ—μ„œμ˜ 가지(branch)와 κ°™μŠ΅λ‹ˆλ‹€.
  3. degree(차수) : 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ μΈμ ‘ν•œ μ •μ μ˜ 두
  4. in-degree(μ§„μž… 차수) : λ‹€λ₯Έ μ •μ μ—μ„œ μ˜€λŠ” κ°„μ„ μ˜ 개수
  5. out-degree(차좜 차수) : λ‹€λ₯Έ μ •μ μœΌλ‘œ κ°€λŠ” κ°„μ„ μ˜ 개수

νŠΈλ¦¬λŠ” ν•˜λ‚˜μ˜ λΆ€λͺ¨ λ…Έλ“œμ—μ„œ μ•„λž˜λ‘œ λ‚΄λ €μ˜€λŠ” κ·Έλž˜ν”„λΌκ³  ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

2. νŠΉμ§•

  • λ„€νŠΈμ›Œν¬ λͺ¨λΈ
  • λ²„ν…μŠ€ μ‚¬μ΄μ—μ„œ μ–‘μͺ½ λ°©ν–₯으둜 λ°©ν–₯을 κ°€μ§ˆ 수 μžˆμŠ΅λ‹ˆλ‹€.
  • Root / Leaf / λΆ€λͺ¨ / μžμ‹ 등이 μ—†μŠ΅λ‹ˆλ‹€.

3. μ’…λ₯˜

  • 무방ν–₯/λ°©ν–₯ κ·Έλž˜ν”„ (Undirected/Directed Graph)
  • 무방ν–₯ κ·Έλž˜ν”„λŠ” μ•„λž˜μ˜ 그림처럼 κ·Έλž˜ν”„μ— ν™”μ‚΄ν‘œκ°€ μ—†μŠ΅λ‹ˆλ‹€!
  • κ·Έλž˜μ„œ 각 간선은 μ–‘λ°©ν–₯으둜 갈 수 μžˆμŠ΅λ‹ˆλ‹€.
  • λ°˜λŒ€λ‘œ λ°©ν–₯ κ·Έλž˜ν”„λŠ” μ•„λž˜ κ·Έλ¦Όμ—μ„œ ν•œμͺ½μœΌλ‘œ ν™”μ‚΄ν‘œκ°€ μΆ”κ°€λ©λ‹ˆλ‹€.
  • 사싀 트리 κ΅¬μ‘°λŠ” λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ ν™”μ‚΄ν‘œλ§Œ μƒλž΅ν•œ κ²ƒμž…λ‹ˆλ‹€!

  • κ°€μ€‘μΉ˜ κ·Έλž˜ν”„ (Weighted Graph)
  • 간선에 λΉ„μš© λ˜λŠ” κ°€μ€‘μΉ˜κ°€ ν¬ν•¨λœ κ·Έλž˜ν”„μž…λ‹ˆλ‹€.
  • λ„μ‹œκ°„μ˜ μ—°κ²°, 톡신망 μ‚¬μš©λ£Œ 등에 μ‚¬μš©λ©λ‹ˆλ‹€.
  • 일본 μ§€ν•˜μ² μ€ κ΅¬κ°„λ§ˆλ‹€ λΉ„μš©μ΄ μ¦κ°€ν•˜λŠ”λ°, 이와 λΉ„μŠ·ν•©λ‹ˆλ‹€!
  • μ—°κ²°/λΉ„μ—°κ²° κ·Έλž˜ν”„(Connected/UnConnected Graph)
  • μ—°κ²° : 무방ν–₯ κ·Έλž˜ν”„μ˜ λͺ¨λ“  정점간에 항상 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜λŠ” 경우
  • λΉ„μ—°κ²° : 무방ν–₯ κ·Έλž˜ν”„μ˜ νŠΉμ • 정점간 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ” 경우
  • μˆœν™˜/λΉ„μˆœν™˜ κ·Έλž˜ν”„ (Cyclic/Acyclic Graph)
  • μˆœν™˜ : λ°˜λ³΅λ˜λŠ” 정점이 μ—†λŠ” κ²½λ‘œμ—μ„œ μ‹œμž‘,μ’…λ£Œ 정점이 λ™μΌν•œ 경우
  • λΉ„μˆœν™˜ : μˆœν™˜μ΄ μ—†λŠ” 경우
  • μ™„μ „ κ·Έλž˜ν”„(Complete Graph)
    • λͺ¨λ“  정점이 μ—°κ²°λ˜μ–΄ μžˆλŠ” 경우

4. pseudo Code

κ°„λ‹¨ν•˜κ²Œ λ™μž‘μ›λ¦¬λ§Œ μƒκ°ν•΄λ΄…λ‹ˆλ‹€.

// pseudo Code
κ·Έλž˜ν”„ {
  store {}, edge {}
  
  method: addNode(κ°’) {
   store에 값을 { 'κ°’': κ°’ }으둜 μΆ”κ°€ν•œλ‹€.
  }
  method: contains(κ°’) {
    store['κ°’'] 이 μžˆλŠ”μ§€ μ‘°μ‚¬ν•œλ‹€.
  }
  method: removeNode(κ°’) {
   	store['κ°’'] 을 μ°Ύμ•„ μ œκ±°ν•œλ‹€.
    μ œκ±°ν•  λ•Œ μ—°κ²°λœ 엣지도 μ œκ±°ν•œλ‹€.
  }
  method: hasEdge(from, to) {
   	edge[from] κ°€ to 인지 μ°ΎλŠ”λ‹€. 
  }
  method: addEdge(from, to) {
   	edge[from]에 to, edge[to]에 from을 μΆ”κ°€ν•œλ‹€. 
  }
  method: removeEdge(from, to) {
   	delte edge[from], edge[to] 
  }
  method: forEachNode(콜백) {
    storeλ₯Ό λŒλ©΄μ„œ 콜백(κ°’) 을 μ€€λ‹€.
  }
}

5. Make Graph

νŠΉλ³„ν•œ 건 μ—†μŠ΅λ‹ˆλ‹€.

store와 edge객체에 {key: value}ν˜•νƒœλ‘œ {'κ°’':κ°’}을 λ„£μ–΄ κ΅¬ν˜„ν•©λ‹ˆλ‹€.

μ€‘μš”ν•œ 점은 λ…Έλ“œλ₯Ό μ§€μšΈ λ•Œ, 그와 μ—°κ²°λœ 엣지도 μ§€μ›Œμ•Ό ν•˜λŠ” κ²ƒμž…λ‹ˆλ‹€.

κ·Έλ ‡λ‹€λ©΄ removeNodeμ—μ„œ μ—°κ²°λœ 엣지λ₯Ό μ°Ύμ•„μ„œ μ œκ±°ν•˜λ©΄ κ°„λ‹¨ν•©λ‹ˆλ‹€ :)

// Graph
const _ = require('underscore')

const Graph = function() {
  this.store = {};
  this.edge = {};
};

Graph.prototype.addNode = function(node) {
  this.store[node] = node;
};

Graph.prototype.contains = function(node) {
  return this.store.hasOwnProperty(node);
};

// 1. 4 --- 5 : 
// 2. 4 ---   : removeNode(5) -> 5λž‘ 뭐가 μ—°κ²°λ˜μ–΄μžˆμ£ ? λ₯Ό λ¬Όμ–΄λ΄μ„œ 4λ₯Ό κ°€μ Έμ˜¨λ‹€λ©΄,
// 3. 4       : removeEdge(κ°€μ Έμ˜¨ 4, 5),
Graph.prototype.removeNode = function(node) {
  let tmpNode = this.edge[node]
  delete this.store[node]
  this.removeEdge(tmpNode, node)
};

Graph.prototype.hasEdge = function(fromNode, toNode) {
  return this.edge[fromNode] === toNode;
};

Graph.prototype.addEdge = function(fromNode, toNode) {
  this.edge[fromNode] = toNode;
  this.edge[toNode] = fromNode;
};

Graph.prototype.removeEdge = function(fromNode, toNode) {
  delete this.edge[fromNode];
  delete this.edge[toNode];
};

Graph.prototype.forEachNode = function(cb) {
  _.each(this.store, node => cb(node))
};
profile
ggit

0개의 λŒ“κΈ€