Graph

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.
• 정점 집합과 간선 집합으로 표현된다.
• 정점과 간점은 node와 edge로 보인다.
• 보통 지하철 노선도, 페이지 랭크 알고리즘에 많이 사용된다.

특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 방향 그래프 / 무방향 그래프로 나뉜다.
• 간선은 가중치르 가질 수 있다.
• 사이클이 발생할 수 있다 (무한루프에 빠지지 않도록 한다

무방향 그래프

• 간선으로 이루어진 정점끼리 양방향으로 이동이 가능하다.

  → (A,B) 와 (B,A) 는 같은 간선으로 취급된다.

  • ex) 양방향 통행

양방향 그래프

• 간선에 방향성이 존재하는 그래프

  → 양방향으로 갈 수 있어도 (A,B) 와 (B,A) 는 같은 간선으로 취급된다

  • 일방 통행

연결 그래프

• 모든 정점이 서로 이동 가능 상태인 그래프이다.