그래프 개요

- 그래프 구성요소 -

Vertex 와 Edge 

 

-  Path - 

인접한 Vertex로 구성된 시퀀스

 

ex) v1에서 v9까지의 path

• [v1,v2,v3,v4,v5,v8,v6,v5,v9]

 

-degree-

한 vertex의 degree란 해당 vertex에 연결된 edge의 수 또는 가중치의 합

 

- Loop - 

시작점과 끝이 같은 Edge 

 

- Cycle - 

한 vertex에서 시작해 해당 vertex에서 끝나는 경로

 

ex) v1에서 v1까지의 path, cycle

• [v1,v2,v3,v4,v5,v8,v6,v5,v9,v1]

 

<그래프의 표현>

인접 행렬, 인접 리스트 간선 리스트 

 

-인접행렬-

전체 Vertex가 n 이라고 하면 n x n 크기의 2차원 행렬에 간선을 저장

만약 matrix[5][4] = True 이면 vertex 5에서 vertex4 로 이어지는 간선이 있음을 의미 

 

-인접리스트-

인접리스트 특정 vertex와 연결된 모든 vertex의 edge를 1차원 적으로 저장하는 리스트 

a[1] = [2, 4, 5] 는 1번쨰 vertex에 2,4,5 vertex와 연결되어 있음을 의미 

 

-간선리스트-

edge 는 두개의 vertex로 정의되는데 그 두개의 vertex를 저장하는 리스트 

a[0] = (1, 2) 

첫번쨰 edge는 1과2를 연결하는 리스트 

 

 

참고자료

https://ratsgo.github.io/data%20structure&algorithm/2017/11/18/graph/