[자료구조] 그래프(graph) 기본 개념/용어 정리

그래프는 node와 edge로 이루어진다. 

edge에는 undirected edge, directed edge, weighted edge 가 있다. 

 

undirected edge (and unweighted)

 

directed edge (and weighted)

 

weighted edge 

 

 

-용어

subgraph: 그래프의 한 부분(그래프의 특성을 가지고 있는)

connected graph: 모든 노드가 다른 모든 노드로 접근이 가능한 그래프

disconnected graph: 최소 하나의 노드가 다른 모든 노드로 접근이 불가능한 그래프

adjacent node: 두 노드 사이에 edge로 곧바로 연결된 것

complete graph: 모든 노드가 다른 모든 노드로부터 인접한 것(edge로 곧바로 연결된 것)

 

 

-예제

connected graph

 

adjacent nodes

A, B

A, E

B, C

C, D

 

subgraph

 

disconnected graph

 

complete graph

 

 

-용어

path: edge의 순서 (from node A to node B)

cycle: 시작 노드로 다시 돌아오는 path

cyclic path: cycle을 가진 그래프

acyclic path: cycle이 없는 그래프

 

cyclic graph

 

acyclic graph