그래프(Graph)

• 정점(Vertex)와 간선(Edge)의 집합
• 트리 또한 그래프의 일종이고 이때 트리는 사이클을 허용하지 않는 그래프이다

 

• 무방향 그래프
  • 말 그대로 간선의 방향이 없는 그래프
  • (3,4)나 (4,3)이나 같은 간선
• 방향 그래프
  • 간선에 방향이 있는 그래프
  • (3,4)와 (4,3)은 다른 간선
• Degree
  • 무방향 그래프
    • 간선의 개수
  • 방향 그래프
    • Indegree : 정점으로 들어오는 간선
    • outdgree : 정점에서 나가는 간선
• 그래프를 표현하는 방법
  • 인접 행렬(Adjacency Matrix)
    • 정점과 정점의 연결 관계를 행렬로 표현
    • 연결 관계를 한번에 파악할 수 있다
    • 간선의 개수와 무간하게 정점의개수^2의 공간이 필요
    • 해당 정점에 연결된 간선의 정보 파악 위해선 O(정점의 개수)의 시간이 걸린다
  • 인접 리스트(Adjacency List)
    • 한 정점에 연결된 정점을 연결리스트로 추가하여 표현
    • 연결 관계 파악 시 전체 리스트 개수 만큼 돌아야함
    • 간선의 개수만큼의 공간만 필요
    • 해당 정점에 연결된 간선 파악이 빠름
• 최소 신장 트리(Spanning Tree)
  • 신장 트리(Spanning Tree)
    • 모든 정점을 연결하고 사이클이 없는 그래프의 부분 그래프
    • n개의 정점이 있다면 간선의 수는 n-1개
  • 최소 신장 트리는 각 간선의 가중치의 합이 최소가 되는 신장 트리이다
    • 프림 알고리즘, 크루스칼 알고리즘이 대표적