[DataStructure] Graphs

데이터들은 다양한 Graph 형태로 연결되어 있다. Tree와 Linked List 또한 Graph의 종류 중 하나이다.

Graphs data structure

용어

• Vertex : node
• Edge : vertex 사이의 연결선

장단점

• 장점 : Relationship
• 단점 : scaling의 어려움

Kind of Graphs

Directed vs Undirected

• 단방향 또는 양방향 (리트윗은 단방향, 페북친구는 양방향)
  Cyclic vs Acyclic
• node로 다시 돌아올 수 있는 형태인지
  Weighted vs Unweighted
• node의 Edge에 가중치가 있는지

Code

예시로 replit에 작성하였다.

Graph는 Array 또는 Hash table로 표현될 수 있다. 아래는 Array 형태이다. (index가 key값임)

// Edge List
// 연결된 node를 나타냄
const graph = [[0, 2], [2, 1], [1, 3], [2, 3]]

// Adjacent List
// node(index)에 연결된 다른 node들을 나타냄
const graph = [[2], [2, 3], [0, 1, 3], [1, 2]]

// Adjacent Matrix
// 2차원 Matrix로 나타냄
const graph = [
  [0, 0, 1, 0],
  [0, 0, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 1, 0]
]

이미지는 visualgo에서 테스트 해본 결과이다. 코드처럼 3가지 형태로 나타내진다.
(참고 : visualgo에서 노드를 지우려면 Select + Del 로 지운다.)