[자료구조] 13. 그래프(Graph)

그래프는 정점과 간선의 집합으로 이루어진 자료구조이다.

정점(vertex)는 노드(node)라고도 부른다.

간선(edge)는 정점의 쌍으로 표현되는데, 간선을 통해서 정점 사이를 이동할 수 있다.

 

이때 간선에 방향이 존재하면 directed edge, 존재하지 않으면 undirected edge라고 하는데, 모든 간선이 directed edge인 그래프를 directed graph, 모든 간선이 undirected edge인 그래프를 undirected graph라고 한다.

용어

directed edge: 방향이 존재하는 간선.

undirected edge: 방향이 존재하지 않는 간선.

directed graph: 모든 간선이 directed edge인 그래프.

undirected graph: 모든 간선이 undirected edge인 그래프.

 

간선의 끝점(end vertices(endpoints) of an edge): 간선의 양끝에 있는 두 정점을 의미한다.

정점에 부속한 간선들(edges incident on a vertex): 정점 V에 연결되있는 간선들을 의미한다.

인접 정점들(adjacent vertices): 두 노드가 간선으로 연결되어 있을때 인접했다고 한다.

정점의 차수(degree of a vertex): 정점에 연결된 간선의 개수를 의미한다.

병렬 간선들(parallel edges): 같은 양 끝점을 공유하는 간선들을 의미한다.

self-loop: 같은 정점을 양 끝점으로 가지는 간선을 의미한다.

 

path: 정점과 간선이 번갈아 나타나는 시퀸스(squence). 정점에서 시작해 정점에서 끝난다.

path의 길이: 경로에 존재하는 간선의 개수를 의미한다.

simple path: 정점과 간선이 겹치지 않는 path를 의미한다.

cycle: 시작 정점과 도착 정점이 동일한 path.

simple cycle: 시작 정점을 제외하고 정점과 간선이 겹치지 않는 cycle.

Subgraph

subgraph S of graph G

spanning 

Connectivity

Tree and forest

Spanning tree and forest

정점과 간선의 성질

ADT

구현

Edge list structure

Adjacency list structure

Adjecency matrix structure

효율