섹션26 그래프

그래프 소개

그래프는 기본적으로 모든 sns에서 사용된다. (넷플릭스의 영화 추천, 광고주가 무언가를 기반으로 대상을 정할 때)

그래프란?

• 노드와 노드들의 연결을 모은 것
• 부모노드가 없고, 들어가는 지점도 없고, 그냥 다 노드다. 서로 다른 방식으로 연결될 뿐이다.

트리의 경우에, 노드가 한 개의 부모,즉 가장 위에 있는 노드를 가졌다. 거기서부터 내려오는 자식 노드가 여러개 있었다.트리는 그래프의 일종이다.

그래프의 이용

• sns
• 지도기능/ 구글지도나 방향안내
• 라우팅 (사이트를 요청하면 실제로 일어나는 일은 전체 네트워크에 퍼져있는 것 중에 일부 연결 부위를 주는 것뿐이다. )
• recommendations (사람들이 많이본거, 너가 아마 이걸 좋아할거야, 너가 아마도 알 수 있는 사람들, 사람들이 빈번하게 산 품목들) => 모든 데이터를 그래프 관계로 저장하기 때문에 가능한 것

그래프의 유형

• vertex : 하나의 노드
• edge : 간선
• 무방향 그래프(undirected graph)
• 방향 그래프 (directed graph)
• 비가중 그래프(unweighted graph) : 간선에 부여된 값이 없다.
• 가중 그래프(weighted graph) : 연결 그 자체에 대한 정보가 생긴 것

그래프의 정렬: 1. 인접 행렬

실제 그래프를 코딩하고, 저장하고, 코드로 표현하는 방법을 간단하게 보자

실제로 그래프를 저장할 때 중요한 정보는 노드, 즉 실제 정점들과 연결을 저장하는 방식이다. 예를 들어, 연결리스트에서는 next와 previous를 했다. 이진 탐색 트리에서는 left와 right가 클래스에 있었다. 그러나 이것들은 그래프에 쓸 수 없다. 왜? 노드의 개수나 노드 사이의 연결인 간선의 개수가 정해져 있지 않기 때문이다.

우리가 살펴볼 접근법은 두가지

• 인접 행렬
• 인접 리스트

인접 행렬 Adjacency matrix

행과 렬이 있는 것

출처 : 유데미 js알고리즘&자료구조 마스터클래스 강의

무방향그래프는 인접행렬이 대칭구조일 수 밖에 없다. 양방향이기 때문에
방향 그래프는 대칭 구조가 아니다.

그래프의 정렬: 2. 인접 리스트

• 무방향 그래프
• 양방향으로 데이터가 저장되어 있다.
  
  출처 : 유데미 js알고리즘&자료구조 마스터클래스 강의

근데 만약 각 노드가 숫자가 아니거나, 숫자여도 큰 차이가 나면 배열을 사용하지 말아야 할까?
=> 해시 테이블을 사용하자 키-값 데이터 구조

딕셔너리나, 자바스크립트에서는 객체나 맵이 있다.

출처 : 유데미 js알고리즘&자료구조 마스터클래스 강의

인접 행렬 vs 리스트의 빅오

출처 : 유데미 js알고리즘&자료구조 마스터클래스 강의

인접행렬은 2차원 배열이니, 새로운 정점을 추가하면 한 칸을 더하는 것이 아니라 두칸을 더한다. 따라서 O(V^2)
인접행렬에서 데이터가 퍼져있고, 연결 즉 간선이 많지 않으면 행렬을 사용하지 않는 것이 낫다.

인접 리스트

• 간선이 많지 않고 퍼져있는 그래프에 대해서 인접 행렬보다 더 적은 공간을 차지한다.
• 실제 연결만을 저장한다. 따라서 모든 간선을 순환하는 것은 더 빠르지만,
• 특정 간선이 존재하는 것을 확인하려면 느려질 수 있다. A랑 D가 연결되어 있는가? A에 D의 간선이 있는지 순회해야한다. 그 배열을 다 순회

인접 행렬

• 인접행렬은 더 많은 공간을 차지한다. vertex가 정점의 숫자일 때 v제곱의 공간 차지
• 인접행렬은 간선을 확인하고 싶으면 모든 간선에 대해 루프를 돌아서 찾아야 하는데 근데 간선이 없는 것도 0으로 저장되어 있기 때문에 느리다.
• 특정 간선이 존재하는 것을 확인하는 것은 빠르다. B와 C 사이에 간선이 있나요? 응 !

우리는 인접 리스트에 대해 더 알아볼 것이야!!!

왜?

• 차지하는 공간 때문에
• 실제 데이터들이 퍼져있는 경우가 더 많아 (위키피디아 문서, 연예인과의 관계)/ vertex의 개수는 아주 많지만 그게 서로 다 연결이 되어 있지 않은 경우가 더 많다. 행렬을 만들면 아주 큰 공간이 되지만, 리스트를 이용하면 실제로 있는 연결만 저장하면 된다

점(vertex) 추가에 대한 소개

그래프에 대한 기본 클래스는 아주 기본적인 것
우리는 무방향 그래프 클래스를 작성할 것이다. 왜냐? 무방향 그래프를 간선이 한 방향으로만 연결되는 방향 그래프로 바꾸는 것은 아주 간단하기 때문~
간선을 만들기 전에 먼저 정점을 만들어줘야 한다.

class Graph {
  constructor(){
  	this.adjacencyList ={}
  }

Adding a vertex

• write a method called addVertex, which accepts a name of a vertex
• it should add a key to the adjacency list with the name of the vertex and set its value to be an empty array

만약 g라는 그래프에 addVertex함수를 이용해 Tokyo 라는 vertex를 추가해주는거
g.addVertex("Tokyo") => { "Tokyo" : []}

점(vertex) 추가 솔루션

 class Graph{
 	constructor(){
    	this.adjaceneyList = {}
    }
   addVertex(vertex){
   	if(!this.adjaceneyList[vertex]) this.adjaceneyList[vertex] = [];
   }
 }

선(edge) 추가에 대한 소개

Tokyo, Dallas, Los Angeles, Hong Kong, 이런식으로 도시들 추가
항공편 관련 작업을 하고 있는 것! 항공잡지 뒤에 나와있는 모든 항공편과 연결된 비행편을 표현하는 것을 목표로 작업을 하고 있는 것

• 함수는 두개 vertex를 가진다.
• 이 함수는 adjacencyList에서 vertex1의 키를 찾아서 vertex2를 그 배열에 넣어줘야 한다. 그리고, 그 반대로도 해줘야 한다.
• 에러는 신경쓰지 말아보자.

{
"Tokyo" : [],
"Dallas" : [],
"Aspen" : []
}

=>

g.addEdge("Tokyo", "Dallas")

=>

{
"Tokyo" : [Dallas],
"Dallas" : [Tokyo],
"Aspen" : []
}

선(edge) 추가 솔루션

 class Graph{
 	constructor(){
    	this.adjaceneyList = {}
    }
   addVertex(vertex){
   	if(!this.adjaceneyList[vertex]) this.adjaceneyList[vertex] = [];
   }
   addEdge(v1, v2){
   		this.adjaceneyList[v1].push(v2);
     	this.adjaceneyList[v2].push(v1);
   }
 }

선(edge) 제거에 대한 소개

• 이 함수는 두개의 인자 vertex1, vertex2 를 받는다
• vertex1은 vertex2가 포함되어 있지 않는 배열을 reassign 한다.
• vertex2는 vertex1이 포함되어 있지 않은 배열을 reassign 한다.

예상)
{
"Tokyo": [Dallas],
"Dallas" : ["Tokyo", "Aspen"],
"Aspen" : ["Dallas"]
}
=> g.removeEdge("Tokyo","Dallas")

=> {
"Tokyo": [],
"Dallas" : ["Aspen"],
"Aspen" : ["Dallas"]
}

선(edge) 제거 솔루션

 class Graph{
 	constructor(){
    	this.adjacencyList = {}
    }
   addVertex(vertex){
   	if(!this.adjacencyList[vertex]) this.adjaceneyList[vertex] = [];
   }
   addEdge(v1, v2){
   		this.adjacencyList[v1].push(v2);
     	this.adjacencyList[v2].push(v1);
   }
   removeEdge(vertex1,vertex2){
   		this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2 )
     this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1 )
   }
 }

점(vertex) 제거에 대한 소개

• the finction should accept a vertex to remove
• the function should loop as long as there are any other vertices in the adjacency list for that vertex
• inside of the loop, call our removeEdge function with the vertex we are removing and any values in the adjacency list for that vertex
• delete the key in the adjacency list for that vertex

점(vertex) 제거 솔루션

 class Graph{
 	constructor(){
    	this.adjacencyList = {}
    }
   addVertex(vertex){
   	if(!this.adjacencyList[vertex]) this.adjaceneyList[vertex] = [];
   }
   addEdge(v1, v2){
   		this.adjacencyList[v1].push(v2);
     	this.adjacencyList[v2].push(v1);
   }
   removeEdge(vertex1,vertex2){
   		this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2 )
     this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1 )
   }
   
   removeVertex(vertex){
   		while(this.adjacencyList[vertex].length){ // 홍콩 배열길이 만큼
        	const adjacentVertex = this.adjacencyList[vertex].pop();//뒤에서부터 없애고 할당한다.  
          this.removeEdge(vertex, adjacentVertex); // 할당된 나라에 가서 홍콩 간선을 제거한다. 
        } // 관련 간선들 삭제하는거 
     delete this.adjacencyList[vertex] //그 정점 삭제하는거
   }
 }