πŸ“šTech-Stack

# κ·Έλž˜ν”„(Graph)

written by sohyeon, hyemin πŸ’‘


# 1. κ·Έλž˜ν”„λž€?

κ·Έλž˜ν”„(Graph)λŠ” λ…Έλ“œ(node)와 κ°„μ„ (가지, edge)을 ν•˜λ‚˜λ‘œ λͺ¨μ•„ 놓은 자료ꡬ쑰λ₯Ό λ§ν•œλ‹€.

즉, μ—°κ²°λ˜μ–΄ μžˆλŠ” 객체 κ°„μ˜ 관계λ₯Ό ν‘œν˜„ν•  수 μžˆλŠ” 자료ꡬ쑰


# 2. κ·Έλž˜ν”„μ˜ νŠΉμ§•

  • κ·Έλž˜ν”„λŠ” λ„€νŠΈμ›Œν¬ λͺ¨λΈμ΄λ‹€.

  • 2개 μ΄μƒμ˜ κ²½λ‘œκ°€ κ°€λŠ₯ν•˜λ‹€.

  • self-loop 뿐만 μ•„λ‹ˆλΌ loop/circuitμ „λΆ€ κ°€λŠ₯ν•˜λ‹€.

  • νŠΈλ¦¬μ™€ 달리 루트, λΆ€λͺ¨-μžμ‹μ˜ κ°œλ…μ΄ μ—†λ‹€.

  • μˆœνšŒλŠ” DFS(Depth-First Search)λ‚˜ BFS(Breadth-First Search)둜 이루어진닀.

  • κ·Έλž˜ν”„λŠ” μˆœν™˜(Cyclic) ν˜Ήμ€ λΉ„μˆœν™˜(Acyclic)이닀.

    • μˆœν™˜ κ·Έλž˜ν”„(Cycle)
      λ‹¨μˆœ 경둜의 μ‹œμž‘ 정점과 μ’…λ£Œ 정점이 λ™μΌν•œ 경우λ₯Ό λ§ν•œλ‹€.
    • λΉ„μˆœν™˜ κ·Έλž˜ν”„
      사이클이 μ—†λŠ” κ·Έλž˜ν”„λ₯Ό μ˜λ―Έν•œλ‹€.

  • κ·Έλž˜ν”„λŠ” λ°©ν–₯ κ·Έλž˜ν”„(Undirected Graph)와 무방ν–₯ κ·Έλž˜ν”„(Directed Graph)κ°€ μžˆλ‹€.

    • 무방ν–₯ κ·Έλž˜ν”„
      간선을 ν†΅ν•΄μ„œ μ–‘λ°©ν–₯으둜 갈 수 μžˆλ‹€.
    • λ°©ν–₯ κ·Έλž˜ν”„
      간선에 λ°©ν–₯성이 μ‘΄μž¬ν•˜λŠ” κ·Έλž˜ν”„μ΄λ‹€.

  • κ·Έλž˜ν”„λŠ” μ—°κ²° κ·Έλž˜ν”„(Connected Graph) ν˜Ήμ€ λΉ„μ—°κ²° κ·Έλž˜ν”„(Disconnected Graph)이닀.

    • μ—°κ²° κ·Έλž˜ν”„
      무방ν–₯ κ·Έλž˜ν”„μ—μ„œ λͺ¨λ“  μ •μ μŒμ— λŒ€ν•΄ 항상 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜λŠ” κ·Έλž˜ν”„ ex) 트리
    • λΉ„μ—°κ²° κ·Έλž˜ν”„
      무방ν–₯ κ·Έλž˜ν”„μ—μ„œ νŠΉμ • μ •μ μŒ 사이에 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ” κ·Έλž˜ν”„

  • 이외에도 κ·Έλž˜ν”„μ˜ μ’…λ₯˜μ—λŠ” κ°€μ€‘μΉ˜ κ·Έλž˜ν”„(Weighted Graph), μ™„μ „ κ·Έλž˜ν”„(Complete Graph) 등이 μžˆλ‹€.

    • κ°€μ€‘μΉ˜ κ·Έλž˜ν”„
      간선에 λΉ„μš©μ΄λ‚˜ κ°€μ€‘μΉ˜κ°€ ν• λ‹Ήλœ κ·Έλž˜ν”„
    • μ™„μ „ κ·Έλž˜ν”„
      κ·Έλž˜ν”„μ— 속해 μžˆλŠ” λͺ¨λ“  정점이 μ„œλ‘œ μ—°κ²°λ˜μ–΄ μžˆλŠ” κ·Έλž˜ν”„

# 3. κ·Έλž˜ν”„μ˜ κ΄€λ ¨ μš©μ–΄

  • 정점(vertex)
    μœ„μΉ˜λ₯Ό μ˜λ―Έν•œλ‹€. (node와 같은 의미)

  • κ°„μ„ (edge)
    μœ„μΉ˜ κ°„μ˜ κ΄€κ³„λ‘œ λ…Έλ“œ(node)λ₯Ό μ—°κ²°ν•˜λŠ” 선이닀.

  • 인접 정점(adjacent vertex)
    간선에 μ˜ν•΄ 직접 μ—°κ²°λœ 정점을 μ˜λ―Έν•œλ‹€.

  • μ •μ μ˜ 차수(degree)
    무방ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•˜λ‚˜μ˜ 정점에 μΈμ ‘ν•œ μ •μ μ˜ 수λ₯Ό μ˜λ―Έν•œλ‹€.
    무방ν–₯ κ·Έλž˜ν”„μ— μ‘΄μž¬ν•˜λŠ” μ •μ μ˜ λͺ¨λ“  차수의 ν•© = κ·Έλž˜ν”„μ˜ κ°„μ„  수의 2λ°°

  • μ§„μž… 차수(in-degree)
    λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€μ—μ„œ μ˜€λŠ” κ°„μ„ μ˜ 수λ₯Ό μ˜λ―Έν•œλ‹€.

  • μ§„μΆœ 차수(out-degree)
    λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€λ‘œ κ°€λŠ” κ°„μ„ μ˜ 수λ₯Ό μ˜λ―Έν•œλ‹€.

  • 경둜 길이(path length)
    경둜λ₯Ό κ΅¬μ„±ν•˜λŠ” 데 μ‚¬μš©λœ κ°„μ„ μ˜ 수λ₯Ό μ˜λ―Έν•œλ‹€.

  • λ‹¨μˆœ 경둜(simple path)
    경둜 μ€‘μ—μ„œ λ°˜λ³΅λ˜λŠ” 정점이 μ—†λŠ” 경우λ₯Ό λ§ν•œλ‹€.

  • 사이클(cycle)
    λ‹¨μˆœ 경둜의 μ‹œμž‘ 정점과 μ’…λ£Œ 정점이 같은 경우λ₯Ό λ§ν•œλ‹€.


# 4. κ·Έλž˜ν”„μ™€ 트리의 차이점

κ·Έλž˜ν”„(Graph) 트리(Tree)
μ •μ˜ λ…Έλ“œ(node)와 κ·Έ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” κ°„μ„ (edge)을 ν•˜λ‚˜λ‘œ λͺ¨μ•„ 놓은 자료ꡬ쑰 κ·Έλž˜ν”„μ˜ ν•œ μ’…λ₯˜
DAG(Directed Acyclic Graph)의 ν•œ μ’…λ₯˜
λ°©ν–₯μ„± λ°©ν–₯κ·Έλž˜ν”„(Directed), 무방ν–₯ κ·Έλž˜ν”„(Undirected) λͺ¨λ‘ 쑴재 λ°©ν–₯κ·Έλž˜ν”„(Directed)
사이클 사이클(Cycle)와 자체 κ°„μ„ (self-loop) κ°€λŠ₯
μˆœν™˜ κ·Έλž˜ν”„(Cyclic), λΉ„μˆœν™˜ κ·Έλž˜ν”„(Acyclic) λͺ¨λ‘ 쑴재		 사이클(Cycle)와 자체 κ°„μ„ (self-loop) λΆˆκ°€λŠ₯
λΉ„μˆœν™˜ κ·Έλž˜ν”„(Acyclic)
루트 루트 λ…Έλ“œμ˜ κ°œλ…μ΄ μ—†μŒ ν•œ 개의 루트 λ…Έλ“œλ§Œμ΄ 쑴재, λͺ¨λ“  μžμ‹ λ…Έλ“œλŠ” ν•œ 개의 λΆ€λͺ¨ λ…Έλ“œλ§Œμ„ 가짐
λΆ€λͺ¨-μžμ‹ λΆ€λͺ¨-μžμ‹μ˜ κ°œλ…μ΄ μ—†μŒ λΆ€λͺ¨-μžμ‹ 관계, top-bottom λ˜λŠ” bottom-top으둜 이루어짐
λͺ¨λΈ λ„€νŠΈμ›Œν¬ λͺ¨λΈ 계측 λͺ¨λΈ
순회 DFS, BFS DFS, BFSμ•ˆμ˜ Pre-order, In-order, Post-order
κ°„μ„ μ˜ 수 κ·Έλž˜ν”„μ— 따라 κ°„μ„ μ˜ μˆ˜κ°€ 닀름
간선이 없을 μˆ˜λ„ 있음		 λ…Έλ“œκ°€ N인 νŠΈλ¦¬λŠ” 항상 N-1의 간선을 가짐
경둜 - μž„μ˜μ˜ 두 λ…Έλ“œ κ°„μ˜ κ²½λ‘œλŠ” 유일
μ˜ˆμ‹œ 및 μ’…λ₯˜ 지도, μ§€ν•˜μ²  λ…Έμ„ λ„μ˜ μ΅œλ‹¨ 경둜, μ „κΈ° 회둜의 μ†Œμžλ“€, λ„λ‘œ(ꡐ차점과 일방 톡행길) 이진 트리, 이진 탐색 트리, κ· ν˜• 트리(AVL트리, red-black 트리), 이진 νž™(μ΅œλŒ€νž™, μ΅œμ†Œνž™) λ“±

# 5. κ·Έλž˜ν”„μ˜ κ΅¬ν˜„ 2가지

# 인접 리슀트(adjacency list)

인접 리슀트둜 κ·Έλž˜ν”„λ₯Ό ν‘œν˜„ν•˜λŠ” 것이 κ°€μž₯ 일반적인 방법이닀.

  • λͺ¨λ“  정점(ν˜Ήμ€ λ…Έλ“œ)을 인접 λ¦¬μŠ€νŠΈμ— μ €μž₯ν•œλ‹€. 즉, 각각의 정점에 μΈμ ‘ν•œ 정점듀을 리슀트둜 ν‘œν˜„ν•œ 것이닀.
    • λ°°μ—΄(ν˜Ήμ€ ν•΄μ‹œν…Œμ΄λΈ”)κ³Ό λ°°μ—΄μ˜ 각 μΈλ±μŠ€λ§ˆλ‹€ μ‘΄μž¬ν•˜λŠ” 또 λ‹€λ₯Έ 리슀트(λ°°μ—΄, 동적 κ°€λ³€ 크기 λ°°μ—΄(arraylist), μ—°κ²°λ¦¬μŠ€νŠΈ(linked list) λ“±)λ₯Ό μ΄μš©ν•΄μ„œ 인접 리슀트λ₯Ό ν‘œν˜„ν•  수 μžˆλ‹€.
0 : 1
1 : 2
2 : 0, 3
3 : 2
4 : 6
5 : 4
6 : 5

  • 무방ν–₯ κ·Έλž˜ν”„(undirected graph)μ—μ„œ (a, b) 간선은 두 번 μ €μž₯λœλ‹€.

    • ν•œ λ²ˆμ€ a 정점에 μΈμ ‘ν•œ 간선을 μ €μž₯ν•˜κ³  λ‹€λ₯Έ ν•œ λ²ˆμ€ b에 μΈμ ‘ν•œ 간선을 μ €μž₯ν•œλ‹€.

  • κ·Έλž˜ν”„μ—μ„  νŠΉμ • λ…Έλ“œμ—μ„œ λ‹€λ₯Έ λͺ¨λ“  λ…Έλ“œλ‘œ 접근이 κ°€λŠ₯ν•˜μ§€ μ•Šλ‹€ => Graph 클래슀 ν•„μš”

    • νŠΈλ¦¬μ—μ„  νŠΉμ • λ…Έλ“œ ν•˜λ‚˜(루트 λ…Έλ“œ)μ—μ„œ λ‹€λ₯Έ λͺ¨λ“  λ…Έλ“œλ‘œ 접근이 κ°€λŠ₯ => Tree 클래슀 λΆˆν•„μš”

# ex) λ…Έλ“œλ₯Ό μ •μ˜ν•˜λŠ” κ°„λ‹¨ν•œ 클래슀

class Graph {
    public Node[] nodes;
}

class Node {

}

# 인접 ν–‰λ ¬

인접 행렬은 N X N 뢈린 ν–‰λ ¬(boolean matrix)λ‘œμ„œ matrix[i][j]κ°€ true라면 iμ—μ„œ j둜의 간선이 μžˆλ‹€λŠ” λœ»μ΄λ‹€.

  • 0κ³Ό 1을 μ΄μš©ν•œ μ •μˆ˜ ν–‰λ ¬(integer matrix)을 μ‚¬μš©ν•  수 μžˆλ‹€.

  • 인접 λ¦¬μŠ€νŠΈμ—μ„œλŠ” μ–΄λ–€ λ…Έλ“œμ— μΈμ ‘ν•œ λ…Έλ“œλ“€μ„ μ‰½κ²Œ 찾을 수 μžˆμ§€λ§Œ, 인접 ν–‰λ ¬μ—μ„œλŠ” μ–΄λ–€ λ…Έλ“œμ— μΈμ ‘ν•œ λ…Έλ“œλ₯Ό μ°ΎκΈ° μœ„ν•΄μ„œλŠ” λͺ¨λ“  λ…Έλ“œλ₯Ό μ „λΆ€ μˆœνšŒν•΄μ•Ό μ•Œ 수 μžˆλ‹€.


# Reference & Additional Resources

Last Updated: 12/5/2020, 11:36:44 AM

← μ—°κ²°λ¦¬μŠ€νŠΈ (LinkedList) β†’