학습 일자 : 2023.05.01

Graph (그래프)

• 정점의 모음과 이 정점을 잇는 간선의 모음의 결합

  • 정점(Vertex or Node) : 데이터를 저장하는 위치
  • 간산(Edge) : 정점을 연결하는 선으로 링크(link) 또는 브랜치(branch)로도 불린다

• 한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 순환구조를 가짐

  → 어느 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 그 경로를 일컬어 ‘사이클(Cycle)’이라고 말함

• 간선의 방향성에 따라 단방향 그래프, 양방향 그래프가 있음 간선의 가중치에 따라 연결 그래프, 가중치 그래프가 있음

인접 행렬 (Adjacency Matrix)

⇒ 인접(adjacent) : 간선으로 연결되어 있는 두 정점을 가리켜 서로 ‘인접’ 또는 이웃 관계에 있다고 말함.

점끼리의 인접 관계를 나타내는 행렬 : 정점 수 크기(N x N)의 행렬을 만들어 인접 여부를 표시함

                     정점이 인접해 있는 경우는 1, 인접해 있지 않은 경우는 0으로 표시함

위상 정렬

위상 : 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태

→ 사물을 정점으로 바꿔 정점이 다른 정점의 관계 속에서 가지는 위치

그래프