그래프(Graph)

그래프는 노드(Node, 또는 정점 -vertex- 이라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성됩니다. 그래프는 무방향(undirected)일 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미입니다. 한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미합니다. 이번 스프린트에서는 무방향 그래프를 구현합니다.

그래프(Graph) 용어

• 노드(node) : 정점(vertice)라고도 불리며, 일반적으로 노드에는 데이터가 저장됨

• 간선(edge): 링크, arcs라고도 불리며, 노드간의 관계를 나타냄

• 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점. 위 그림에서 노드A와 B는 인접 정점이라고 할 수 있다

• 단순 경로(simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로

• 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수. 위 그래프에서 A의 차수는 3이다.

• 진출차수(out-degree)/진입차수(in-degree) : 방향그래프에서 사용되는 용어

  진출 차수 는 한 노드에서 외부로 향하는 간선의 수,

  진입차수 는 외부 노드에서 들어오는 간선의 수

그래프(Graph) 종류

• 그래프는 node(혹은 vertice)와 edge(혹은 arcs)로 구성되어 있으며 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델이다.
• 방향성에 따라 undirected graph 와 directed graph 로 나뉘며 간선에 비용이나 가중치를 할당하는 가중치 그래프(weighted graph)가 있다.
• 무방향 그래프(undirected graph): 간선을 통해 양방향으로 이동하며, 정점A와 정점B를 연결하는 간선은 (A, B)와 같이 쌍으로 표현한다.
• 방향 그래프(directed graph): 간선에 방향성이 존재한다. A →B 로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B> 와 <B, A>는 다르다.
• 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’라고도 한다.

그래프(Graph)그래프(Graph) 의 구현 방식

그래프의 표현 방식은 인접 행렬과 인접 리스트 두가지 방식으로 나눌 수 있다.