(미완) 그래프 알고리즘 종류

1) 그래프 탐색 알고리즘 (Graph Search Algorithms)

그래프에서 특정 정점을 찾는 알고리즘

그래프의 각 정점을 순회하면서 방문해야 하므로, 그래프 순회 알고리즘(Graph Traversal Algorithms)으로 부르기도 한다.

• 너비 우선 탐색 (BFS)
• 깊이 우선 탐색 (DFS)

 

2) 최단 경로 알고리즘

최소 가중치 합을 가지는 경로를 찾는 알고리즘

네트워크 설계, 교통 시스템 최적화, 지리적 경로 탐색 등 다양한 분야에서 경로 최적화 문제를 해결하는 데 활용

• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 플로이드 알고리즘

---

알아보고 싶던 것은 그래프 탐색 알고리즘이므로 BFS와 DFS를 중점적으로 조사할 생각이다.

 

알고리즘의 시간 복잡도는 그래프의 구조에 따라 달라질 수 있으나, 일반적으로 O(V+E)로 표현된다.

1) 너비 우선 탐색 (BFS) - Breath-First Search

가까운 인접 정점을 모두 방문한 후, 그다음 가까운 정점을 방문하는 방식의 그래프 탐색 알고리즘

• 큐
• 최단 경로를 찾는데 유용
• 넓은 범위를 탐색할 때 메모리 소비가 크다
• 네트워크 라우팅, 소셜 네트워킹의 최단 경로 찾기

 

 

 

 

 

 

 

2) 깊이 우선 탐색 (DFS) - Depth-First Search

최대한 깊이 갈 수 있는 정점까지 가보고, 더 이상 진행 못하는 경우 다시 돌아와서 갈림길에 있는 미방문 정점부터 탐색을 시작하는 방식

• 스택, 재귀 호출 방식
• 메모리 소비가 적고 복잡한 경로나 사이클을 찾는데 유리
• 최단 경로를 보장하지 않음
• 퍼즐, 미로 찾기, 트리 구조 분석

 

 

 

 

g = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

 

1) 재귀함수를 이용

# DFS 함수를 정의합니다.
def dfs(graph, start, visited=None): #visited 기본값 None
    if visited is None: #visited가 없을 경우 선언
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

 

2) 스택을 이용

def dfs(graph, start):
    visited = set()  # 방문한 노드를 저장할 set
    stack = [start]  # 시작 노드를 스택에 추가
    while stack:
        node = stack.pop()  # 스택에서 가장 최근에 추가된 노드를 가져옴
        if node not in visited:
            visited.add(node)  # 방문한 노드를 저장
            print(node, end=' ')
            for next_node in graph[node]:
                if next_node not in visited:
                    stack.append(next_node)  # 다음에 방문할 노드를 스택에 추가

 

 

 

 

재귀쪽은 A-B로 향했는데 스택쪽은 A-C로 향했다. 효율면에서 보면 스택쪽이 한붓그리기처럼 다음 노드로 갈 때 불필요하게 간선을 거쳐가지 않은 듯 보인다...

 

의문점

1. 재귀와 스택 중 더 효율적인 쪽이 무엇인지

2. 재귀와 스택의 답이 다른데, (물론 방향이 다른 것뿐 둘다 틀린 답은 아닌 듯 하다.) 이 경우 어느 쪽을 사용하더라도 '코딩 테스트' 관점에서는 문제가 없는지

 

 

 

참고한 자료

https://yozm.wishket.com/magazine/detail/2411/

https://velog.io/@maantano/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC-DFS-BFS-%EC%A0%95%EB%A6%AC

https://python101.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-DFS-%EA%B5%AC%ED%98%84