Graph 그래프

katsukichi·2021년 3월 4일

CODESTATES TIL

CodeStates_IM

목록 보기

16/48

그래프?

Graph 그래프

그래프가 뭐지

딱 정의하면

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조.

점은 정점(vertex)이라고 표현하고, 선은 간선(edge) 이라고 표현한다.

어디에쓰이는가?

포털 사이트의 검색 엔진, SNS, 네비게이션 (길찾기) 등에서 사용하는 자료구조가 바로 그래프이다.

간선으로 이어지지않은것

간선으로 이어지지 않았다는것은 갈수가 없다는것

그렇다면 그래프에선 이를 관계가 없다 라고 표한한다.

연결에 강도가 존재할수있다.

가중치라는 요소가 존재할수있는데

가중치가 없다면 비가중치 그래프 라고한다.

a,b,c 서로 친구인 사이의 3명이 있다면


let isFriends = {
  a : {
    b:true,
    c:true
  },
  b : {
    a:true,
    c:true
  },
  c : {
    a:true,
    b:true
  }
}
console.log(isFriends.a.b) // true
console.log(isFriends.b.c) // true

이러한 스타일이 비가중치 그래프 라고할수있다.

가중치로 바꾸어보면

a - 절친 - b , b - 그냥친구 - c , c - 서먹서먹함 - a

이런느낌일것이다. 뭐 친구를 0~100 사이의 친한정도를 나타낼수있다면 수치적으로도 저장할수있다.

(예시가 내가만들었지만 개떡같다.)

그래프의 용어(특징)들

무향그래프(undirected graph): 앞서 예시를 들었던게 무향그래프이다. 쉽게말하면 방향성이 없다. 즉 왕복이 가능하다 이렇게 생각하면된다. 예시에 빗대어서 생각해보면 누구는 친하게생각하고 상대는 아닐수도있으니까.
진입차수(in-degree) / 진출차수(out-degree) : 하나의 정점에서 들어오거나 나가는 선이 몇개인지
인접(adjacency) :얻제이선씨~ / 두 정점간에 간선이 직접 이어져 있다면 이 두정점은 인접한 정점이다.
자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징
사이클(cycle) : 한정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다 고 표현한다.

그래프의 표현방식

인접행렬

인접함을 표시해주는 행렬이다. 2차원 배열의 모습을 가지고 있다.

언제 인접 행렬을 사용할까?

두 정점 사이의 관계가 있는지, 없는지 확인하기에 용이하다.
간선이 존재하는지 파악하기에 직관적이다.
가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.

인접 리스트

이미지에서 0에서는 1과 3으로 갈수있는데 왜 1이 먼저인가?

-> 별로중요하지않다.

그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수있는데, 그래프를 인접 리스트로 구현할 때 정점별로 살펴봐야 할 우선 순위를 구현하고 싶다면, 리스트에 담겨진 정점들을 우선 순위별로 정렬하여 담을 수 있다. 우선 순위가 없다면 연결된 정점들을 단순히 나열한 리스트이다.