그래프

• 연결되어있는 개체간의 관계를 표현한 자료구조
• 정점과 간선의 집합으로 구성
  • 정점(Vertext) : 연결할 개체
  • 간선(Edge) : 개체 관의 관계, 개체를 연결하는 선

그래프 종류

방향성에 따라

• 방향그래프(Directed Graph) : 정해진 방향 없이 양방향으로 갈 수 있다

  셀프엣지(자기자신을 가리키는 간선)를 갖는 그래프도 있다

• 무방향그래프(Undirected Graph) : 간선에 방향성이 존재한다

순환성에 따라

• 순환 그래프(Cyclic Graph) : 하나이상의 사이클이 있는 그래프
• 비순환 그래프(Acyclic Graph) : 사이클이 하나도 없는 그래프

연결성에 따라

• 연결그래프(Connected Graph) :
• 단절그래프(Disconnected Graph)

기타

• 가중치 그래프(Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
• 완전 그래프(Complete Graph) : 모든 정점이 서로 연결되어 있는 그래프
• 부분 그래프(Isolated Subgraphs) : 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다

그래프 표현 방법