Graph

Graph

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

Undirected Graph / Directed Graph(Digraph)

말 그대로 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라 하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph 라고 한다.

Directed Graph(Digraph)

V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex u에서 vertex v로 가는 edge

Undirected Graph

V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex u와 vertex v를 연결하는 edge

Degree

Undirected Graph 에서 각 정점(Vertex)에 연결된 Edge 의 개수를 Degree 라 한다. Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

인접행렬 / 인접리스트 구현

다음의 그래프를 인접행렬과 인접 리스트로 구현해보겠습니다.

인접행렬 그래프

인접행렬로 구현할 때는 array[i][j] = 1 일 경우에 vertex i에서 vertex j로 가는 간선의 가중치가 1이라고 표현합니다.

가중치가 없는 그래프일 경우에는 i에서 j로 갈 수 있다라고 표현될 수 있습니다. i에서 j로 가는 간선이 없어서 갈 수 없는경에는 0이나 INF로 표현을 해도 됩니다.

인접리스트 그래프

그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프로 표현합니다. 각 정점마다 하나의 연결리스트를 갖는 방식으로 구현