[알고리즘] 그래프와 그래프 탐색

개념

• 데이터들 간 관계를 표현
• 데이터가 있고 데이터들 간의 커넥션이 있는 경우 그래프로 나타냄
• 정점 = 데이터
• 간선 = 정점과 정점을 이어줌, 방향이 있을 수도 있고 없을 수도 있음
• 가중치 = 간선 위의 숫자

무방향 그래프

• 간선의 방향이 없는 그래프
• 가중치와는 무관
  

방향 그래프

• 간선의 방향이 있는 그래프
• 가중치와는 무관
  

가중치 그래프

• 간선에 가중치가 있는지 여부가 중요
• 간선의 방향과 무관

표현

인접행렬을 이용한 방식

• 2차원 배열 활용
• 2차원 배열의 인덱스 = 각 정점
• 배열의 값 = 정점의 가중치
• random access 가능 -> 성능 면에서 우수
• 정점의 개수 1000개 미만일 때 활용
  

인접리스트를 이용한 방식

• 링크드리스트 활용
• 메모리 측면에서 우수
• 정점의 개수 1000개 이상일 때 활용
  

탐색

깊이우선탐색(DFS) - LIFO

• 뒤로 가는 동작이 필요함 = 백트랙이 있음
• 최근에 push 된 정점에 방문함

1. 시작 정점을 방문한다.
2. 현재 방문한 정점과 연결된 정점 중, 아직 방문하지 않은 정점을 스택에 push 한다. 이때 방문한 정점의 visited를 true로 설정한다
3. stack에서 pop하면서 방문한다

2~3 과정을 모든 정점을 방문할 때까지 반복한다.

dfs_stack

def dfs(graph, start_node):
    visited = [False] * (len(graph) + 1)
    stack = [start_node]
    
    while stack:
        node = stack.pop()
        
        if not visited[node] :
            visited[node] = True;
            print(node)
            for adj_node in graph[node]: # 인접한 노드 방문
                    if not visited[adj_node]:
                        stack.append(adj_node)
              

# 그래프를 인접 리스트로 표현
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

# DFS 알고리즘 실행
dfs(graph, 1) # 1 3 2 5 4

dfs_recursion

def dfs(graph, start_node,visited):
    visited[start_node] = True
    print(start_node)
    
    for adj_node in graph[start_node]: # 인접한 노드 방문
       if not visited[adj_node]:
          dfs(graph,adj_node,visited)
              

# 그래프를 인접 리스트로 표현
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

visited = [False] * (len(graph) + 1)
# DFS 알고리즘 실행
dfs(graph, 1,visited) # 1 2 4 5 3

너비우선탐색(BFS) - FIFO

• 레벨: 몇 번 거쳐서 가느냐
• 같은 레벨끼리는 순서가 바뀌어도 상관없음
• 연결된 모든 것을 담아야 하므로 메모리 공간이 많이 필요
• 정점을 일단 큐에 넣어놓고 나중에 방문함

1. 시작 노드(1)를 큐에 넣고, 방문 처리를 한다
2. 큐에서 노드를 하나 꺼낸다(노드 1)
3. 해당 노드의 인접 노드 중 방문하지 않은 노드들(노드 2와 3)을 큐에 넣고 방문 처리를 한다.
4. 큐에서 노드를 하나 꺼낸다(노드 2)
5. 노드 2의 인접 노드 중 방문하지 않은 노드들(노드 4와 5)을 큐에 넣고 방문 처리를 한다.

위 과정을 큐가 빌 때까지 반복한다.

from collections import deque

def bfs(graph, start_node):
    visited = [False] * (len(graph) + 1)
    queue = deque([start_node])
    visited[start_node] = True # 시작노드 방문 처리
   
    
    while queue:
        node = queue.popleft() # 이어붙인 노드를 꺼냄
        print(node) # 방문 노드 출력
        for adj_node in graph[node]: # 인접한 노드 방문
            if not visited[adj_node]:
                queue.append(adj_node) # 큐에 이어붙임
                visited[adj_node] = True
            
# 그래프를 인접 리스트로 표현
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

# BFS 알고리즘 실행
bfs(graph, 1) # 1, 2, 3, 4, 5

---

참고자료

https://cafe.naver.com/dremdeveloper/418
https://cafe.naver.com/dremdeveloper/30