그래프 탐색 알고리즘(Graph Traversals)

그래프(Graph)

• 기본 정의

  • 정점(V: vertices)이라고 불리는 노드들의 집합과 간선(E: edge)이라고 불리는 정점 간의 선으로 이루어짐.
  • (V,E)로 나타낸다.
    • (5, 3) ⇒ 정점 5개, 간선 3개

• 사용

  • 네트워크, 전자회로, 운송 방법(길찾기)

• 종류

  • 방향을 가지는 그래프(Directed graph)

  • 방향을 가지지 않는 그래프(Undirected graph)

  • 순환 그래프(cycle graph): 첫번째 정점과 마지막 정점이 동일

  • 비순환 그래프(acyclic graph)

  • 트리 - 포레스트(forest), 신장트리(spanning), .....

• 표현:

  • 일반적인 인접 무방향 그래프

    

  • 방향 그래프

  • 무방향 가중(weight) 그래프

  ⇒ 인접 매트릭스(인접 행렬)의 필요한 공간은 다음과 같다. : O($V^2$)

•