Graph 그래프

myung hun kang·2022년 11월 6일

실제 우리의 삶에서 다루는 data를 표현할 때 가장 흔하게 잘 사용되는 자료구조이다.
서로 연관된 값들끼리 서로 얽혀있는 묶음이 Graph이다.

그래프

각각 1개의 Item을 노드 또는 Vertex라고 한다.
각 노드는 edge라는 작대기로 연결되어있다.

이런 Graph구조는 인터넷 연결 망이나 사람들의 관계, 도로 등 다양한 곳에서 볼 수 있다. 대체로 모든 경우가 Graph에 속한다고 보면 된다.
--> linked list, binary tree, heap, trie 등 다 graph이다. (물론 아닌것도 있음)

Directed vs Undirected

Directed

방향이 정해진 Graph이다.

Twitter 처럼 상대가 나를 follow 하면 자동으로 나도 follow 하게 되는 것이 Directed 그래프이기 때문이다.

Undirected

양방향으로 data 전송이 가능한 Graph이다.

Facebook 처럼 상대가 나를 follow 했다고 내가 상대를 follow 하는 것이 아니라 선택할 수 있는 것 -> Undirected 여서임.

Weighted 그래프

Weighted

노드들의 연결고리인 edge에 노드간의 관계를 담은 그래프

google map에 빠른 길 찾는 기능이나 내가 찾는 것에 가장 가까운 정보 아니면 내가 관심있어할 정보를 찾는 것에 쓰이는 그래프

Cyclic vs Acyclic 그래프

Cyclic vs Acyclic

data들간에 순환이 되는지 아닌지에 따라 나눈 그래프이다.

이처럼 다양한 특징을 하나씩만 가지는 것은 아니다.
directed unweighted cyclic graph / directed acyclic graph / undirected unweighted cyclic graph
등 다양하게 존재 가능하다.

Graph data 표기법

Graph data

graph data를 표현하는 방법은 세가지 정도로 나뉜다.

Edge List
그래프의 모든 edge 를 배열로 담은 리스트
Adjacent List(인접 리스트)
Linked List 자료구조를 사용해서 그래프의 연결상태를 나타낸다. key 와 value 쌍으로 표시된다.
Adjacent Matrix(인접 행렬 방식)
2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.

graph ex

위 예시 그래프를 각 표기법으로 표기하면 다음과 같다.

Edge List

[ [ 0 , 2 ] , [ 2 , 3 ] , [ 2 , 1 ] , [1 , 3] ]

Adjacent List

각 key와 연결된 노드를 표시한 것

[ [ 2 ] , [ 2 , 3 ] , [ 0 , 1 , 3] , [ 1 , 2 ] ]

Adjacent Matrix

각 key 와 연결된 노드를 배열에 1로 표시한 것

{ [ 0 , 0 , 1 , 0 ] ,
[ 0 , 0 , 1 , 1 ] ,
[ 1 , 1 , 0 , 1 ] ,
[ 0 , 1 , 1 , 0 ] }

장 단점

　　장점　　　　　　　　　　　　　　단점
Relation ships　　　　　　　　　Sacling is hard

data들의 관계를 나타내는데는 좋지만 이 자료구조를 구축하고 확장시키기는 어렵다.

그래프 만들기 (Adjacent List 로)

class Graph { 
  constructor() { 
    this.numberOfNodes = 0; 
    this.adjacentList = {}; 
  } 
  addVertex(node)  { 
    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); 
    } 
} 
}