자료구조 Graph

그래프가 뭔가요?

그래프는 단순히 노드와 그 노드를 연결하는 간선(edge)를 하나로 모아 놓은 자료구조다.
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
Ex : 지도, 지하철 노선도의 최단 경로등을 나타내기 좋은 자료 구조다!

그래프(Graph)의 특징

• 그래프는 네트워크 모델 이다.
• 2개 이상의 경로가 가능하다.
  -즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop 뿐 아니라 loop/circuit 모두 가능하다.
• 루트 노드라는 개념이 없다.
• 부모-자식 관계라는 개념이 없다.
• 순회는 DFS나 BFS로 이루어진다.
• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
• 그래프는 크게 방향 그래프와 무방향 그래프로 나뉜다.
• 간선의 유무는 그래프에 따라 다르다.

그래프(Graph)와 관련된 용어

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

그래프의 종류

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

무방향 그래프(Undirected Graph)

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

방향 그래프(Directed Graph)

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

가중치 그래프

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

Graph 구현하기

슈도코드

1. Add node
1.1. 객체[노드]에 값을 추가한다. 값이 없으면 빈배열 추가

2. Contains
2.1. 만약 노드가 있으면 true 반환
2.2. 없으면 false 반환

3. removeNode
3.1. 만약 노드가 없으면 undefined 반환
3.2. 반복문을 돌려 노드의 모든 양방향 간선을 제거한다.
3.3. 노드삭제

4. hasEdge
4.1. 노드가 존재하는 노드라면
4.2. 반복문을돌려 출발간선에 도착간선이 있는지 확인
4.3. 있으면 true 반환

5. addEdge
5.1. 출발간선에 도착간선추가
5.2. 도착간선에 출발간선 추가

6.removeEdge
6.1. 출발간선의 도착간선 제거
6.2. 도착간선의 출발간선 제거

Js 코드

class Graph {
  constructor() {
 
    this.nodes = {};
  }

  addNode(node) {
    this.nodes[node] = this.nodes[node] || [];
  }

  contains(node) {
    if(this.nodes[node]){
      return true;
    }
    else{
      return false;
    } 
  
  } 

  removeNode(node) {
    if(this.nodes[node] === undefined){
      return undefined
    }
        for (let i of this.nodes[node]) {
          this.removeEdge(i, node)
        }
    
   delete this.nodes[node]
  }

  hasEdge(fromNode, toNode) {
    if(this.nodes[fromNode]){
    for(let edge of this.nodes[fromNode]){
      if(edge === toNode){
        return true
      }
    }
  }
    return false
  }

  addEdge(fromNode, toNode) {
    this.nodes[fromNode].push(toNode)
    this.nodes[toNode].push(fromNode)
  }

  removeEdge(fromNode, toNode) {
        this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode),1)
        this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode),1);
      }
  }