최단경로 탐색 & 깊이우선, 너비우선 탐색

그래프의 활용

최단경로 문제

• |E|>0인 그래프 G=(V, E)에서 꼭짓점 v₁, v₂ ∈ V 간의 가장 짧은 거리의 경로를 찾는 문제
• 출발점(source): 경로의 시작점
• 도착점(destination): 경로의 목적지

가중치 방향 그래프

• 가중치가 부여되지 않은 그래프: 경로의 길이(경로에 포함되는 모서리의 수)로 최단경로
• 가중치가 부여된 경우: 가중치를 계산하여 가중치에 의해 최단거리가 결정
• 가중치가 비용이라면 가중치의 합이 가장 작은 경로가 최단거리이고, 효과라면 가중치의 합이 큰 경로가 최단거리

다익스트라 알고리즘

• 그래프 G=(V, E)가 있을 때, V={v₁, v₂, ... , vₙ}이고 시작점이 v₁라고 가정했을 때 다익스트라 알고리즘에 사용되는 기호와 가정
  • C[vᵢ, vⱼ]: 꼭짓점 vᵢ에서 vⱼ로 가는 가중치를 의미
  • D[v₁]: 시작점 v₁에서부터 vᵢ까지 이르는 최단경로의 가중치를 의미하는데, v₁에서 vᵢ까지 가는 경로가 없으면 그 가중치는 ∞로 나타냄
  • 집합 S: 최단경로에 선택된 꼭짓점은 집합 S의 원소로 포함시키고, 그래프 G의 꼭짓점 집합 V와 상등(S=V)이 되면 알고리즘이 종료됨

void Dijkstra(){
    S = {v₁};
    V = {v₂, v₃, ... , vₙ};
    
    for (vᵢ ∈ V){
        D[Vᵢ] = ∞;
    }
    while (vₓ ∈ V){
        if (D[Vₓ]가 최소){
            S = S ∪ {Vₓ};
            V = V - {Vₓ};
        }
        for (Vₓ에 인접한 vᵥ ∈ V){
            D[Vₓ] = min(D[Vₓ], D[Vᵥ]+C[Vₓ, Vᵥ]);
        }
    }
}

---

그래프 탐색

• 깊이 우선 탐색은 스택 메모리 구조 사용
• 너비 우선 탐색은 큐 메모리 구조 사용

깊이 우선 탐색

• DFS, Depth-First Search
• 어떠한 시작점 v₁에서 인접해 있는 꼭짓점 중 아직 탐색하지 않은 꼭짓점 v₂를 방문하고, 꼭짓점 v₂에 인접해 있는 꼭짓점 중 아직 탐색하지 않은 꼭짓점 v₃를 방문하는 것을 반복
  1. 시작점 v를 탐색
  2. 꼭짓점 v에 인접한 꼭짓점들 중 탐색되지 않은 꼭짓점 vₛ(s = sub)를 탐색
  3. 꼭짓점 vₛ를 v로 하여 2의 과정을 반복
  4. 더 이상 탐색되지 않은 꼭짓점이 없으면 이전에 탐색한 꼭짓점을 v로 하여 2~3의 과정을 반복
  5. 그래프의 모든 꼭짓점을 탐색할 때까지 반복
• 백 트래킹: 이전에 방문한 꼭짓점들을 다시 방문하는 과정

깊이 우선 탐색 알고리즘

• 한 방향으로 끝까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아가 다른 방향으로 다시 탐색 진행
• 되돌아가기 위해서 스택 필요, 순환함수 호출로 묵시적인 스택 이용

def dfs(graph, start, visited = set()):	# 처음 호출할 때 visited 공집합
    if start not in visited:		# start가 방문하지 않은 정점이면
        visited.add(start)		# start를 방문한 노드 집합에 추가
        print(start, end='')		# start를 방문했다고 출력
        nbr = graph[start] - visited	# nbr: 차집합 연산 이용
        for v in nbr:			# v ∈ {인접정점} - {방문정점}
            dfs(graph, v, visited)	# v에 대해 dfs를 순환적으로 호출

너비 우선 탐색

• BFS, Breadth-First Search
• 시작점 v₁으로부터 인접한 꼭짓점 v₂₁, ... , v₂ₙ을 모두 탐색하고, 다시 꼭짓점 v₂₁을 시작으로 인접한 꼭짓점 v₃₁, ... , v₃ₘ을 차례로 탐색하는 방식을 반복

너비 우선 탐색 알고리즘

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐를 사용하여 구현

def bfs(graph, start_:
    visited = set([start])		# 맨 처음에는 start만 방문한 정점
    queue = collections.deque([start])	# 컬렉션의 디큐 개체 생성 (큐로 사용)
    while queue:			# 공백이 아닐 때 까지
        vertex = queue.popleft()	# 큐에서 하나의 정점 vertex를 빼냄
        print(vertex, end='')		# vertex는 방문했음을 출력
        nbr = graph[vertex] - visited	# nbr: 차집합 연산 이용
        for v in nbr:			# v ∈ {인접정점} - {방문정점}
            visited.add(v)		# v는 방문했음
            queue.append(v)		# V를 큐에 삽입