[ KJ ] Week02

ꕥ

2주차에선 Graphs, BFS, DFS, 위상정렬을 활용한 알고리즘을 배웠습니다~

팀원들과 함께 이론 정리를 하고 문제를 푸니까 좀 더 이해하기 좋았는데 구현은 어려워서 못 하고 있습니다 ㅎㅎ

하지만 이론이라도 다 담아가겠다는 열정으로 해보겠습니다!

ꕥ

 

• Graphs

• Node, Vertex : Graphs에서 Data를 저장하거나 Data 없이 연결 구조를 표현
• Edge : Node와 Node를 연결해서 서로의 관계를 형성
• Multiple Edge : 같은 2개의 Node 사이에 간선이 여러 개
• Weight : Node 간의 연결 관계나 관계의 강도를 표현
• Path : Node와 Edge의 연속적인 연결
  1. 오일러 경로 : Graphs의 모든 Edge를 정확히 1번 이상 방문
  2. 오일러 회로 : 오일러 경로의 시작점과 끝점이 같은 경우로 경로가 회로를 형성
• Degree : Node에 연결돼 있는 Edge의 수
• Cycle : 오일러 회로와 다르게 모든 Node를 방문할 필요는 없으며, 시작점과 끝점만 같은 경로
• Arc : 방향성을 가진 Edge
• Tree와 차이점 : 모든 Node는 동등 관계이므로 Root Node와 Cycle 미존재

• BFS(너비 우선 탐색) : 시작 노드에서 가까운 노드부터 탐색하는 방식

• 구현 단계 : 큐를 이용
  1. 시작 노드를 큐에 넣고 방문 처리를 합니다.
  2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 큐에 넣고 방문 처리합니다.
  3. 위 과정을 큐가 빌 때까지 반복합니다.

• 구현 코드

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

• DFS(깊이 우선 탐색) : 시작 노드에서 연결된 노드 중 하나로 끝까지 탐색한 후, 다음 노드로 넘어가는 방식

• 구현 단계 : 재귀나 스택을 이용
  1. 시작 노드를 스택에 넣고 방문 처리를 합니다.
  2. 스택의 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
  3. 위 과정을 스택이 빌 때까지 반복합니다.

• 구현 코드

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)