graph

graph

consists of nodes connected by edges

그래프 용어

• 정점(vertex)
• 간선(edge)
• 진입차수(in-degree), 진출차수(out-degree): 한 정점에 진입(들어오고)하고 진출(나가는)하는 간선의 개수
• 자기루프(self-loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 한다. 다른 정점을 거치지 않는다.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있는 것이다.

  ---

구분

Direction

• Directed graph
• Undirected graph (tree)

Cycle

• cyclic
• acyclic

additional info

• weighted
• unweighted

  ---

표현방법

• adjacency matrix (2차원 배열/ 인접행렬)

  • 두 정점(vertex)이 직접 이어져있다면 이 두 정점은 인접한 정점
  • 인접해있다면 0(false), 인접하지 않았다면 1(true)로 표현한다. 단, 가중치 그래프라면, 0,1 대신 관계에서 의미있는 값을 저장한다. (ex. 거리, 비용 등)
  • 두 정점 사이의 관계 유무를 확인할 때 유용하다
  • 가장 빠른 경로를 찾을때 주로 사용한다
    

• adcagency list (배열의 노드를 나열하고 관계를 linked list로 표현)

  • 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다.
  • 리스트는 자신과 인접한 다른 정점을 담는다.
  • 모든 경우의 수를 저장하기는 인접행렬과 다르게 인접한 경우만 리스트로 나타내므로, 메모리를 효율적으로 사용하고 싶을때 인접 리스트를 사용한다.

이미지 출처
https://ko.myservername.com/java-graph-tutorial-how-implement-graph-data-structure
참고자료
https://www.youtube.com/watch?v=fVcKN42YXXI