| 개념 |

  •  그래프의 종류
    • 무 방향 그래프 : 정점 사이에 방향성이 없는 간선으로 연결된 그래프 (V1,V2) = (V2,V1)
    • 방향 그래프 : 간선이 화살표로 표현되어 방향성을 가지는 그래프  <V1,V2) != <V2,V1>
    • 연결 그래프 : 모든 정점에서 다른 모든 정점으로 경로가 있음
    • 약 연결 그래프 : 방향을 제거하면 연결그래프가 됨
    • 강 연결 그래프 : 방향성이 있는 연결그래프
    • 완전그래프 : 두 쌍의 모든 정점 사이에 간선이 있는 그래프
      • 방향그래프 간선의 수 n(n-1)
      • 무방향 그래프 간선의수 n(n-1)/2
  • 그래프의 용도
    • 여객기의 항로, 버스의 노선, 판매원의 경로
  • 그래의 표현 방법

A(i, j)

1

 Vi와  Vj 가 인접한 경우 즉, 두 정점간에 연결선이 존재하는 경우

0

 두 정점간에 연결선이 없는 경우

      • 무방향 그래프의 인접 행렬은 대칭, 방향 그래프의 인접행렬은 대칭이 아닐 수도 있음

    • 인접 리스트 : 각 정점에 인접된 정점의 연결 리스트
      • 깊이 우선 탐색, 나비 우선 탐색 시 탐색 순서 결정