그래프

그래프

실제 세계의 현상이나 사물을 정점(vertex) 또는 노드(node)와 간선(edge)으로 표현하기 위해 사용함

용어

• 무방향 그래프
  • 정점의 차수: 하나의 노드에 인접한 노드 수

• 방향 그래프
  • 진입 차수: 외부에서 들어오는 간선 수
  • 진출 차수: 외부로 나가는 간선 수

• 경로 길이: 경로를 구성하기 위해 사용된 간선 수
• 단순 경로: 처음 노드와 끝 노드를 제외하고 종복된 노드가 없는 경로
  • A → B → D (O)
  • A → C → D (O)
  • A → B → A → C → D (X)
  • A → B → D → C → A (O)
• 사이클: 단순 경로 중에서 시작 노드와 끝 노드가 동일한 경우
  • A → B → C → A

그래프 종류

• 무방향 그래프
  • 방향이 없는 그래프
  • 간선을 통해 노드는 양방향으로 갈 수 있다

무방향 그래프

• 방향 그래프
  • 간선에 방향이 있는 그래프
  • 방향이 있는 쪽으로만 갈 수 있다.

방향 그래프

• 가중치 그래프 (Weighted Graph)
  • 간선에 비용 또는 가중치가 할당된 그래프

가중치 그래프

• 연결 그래프 (Connected Graph)와 비연결 그래프(Disconnected Graph)
  • 연결 그래프: 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우
  • 비연결 그래프: 무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 경우

비연결 그래프

• 사이클(Cycle)과 비순환 그래프(Acyclic Graph)
  • 사이클: 단순 경로의 시작 노드와 종료 노드가 동일한 경우
  • 비순환 그래프: 사이클이 없는 그래프

비순환 그래프

그래프와 트리의 차이

• 트리는 그래프 중에 속한 특별한 종류라고 할 수 있다.
• 트리는 방향이 있는 비순환 그래프라고 할 수 있다.

	그래프	트리
정의	노드와 노드를 연결하는 간선으로 표현되는 자료 구조	그래프의 한 종류. 방향성이 있는 비순환 그래프
방향성	방향 그래프, 무방향 그래프 모두 존재함	방향 그래프만 존재함
사이클	사이클 가능함. 순환, 비순환 그래프 모두 존재함	비순환 그래프로 사이클이 존재하지 않음
루트 노드	루트 노드 존재하지 않음	루트 노드 존재함
부모/자식 관계	부모 자식 개념이 존재하지 않음	부모 자식 관계가 존재함