그래프 순회(BFS, DFS)

그래프

그래프(Graph)

• 연결되어 있는 객체 간의 관계를 표현하는 자료구조
• ex)
  • 트리도 그래프의 하나
  • 전기회로의 소자 간 연결상태
  • 지도에서 도시들의 연결상태
  • 지하철 노선도
  • 도로망
  • 선수과목 관계

그래프의 역사

• 1800년대 오일러의 의하여 창안

• 오일러 문제

  • 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제

• A.B.C.D 지역의 연결 관계 표현

  • 위치 : 정점(node)
  • 다리 : 간선(edge)

• 오일러 정리

  • 모든 정점에 연결된 간선의 수가 짝수 이면 오일러 경로가 존재함
  • 따라서 그래프 (b)에는 오일러 경로가 존재하지 않음

그래프의 정의

• 그래프 G는(V,E)로 표시
• 정점(Vertices)
  • 여러 가지 특성을 가질 수 있는 객체 의미
  • V(G) : 그래프 G의 정점들의 집합
  • 노드(Node)라고도 불림
• 간선(Edge)
  • 정점들 간의 관계 의미
  • E(G) : 그래프 G의 간선들의 집합
  • 링크(link)라고도 불림

1. G1 연결 그래프(무방향)
   • V(G1)= {0, 1, 2, 3}, E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
2. G2 비연결 그래프(무방향)
   • V(G2)= {0, 1, 2, 3}, E(G3)= {(0, 1), (0, 2))}
3. G3 방향 그래프
   • V(G2)= {0, 1, 2}, E(G2)= {<0, 1>, <1, 0>, <1, 2>}

네트워크

• 가중치 그래프는 네트워크(network)라고도 함
• 간선에 비용(cost)이나 가중치(weight)가 할당된 그래프
• 네트워크의 예
  • 정점 : 각 도시를 의미
  • 간선 : 도시를 연결하는 도로
  • 가중치 : 도로의 길이

부분 그래프

• 정점 집합 V(G)와 간선 집합E(G)의 부분 집합으로 이루어진 그래프
• 그래프 G1의 부분 그래프들

그래프

• 인접 정점(adjacent vertex)
  • 하나의 정점에서 간선에 의해 직접 연결된 정점
  • G1에서 정점 0의 인접 정점: 정점 1, 정점2, 정점 3
• 무방향 그래프의 차수(degree)
  • 하나의 정점에 연결된 다른 정점의 수
  • G1에서 정점 0의 차수 : 3
• 방향 그래프의 차수(degree)
  • 진입 차수
  • 진출 차수
  • G3에서 정점 1의 차수: 내차수 1, 외차수 2
  • 방향 그래프의 모든 진입(진출) 차수의 합은 간선의 수

그래프 순회

BFS(너비 우선 탐색)

BFS는 그래프에서 노드를 탐색하는 방법 중 하나로, 시작 노드에서부터 근접한 노드부터 탐색하는 방식이다. 이것은 큐(queue)를 사용하여 구현한다. 탐색 순서대로 노드를 큐에 추가하고, 해당 노드와 연결된 노드를 모두 큐에 넣는다. 이렇게 하면 시작 노드로부터 멀리 떨어진 노드를 나중에 탐색한다.

BFS의 과정

• 시작 노드를 방문하고, 그 노드의 인접한 노드들을 모두 큐에 넣는다.
• 큐에서 노드를 꺼내서 방문하고, 해당 노드의 인접한 노드들을 큐에 넣는다. 이때 이미 큐에 들어있는 노드는 무시한다.
  큐가 빌 때까지 위 과정을 반복하면서 모든 노드를 탐색한다.

BFS 예시
친구 관계 그래프에서 '나'를 시작 노드로 하여 BFS로 탐색한다고 가정해보자 나의 친구 관계를 네트워크로 표현한 그래프에서 나와 직접 연결된 친구들을 먼저 탐색하고, 그 다음으로는 나와 한 단계 거리에 있는 친구들을 탐색하게 된다

DFS (깊이 우선 탐색)

DFS는 그래프에서 노드를 탐색하는 또 다른 방법으로, 시작 노드에서부터 한 방향으로 최대한 깊이 탐색하다가 더 이상 진행할 수 없으면 다시 뒤로 돌아와 다른 방향으로 탐색하는 방식이다. 이것은 스택(stack)이나 재귀(recursion)를 통해 구현된다.

DFS의 과정

• 시작 노드를 방문하고, 그 노드의 인접한 노드 중 아직 방문하지 않은 노드를 선택한다.
• 선택한 노드로 이동하여 해당 노드를 방문한다. 선택한 노드에 대해서도 다시 인접한 노드 중 방문하지 않은 노드를 선택하고 이동한다.
• 이동한 노드에 더 이상 방문하지 않은 인접 노드가 없다면, 이전 단계로 돌아가서 다른 방향의 노드를 선택하고 탐색을 진행한다.
  위 과정을 반복하면서 모든 노드를 탐색합니다.

DFS 예시
미로를 생각해보겠습니다. 시작점에서부터 한 방향으로 계속 나아가다가 막다른 길에 도달하면 다시 돌아가 다른 길을 찾아본다. 이렇게 하면 각 가능한 경로를 가능한 최대한 깊이 탐색하게 된다.

간단하게 정리하자면, BFS는 근접한 노드부터 탐색하고, DFS는 한 방향으로 깊이 탐색하다가 더 이상 진행할 수 없으면 돌아가서 다른 방향을 탐색한다.

차이점

• DFS는 한 경로를 최대한 깊이 탐색하고, BFS는 한 레벨의 노드들을 모두 탐색한 후 다음 레벨로 이동한다.
• DFS는 스택 또는 재귀를 사용하며, 최대한 깊이 탐색한다. BFS는 큐를 사용하며, 현재 노드와 같은 레벨에 있는 노드들을 먼저 탐색한다.
• DFS는 해를 찾을 때까지 더 깊이 들어가기 때문에 메모리 사용이 적지만, 무한 루프에 빠질 위험이 있다. BFS는 모든 노드를 한 단계씩 탐색하므로 무한 루프에 빠질 가능성이 낮지만, 메모리 사용이 더 많을 수 있다.
• 일반적으로 가중치가 없는 그래프에서 최단경로 탐색은 BFS를 이용한다.
  DFS와 BFS는 그래프 탐색을 다르게 접근하는 방법으로, 상황에 따라 어떤 방식을 선택하느냐에 따라 탐색 순서와 성능이 달라질 수 있다.