[Python3] 알고리즘 - 그래프(Graph)

# ROKEY 3기 Python 강의 복습 겸 기록용으로 남기는 글입니다.

 

✅ 그래프(graph)

• 관계를 표현하는 구조

• 노드(vertex, 정점) : 하나의 데이터를 나타내는 객체
• 엣지(edge, 간선) : 두 노드 간의 연결 관계를 나타내는 데이터(연결선)
  • 👉🏻 두 노드 사이에 엣지가 있다면 ▪️ 두 노드는 인접해 있다 ▪️ 라고 표현
• 차수(degree) : 하나의 노드에 연결된 엣지의 수
• 경로(path) : 한 노드에서 다른 노드까지 가는 길(= 노드들의 순서)

---

📐 그래프의 수학적 표현

• G = (V, E)
  • V : 노드 집합
  • E : 두 노드를 연결하는 엣지 집합
  • 👉🏻 Graph1  ▶  V = {1, 2, 3, 4, 5}  &  E = {(1, 2), (1, 3), (1, 5), ..., (3, 5), (4, 5)}

---

📈그래프 종류

• 무방향 그래프 : 엣지에 방향 X
• 방향 그래프 : 엣지에 방향 O
• 가중치 그래프 : 엣지에 가중치 부여
  • 가중치: 한 지점에서 다른 지점으로 이동하는데 필요한 비용, 시간 등 

---

• 파이썬에서 그래프는 딕셔너리로 구현!
  • 키(key)     ▶ 노드
  • 값(value)  ▶ 키와 연결된 노드 리스트 

my_graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'E'], 
    'C': ['A', 'F', 'G'],
    'D': ['A', 'H'],
    'E': ['B', 'I'],
    'F': ['C', 'J'],
    'G': ['C'],
    'H': ['D'],
    'I': ['E'],
    'J': ['F'],     
}

---

✅ DFS(Depth First Search)

• 시작 노드의 특정 엣지를 따라 노드 계속 방문 ➡️ 말단 노드에 이르면 가장 가까운 분기점으로 돌아가서 ➡️ 방문하지 않은 노드 방향으로 위 과정을 반복하는 탐색 방법
  
  • 연결 요소 탐색 시 사용
  • 구현 시, Stack 이용

def my_dfs(graph, start_node):
    stack, visited = [], []  # 방문할 노드를 담을 Stack & 방문 여부 구분을 위한 List 생성

    stack.append(start_node)  # 탐색 시작노드를 Queue에 삽입  

    while stack:  # Stack이 비어있을 때까지 (= 방문할 노드가 없을 때까지)
        cur_node = stack.pop()  # 현재 방문할 노드 꺼내기
        
        if cur_node not in visited:	  # 꺼낸 노드가 방문하지 않은 노드라면
            visited.append(cur_node)  # 방문했음을 기록하기 위해 List에 추가
            stack.extend(reversed(graph[cur_node]))  # 인접 노드를 Stack에 반대 순서로 삽입(LIFO)

    print(f'DFS visited:    {visited}')

 

---

✅ BFS(Breadth First Search)

• 시작 노드에 인접한 모든 노드 우선 방문 ➡️ 다시 방문했던 노드에 인접한 모든 노드들 방문 ➡️ 이 과정을 반복하는 탐색 방법
  
  • 최단 경로를 탐색할 때 사용
  • 구현 시, Queue 이용 

def my_bfs(graph, start_node):
    queue, visited = [], []  # 방문할 노드를 담을 Queue & 방문 여부 구분을 위한 List 생성

    queue.append(start_node)  # 탐색 시작노드를 Queue에 삽입  

    while queue:  # Queue가 비어있을 때까지 (= 방문할 노드가 없을 때까지)
        cur_node = queue.pop(0)  # 현재 방문할 노드 꺼내기

        if cur_node not in visited:	  # 꺼낸 노드가 방문하지 않은 노드라면
            visited.append(cur_node)  # 방문했음을 기록하기 위해 List에 추가
            queue.extend(graph[cur_node])  # 인접 노드를 Queue에 순서대로 삽입

    print(f'BFS visited:    {visited}')