Graph 구현
Graph란 무엇인가
자료구조의 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 보이고있다.
- 정점 (vertex): 하나의 점
- 하나의 선(edge) : 간선
Graph의 실사용예제
- 포털사이트의 검색엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등에서 사용하는 자료구조
- 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이루어져있다.
네비게이션 예시
정점: 서울, 대전, 부산
간선: 서울ㅡ대전, 대전ㅡ부산, 부산ㅡ서울
정점: 서울, 대전, 부산
간선: 서울ㅡ대전, 대전ㅡ부산, 부산ㅡ서울
하지만 정점에 시카고를 추가한가도 하면? 자동차로는 한국에서 시카고로 이동할 수 없기 때문에, 어떠한 간선을 추가할 수 없다. Graph에서는 이런 경우를 관계가 없다 라고 표현한다.
비가중치 그래프
위의 간선을 살펴보면, 서울, 대전, 부산이 서로 관계가 있다는 것은 알 수 있지만, 각 도시가 얼마나 떨어져있는지는 알 수 없다. 이렇게 추가적으로 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지) 가 적혀있지 않은 그래프를 비가중치 그래프라고 한다. 간단한 JS Object를 이용하여 비교할 수 있다.
let isConnected = {
seoul: {
busan: true;
daejeon: true;
},
...
}
console.log(isConnected.seoul.daejeon) // true;
[비가중치 그래프로 나타낸 서울, 대전, 부산 그래프]
위 정보만으로는 서울에서 부산까지 갈 수 있다는 사실외에 파악할 수 있는 정보가 없다. 네비게이션이라면, 적어도 각 도시간의 거리가 얼마나 되는지 표시해야한다. 그래서 가중치 그래프로 바꾸고, 각 도시간의 거리를 표시한다면 어떨까? 가중치 그래프는 더 자세한 정보를 담을 수 있기 때문이다.
- 정점: 서울, 대전, 부산
- 간선: 서울ㅡ140kmㅡ대전, 대전ㅡ200kmㅡ부산, 부산ㅡ325kmㅡ서울
이렇게 네비게이션은 간선에 거리를 표시한 가중치 그래프가 확장되어서, 수백만개의 정점(주소)과 간선이 추가되어서 네이게이션에서 쓰는 자료구조와 비슷해진다.
알아둬야할 Graph 용어들
- 무(방)향그래프 (undirected graph)
=> 위의 네이게이션 예제는 무(방)향 그래프이다. 서울에서 부산을 갈 수 있듯이, 반대로 부산에서 서울까지도 가능하다. 하지만 단방향 그래프로 구현된다면, 부산에서 서울로 가는 것은 불가능하다. 만약 두 지점이 일방통행 도로로 이어져있다면, 단방향인 간선으로 표현할 수 있다.
- 진입차수 (in-degree) / 진출차수(out-degree)
=> 한 정점에 진입(들어오는 간선) 하고 진출 (나가는 간선)하는 간선이 몇개인지를 나타낸다.
- 인접(adjacency) :
=> 두 정점간에 간선이 이어져 있다면, 이 두 정점은 인접한 정점이다.
- 자기 루프 ( self loop)
=> 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 가지지 않는다는 것이 특징이다.
- 사이클(cycle)
=> 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다 라고 표현한다. 네비게이션 Graph는 서울 > 대전 > 부산 > 서울
로 이동이 가능해서 , 사이클이 존재하는 Graph이다.
question
- 위 네비게이션 예제에서 서울은 몇개의 진입차수와 , 진출차수를 가지고 있나?
=> 진입차수는 대전과 부산 으로 갈 수 있어서 2개이고 진출 차수는 서울 하나여서 1개인 것 같다.
- 네비게이션 대신 SNS에서 자료구조를 그래프로 이용한다면, 정점과 간선은 무엇일까?
=> 개개인의 프로필이 정점이고 간선은 서로 친구일때 연결되는 것 같다.
- SNS에서 어떤 관계일 경우, 단방향 그래프가 생성될까?
=> 맞팔로우가 안되어있는 상황?
- 자기 루프와 사이클은 어떻게 다를까?
=> 자기 루프는 좀 폐쇄적일 것 같고 사이클은 소통이 가능한 구조인 것 같다.
Graph의 표현방식
인접행렬
위에서 인접이라는 용어을 설명했듯이, 두 정점을 바로 이어주는 간선이 있다면, 두 정점은 인접하다고 말한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타난다. 만약 A라는 정점과 B라는 정점이 이어져있다면, 1(true), 아니면 0 (false)로 표시한 일종의 표이다.
만약 가중치 그래프라면 1대신 관계에서 의미있는 값을 저장한다. 위의 네비게이션 예제라면, 거리를 입력하면 좋겠다.
네비게이션 Graph를 인접행렬로 표현하면?
=> 위의 네이게이션 예제는 무(방)향 그래프이다. 서울에서 부산을 갈 수 있듯이, 반대로 부산에서 서울까지도 가능하다. 하지만 단방향 그래프로 구현된다면, 부산에서 서울로 가는 것은 불가능하다. 만약 두 지점이 일방통행 도로로 이어져있다면, 단방향인 간선으로 표현할 수 있다.
=> 한 정점에 진입(들어오는 간선) 하고 진출 (나가는 간선)하는 간선이 몇개인지를 나타낸다.
=> 두 정점간에 간선이 이어져 있다면, 이 두 정점은 인접한 정점이다.
=> 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 가지지 않는다는 것이 특징이다.
=> 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다 라고 표현한다. 네비게이션 Graph는
서울 > 대전 > 부산 > 서울
로 이동이 가능해서 , 사이클이 존재하는 Graph이다.=> 진입차수는 대전과 부산 으로 갈 수 있어서 2개이고 진출 차수는 서울 하나여서 1개인 것 같다.
=> 개개인의 프로필이 정점이고 간선은 서로 친구일때 연결되는 것 같다.
=> 맞팔로우가 안되어있는 상황?
=> 자기 루프는 좀 폐쇄적일 것 같고 사이클은 소통이 가능한 구조인 것 같다.
인접행렬
위에서 인접이라는 용어을 설명했듯이, 두 정점을 바로 이어주는 간선이 있다면, 두 정점은 인접하다고 말한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타난다. 만약 A라는 정점과 B라는 정점이 이어져있다면, 1(true), 아니면 0 (false)로 표시한 일종의 표이다.
만약 가중치 그래프라면 1대신 관계에서 의미있는 값을 저장한다. 위의 네비게이션 예제라면, 거리를 입력하면 좋겠다.
네비게이션 Graph를 인접행렬로 표현하면?
ㅡㅡㅡㅡㅡto A B C
from A ㅡㅡ0 0 1 => 0번째 인덱스
ㅡㅡBㅡㅡ 1 0 1 => 1번째 인덱스
ㅡㅡCㅡㅡ1 0 0 => 2번째 인덱스
- A의 진출 차수 1개
- [0][2] === 1
- B의 진출 차수 2개
- [1][0] === 1
- [1][2] === 1
- C의 진출 차수 1개
- [2][0] === 1
인접 행렬은 언제 사용하나?
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지 없는지 파악한다.
- ex) A to B 로 진출하는 간선이 있는지 파악하기 위해서는 0번째 줄의 1번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있다.
- 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용한다.
인접 리스트
인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 리스트는 자신과 인접한 다른 정점을 담고 있다. 위 그래프를 인접 리스트로 표현하면
A->C->Null
B->A->C->Null
C->A->Null
question
- B는 A와 C로 이어지는 두개의 간선이 있는데, 순서가 중요한가?
=> 보통은 종요하지 않다.Graph, Tree, Stack, Queue 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가 및 삭제할 수 있다. Graph를 인접 리스트로 구현할 때, 정점별로 살펴봐야할 우선순위를 고려해 구현할 수 있다. 이때, 리스트에 담겨진 정점들을 우선 순위 별로 정렬할 수 있다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
- 우선 순위를 다뤄야한다면, 더 적합한 구조 (Queue, heap) 를 사용하는 것이 합리적이다. 따라서 예외는 있지만, 보통은 중요하지 않다는 것이다.
인접 리스트는 언제 사용하나?
- 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에, 상대적으로 메모리를 많이 차지한다.
Author And Source
이 문제에 관하여(Graph 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hunsm4n/Graph-구현저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)