Don't Worry, Be Happy πŸ˜›
#data-structure#cpp#study-notes#resources

자료ꡬ쑰 2

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

#κ·Έλž˜ν”„

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

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

#κ·Έλž˜ν”„μ˜ μ •μ˜

정점, κ°„μ„ μœΌλ‘œ 이루어진 자료ꡬ쑰 Graph G = (V, E)

  • V : 정점(Vertex)의 집합(μœ ν•œ 집합)
  • E : κ°„μ„ (Edge)의 집합(정점 쌍으둜 ν‘œν˜„)

#κ·Έλž˜ν”„μ˜ μ’…λ₯˜

  1. 무방ν–₯μ„± κ·Έλž˜ν”„(Undirected Graph)
    • 정점 μ‚¬μ΄μ˜ μ—°κ²° 관계가 λ°©ν–₯성이 μ—†λŠ” κ·Έλž˜ν”„
  2. λ°©ν–₯μ„± κ·Έλž˜ν”„(Directed Graph)
    • 정점 μ‚¬μ΄μ˜ μ—°κ²° 관계가 λ°©ν–₯성이 μžˆλŠ” κ·Έλž˜ν”„
  3. κ°€μ€‘μΉ˜ κ·Έλž˜ν”„(Weighted Graph) & λ„€νŠΈμ›Œν¬(Network)
    • 간선에 κ°€μ€‘μΉ˜(λΉ„μš© λ“±)κ°€ ν• λ‹Ήλœ κ·Έλž˜ν”„
    • 예) vertex : λ„μ‹œ, edge : λ„λ‘œ, κ°€μ€‘μΉ˜ : 거리

#κ·Έλž˜ν”„ ν‘œν˜„ μ˜ˆμ‹œ

graph_example

//무방ν–₯μ„± μ—μ§€λŠ” ()둜 ν‘œν˜„
V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
//λ°©ν–₯μ„± μ—μ§€λŠ” <>둜 ν‘œν˜„
V(G3) = {0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}

μ˜ˆμ‹œ

  • λ„λ‘œλ§
  • λ„€νŠΈμ›Œν¬
  • μ§€ν•˜μ²  노선도

$$

Share this post