Graph

그래프는 노드(Node, 또는 정점 -vertex- 이라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성됩니다. 그래프는 무방향(undirected)일 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미입니다. 한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미합니다.

즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등
참고 : https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

그래프(Graph) 용어

정점(vertex): 위치라는 개념. (node 라고도 부름)
간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph) 종류

무방향 그래프 VS 방향 그래프

무방향 그래프(Undirected Graph)

무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
(A, B)는 (B, A) 동일
Ex) 양방향 통행 도로

방향 그래프(Directed Graph)

간선에 방향성이 존재하는 그래프
A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
<A, B>는 <B, A>는 다름
Ex) 일방 통행

가중치 그래프

가중치 그래프(Weighted Graph)

간선에 비용이나 가중치가 할당된 그래프
‘네트워크(Network)’ 라고도 한다.
Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등

연결 그래프 VS 비연결 그래프

연결 그래프(Connected Graph)

무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프

비연결 그래프(Disconnected Graph)

무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

사이클 VS 비순환 그래프

사이클(Cycle)

단순 경로의 시작 정점과 종료 정점이 동일한 경우
단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우

비순환 그래프(Acyclic Graph)

사이클이 없는 그래프

완전 그래프

완전 그래프(Complete Graph)
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
무방향 완전 그래프
정점 수: n이면 간선의 수: n * (n-1) / 2

참고:https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

Graph code

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    let treeNode = new TreeNode(value);
    this.children.push(treeNode);
  }

  contains(value) {
    let result = false;
    let currentNode = this;
    if(this.value === value){
      result =  true;
      return;
    }
    function recursion(element, value){
      let result = false;
      if(element.value === value){
        result = true;
        return result;
      }
      for(let i = 0 ; i < element.children.length; i++){
        result = this.recursion(element.children[i],value);
        if(result === true){
          return result;
        }
      }
      return result;
    }
    result = recursion(currentNode, value);
    return result;
  }
}