Graphs

Graph는 현실을 구현하는데 가장 유용한 Data Structure이다.(그렇기에 Scailing이 가장 어렵다.)

World Wide Web, SNS 등의 모두 Graph로 되어 있고 실제로도 사용하고 있다.

Neo4j라는 회사가 Graph 형태 Database를 제공한다고 한다.

Type of graphs

Directed vs Undirected

-Directed : 특정 방향으로만 연결 된다. ex)Twitter 트위터는 팔로우하면 자동으로 팔로우 한사람과 서로 팔로우 되지 않는다. -Undirected : 무조건 양바향으로 연결 된다. ex)Facebook 친구를 하면 서로 친구가 된다.

Weighted vs Unweighted

-Weighted : node마다 숫자 value가 있고 Edge마다 value가 있다. ex)Google map 특정 장소를 찾아서(node의 value를 검색) 가장 빠른 경로를 찾는다(Edge들의 value분석). -Unweighted : node마다 value가 있지만 Edge에 value는 없다.

Cyclic vs Acyclic

-Cyclic : 각 node가 서로 연결되어 있는 상태 Cyclic은 특히 Weighted Graph에서 자주 보이는 형태이다. -Acyclic : 각 node가 서로 연결되어 있지 않는 상태

Graph Data

아래와 같은 graph가 있다고 할 때 이것을 어떻게 data화 시켜 프로그램에서 다룰 것인가??

Adjacent Matrix

const graph = [[0,2], [2,3], [2,1], [1,3]];

0과 2가 연결되어 있다, 2와 3이 연결되어 있다, 2와 1이 연결되어 있다, 1과 3이 연결되어 있다

Adjacent List

const graph = [[2], [2,3], [0,1,3], [1,2]];

0은 2와 근접해있다, 1은 2,3과 근접해있다, 2는 0,1,3과 인접해있다, 3은 1,2와 인접해 있다

HashTable을 이용해 key값을 node의 value로 한다면 한층 다루기 편해질 것.

Edge List

const graph = [
	0: [0,0,1,0], 
	1: [0,0,1,1], 
	2: [1,0,1,1], 
	3: [0,1,1,0]
];

0은 2번과 접해있다. 1은 2와 3과 접해있다.

Excercise

class Graph { 
  constructor() { 
    this.numberOfNodes = 0; 
    this.adjacentList = {}; 
  } 
  addVertex(node)  { 
    this.adjacentList[node] = []; 
    this.numberOfNodes++;
  } 
  addEdge(node1, node2) { 
    //uniderected Graph 
    this.adjacentList[node1].push(node2); 
    this.adjacentList[node2].push(node1); 
  } 
  showConnections() { 
    const allNodes = Object.keys(this.adjacentList); 
    for (let node of allNodes) { 
      let nodeConnections = this.adjacentList[node]; 
      let connections = ""; 
      let vertex;
      for (vertex of nodeConnections) {
        connections += vertex + " ";
      } 
      console.log(node + "-->" + connections); 
    } 
  } 
} 

var myGraph = new Graph();
myGraph.addVertex('0');
myGraph.addVertex('1');
myGraph.addVertex('2');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addEdge('3', '1'); 
myGraph.addEdge('3', '4'); 
myGraph.addEdge('4', '2'); 
myGraph.addEdge('4', '5'); 
myGraph.addEdge('1', '2'); 
myGraph.addEdge('1', '0'); 
myGraph.addEdge('0', '2'); 
myGraph.addEdge('6', '5');

myGraph.showConnections();