자바스크립트를 배우고 있는 예비 개발자입니다.
오늘 배운 내용을 간단히 정리하고자 합니다.
수정사항이 있을시 적극적으로 알려주시면 감사히 배우겠습니다.
What I learned today :)
😎 Graph 📌
😎 tree (Binary tree)🌱 Graph
데이터 자료구조 중 하나인 그래프(Graph)는
Node(= '정점', 'vertex') && node들을 서로서로 연결하는 edge(= '간선')으로 구성되어 있다.
다음 포스트에서 작성할 tree도 그래프의 한 종류라는 걸 알고 있자!
Directed Graph VS Undirected Graph
그래프에는 방향성이 있는 것(Directed Graph)도 있고, 방향성이 없는(Undirected Graph) 그래프도 있다.
여기서 방향성이 있고 없는 차이는 그저 간선이 화살표로 이어져있는지 아닌지로 구분할 수 있는데
더 말이 길어지기 전에 아래 그림부터 보고 오도록 하자.
Directed Graph는 비대칭 관계로 단방향 혹은 일방향적인 그래프이다.
일상 생활에서 예를 찾아보면 보통 소셜네트워크의 인스타 || 트위터를 예를 든다.
이 소셜네트워크들은 Potter -> John을 팔로우 한다고 해도, John이 맞팔을 하지않는 이상 서로 소통이 되지 않는다.
반면, Undirected Graph는 방향성이 없고, node들끼리 쌍방성을 가지고 있다.
즉, 싸이월드나 페이스북처럼 혹은 카카오톡처럼 연락처를 주고받고 '친구'관계가 형성되어 언제든 서로 소통할 수 있는 구조라 보면 된다.
다시 말해
인스타, 트위터 --> Directed Graph
싸이월드, 페이스북 --> Undirected Graph를 사용하고 있다고 볼 수 있다.
사진출처:https://www.businessinsider.com.au/explainer-what-exactly-is-the-social-graph-2012-3
Graph 용어 정리
-
노드(node) : 엘리먼트와 유사한 개념이며, 위치라는 개념으로 이해하자. (= '정점', 'vertex')
-
간선(edge) : node와 node를 연결하는 선
-
인접 노드(adjacent Vertex) : 간선에 의해 연결된 노드
-
노드 차수(degree) : 하나의 노드에 인점한 정점의 수 in Undirected Graph
-
모든 노드 차수의 합 in Undirected Graph : 간선 수 *2
-
진입 차수(in-degree) : 외부에서 오는 간선의 수 ( = '내차수') in Directed Graph
-
진출 차수(out-degree) : 외부로 향하는 간선의 수 ( ='외차수') in Directed Graph
-
정점의 진입 차수 || 진출 차수의 합 in Directed Graph : 내차수 + 외차수
(진입, 진출 차수에 대한 그림 예제는 포스트 마지막에 있으니 참고 할 것.) -
단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우
-
사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
-
경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
Graph 구현 방식
Graph 구현 방식에는
1) Adjacency Matrix (인접 행렬)
2) Adgacency List (인접 리스트)
위의 두 종류로 구현할 수 있다.
**Adjacency: 인접한
Adjacency Matrix (인접 행렬)
이차원 배열에 표현하는 방법으로
- 직접적으로 서로 연결된 node들은 1
- 연결되지 않은 node들은 0으로 배열방을 채우는 방식이다.
javaScript에서는 이 행렬을 다음과 같이 구현될 수 있다.
[ [0, 1, 1, 1],
[1, 0, 0, 0],
[1, 0, 0, 1],
[1, 0, 1, 0] ]
Adjacency List (인접 리스트)
배열에 node들을 나열하고, 각 배열방에 있는 해당 node와 인접한 node들을
Linked list로 쭈우우욱 나열해서 저장하는 것이다. (순서 상관 x)
즉, 인접 리스트는 각 node들의 관계들을 링크드 리스트로 표현하는 구현 방법이다.
자, 그럼 여기에서 node들의 개수는 몇개가 될까?
여기서의 node들은 서로 관계를 나타내고
node와node를 연결하는 것을 간선(edge)을 x라고 할 때
총 node의 개수는 2x가 된다. (2배)
그 이유는 서로 관계있다고 하니,
예를 들어
3은 "나는 4랑 관계있다!",
4는 "나는 3이랑 관계있다!"라고 서로 적다보니 원래의 간선 개수보다 노드가 2배 많아지는 것이다.
위의 그래프에서 Vertex C의 in degree와 out degree의 합은 무엇일까요?
