ZTM Data Structures & Algorithms - Graph

https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

Graph Data Structure And Algorithms - GeeksforGeeks

- 그래프는 정점(vertex)과 엣지(edge) 로 이루어진 자료구조이다. 
- 하나의 정점에서 출발하여 다시 해당 정점으로 돌아올수있다면 Cyclic 이라하며 아닐경우 Acyclic 이라한다. 
- 하나의 정점에서 갈수있는 방향이 정해져있는경우(directed)와 아닌경우(undirected) 로 구분 할 수 도 있다. 

- 그래프를 표현할때는 인접행렬, 인접리스트, 엣지리스트 로 그래프를 표현 할 수 있다. 

undirected 인접리스트로 그래프를 구현하면 아래와 같이 될수 있다. 

class Graph { 
  constructor() { 
    this.numberOfNodes = 0;
    this.adjacentList = {
    }; 
  } 
  addVertex(node)  { 
    if (this.adjacentList[node]) {
      return;
    }
    this.adjacentList[node] = [];
    this.numberOfNodes++;
  } 
  addEdge(node1, node2) { 
    //undirected 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); 
    } 
} 
} 

const 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(); 
//Answer:
// 0-->1 2 
// 1-->3 2 0 
// 2-->4 1 0 
// 3-->1 4 
// 4-->3 2 5 
// 5-->4 6 
// 6-->5