[20250203] 파이썬 프로그래밍 - 알고리즘 2

수업 목표

- 그래프 개요를 이해할 수 있다.

- 깊이 우선 탐색의 개념을 알고 구현할 수 있다.

- 너비 우선 탐색의 개념을 알고 구현할 수 있다.

 

 

1. 그래프

그래프

- 관계를 표현하는 구조. e.g. 도시를 연결하는 도로, 인맥 관계, 컴퓨터 네트워크 등

- 노드와 엣지로 구성된 자료 구조

    - 노드(node, 정점, vertex) : 하나의 데이터 단위를 나타내는 객체

    - 엣지(간선) : 두 노드간의 연결 관계를 나타내는 데이터 (연결선)

    - 두 노드 사이에 엣지가 있으면 '두 노드는 인접해 있다'고 표현함

- 차수(degree) : 하나의 노드에 연결된 엣지의 수

- 경로(path) : 한 노드에서 다른 노드까지 가는 길(노드들의 순서)

 

- 수학적 표현 : G = (V, E)

    - V : 노드의 집합

    - E : 두 노드를 연결하는 간선의 집합

 

- 그래프의 종류

    - 무방향 그래프(undirected graph) : 두 노드를 연결하는 엣지에 방향이 없는 그래프

    - 방향 그래프 (directed graph) : 엣지에 방향이 있는 그래프

    - 가중 그래프 (weighted graph) : 노드를 연결하는 엣지에 가중치(weight)를 부여한 그래프

        * 가중치는 한 지점에서 다른 지점으로 이동하는 데 필요한 비용이나 시간 등

- 딕셔너리로 주로 표현함 {노드: 키와 연결된 노드 리스트}

 

2. DFS (Depth First Search)

- 노드에 연결된 엣지를 모두 방문하는 것이 아닌 특정 한 개의 엣지를 계속 따라 방문하다가 끝에 다다르면,

  다시 가장 가까운 분기점으로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법

- 스택으로 구현 가능

def dfs(graph, start_node):
    stack = list()
    visited = list()
    
    stack.append(start_node)
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            stack.extend(reversed(graph[node]))
            visited.append(node)
    
    return visited # 방문 순서

 

3. BFS (Breadth First Search)

- 노드에 인접한 모든 엣지를 따라 노드에 방문하고,
   다시 방문한 노드에 인접한 모든 엣지를 따라 노드에 방문하는 과정을 반복하며 탐색하는 방법

- 큐로 구현 가능

def bfs(graph, start_node):
    queue = list()
    visited = list()
    
    queue.append(start_node)
    
    while queue:
        node = queue.pop(0)
        
        if node not in visited:
            queue.extend(graph[node])
            visited.append(node)
            
    return visited

 

 

Python

Rokey

20250203