Graph

---

• 여러 노드가 서로 연결된 자료구조
• 무방향 그래프 : 간선에 방향성이 없는 그래프
• 방향 그래프 : 화살표로 간선 방향을 표기하고, 그래프의 정점 집합이 무방향 그래프와 같음
• *가중치 그래프 :8 간선마다 가중치가 다르게 부여된 그래프
• 순화 : 그래프의 모든 정점을 한번씩 방문(깊이 우선 탐색, 너비 우선 탐색)

---

01. 무방향 그래프

✍ 입력

class Graph:
    def __init__(self, size) -> None:
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)] # 2차원 배열

✍ 입력

G1 = Graph(4)

for item in G1.graph:    # 세로배열
    print(item)

💻 출력
[0, 0, 0, 0][0, 0, 0, 0]
[0, 0, 0, 0][0, 0, 0, 0]

✍ 입력

# A출발
# G1.graph[0][1] = 1 # (A, A)
G1.graph[0][1] = 1    # (A, B) 간선(edge)
G1.graph[0][2] = 1    # (A, B) 간선(edge)
G1.graph[0][3] = 1    # (A, B) 간선(edge)

✍ 입력

# B출발
G1.graph[1][0] = 1    # (B, A) 간선
# G1.graph[1][1] = 0  # (B, B)
G1.graph[1][2] = 1    # (B, C)
# 1.graph[1][3] = 1   # (B, D)

✍ 입력

# C출발
G1.graph[2][0] = 1    # (C, A)
G1.graph[2][1] = 1    # (C, B)
# G1.graph[2][2] = 1  # (C, C)
G1.graph[2][3] = 1    # (C, D)

✍ 입력

# D출발
G1.graph[3][0] = 1    # (D, A)
# G1.graph[3][1] = 1  # (D, B)
G1.graph[3][2] = 1    # (D, C)
# G1.graph[3][3] = 1  # (D, D)

✍ 입력

print('무방향 그래프 ')
for item in G1.graph:
    print(item)

💻 출력
무방향 그래프
[0, 1, 1, 1][1, 0, 1, 0]
[1, 1, 0, 1][1, 0, 1, 0]

2. 방향성 그래프

✍ 입력

G3 = Graph(4)

# G3.graph[0][0] = 0  # A -> A
G3.graph[0][1] = 1    # A -> B
G3.graph[0][2] = 1    # A -> C
# G3.graph[0][3] = 0  # A -> D

# G3.graph[1][0] = 0  # B -> A
# G3.graph[1][1] = 0  # B -> B
# G3.graph[1][2] = 0  # B -> C
# G3.graph[1][3] = 0  # B -> D

# G3.graph[2][0] = 0  # C -> A
# G3.graph[2][1] = 0  # C -> B
# G3.graph[2][2] = 0  # C -> C
# G3.graph[2][3] = 0  # C -> D

G3.graph[3][0] = 1    # D -> A
# G3.graph[3][1] = 0  # D -> B
# G3.graph[3][2] = 0  # D -> C
G3.graph[3][3] = 1    # D -> D

print('방향성 그래프')
for item in G3.graph:
    print(item)

💻 출력
방향성 그래프
[0, 1, 1, 0][0, 0, 0, 0]
[0, 0, 0, 0][1, 0, 0, 1]