07. 그래프(Graph)

그래프(Graph)는 객체 사이의 연결 관계(Connectivity)를 표현하는 자료구조이다. 그래프는 노드(Node or Vertex)와 간선(Edge)의 집합이다. 노드는 일반적으로 모델링하려는 시스템을 구성하는 객체를 나타내며, 간선은 이러한 객체 사이의 관계를 정의한다.

간선의 특성에 따른 그래프의 종류

구분	종류	설명
간선의 방향성	무방향 그래프	간선에 방향이 없는 그래프 (양방향 통행)
	방향 그래프	간선에 방향이 잇는 그래프 (일방 통행)
간선의 가중치	가중 그래프	간선에 가중치가 할당된 그래프
구조적 특징	완전 그래프	연결 가능한 최대 간선 수를 가진 그래프
	부분 그래프	그래프에서 일부의 노드나 간선을 제외하여 만든 그래프
	다중 그래프	중복된 간선을 포함하는 그래프

무방향 그래프(Undirected Graph)

무방향 그래프(Undirected Graph)는 두 노드를 연결하는 간선에 방향이 없는 그래프를 말한다.

방향 그래프(Directed Graph)

방향 그래프(Directed Graph)는 두 노드를 연결하는 간선에 방향이 있는 그래프를 말하며 다이그래프(Digraph)라고도 불린다.

가중 그래프(Weighted Graph)

가중 그래프(Weighted Graph)는 노드를 연결하는 간선에 가중치(Weight)가 할당된 그래프를 말한다. 노드와 노드를 연결하는 간선에 가중치 속성이 있을 때를 말하며, 이러한 가중치는 간선 사이의 비용(Cost)또는 거리(Distance)등 다양한 속성으로 사용될 수 있다. 무방향 그래프에 가중치가 존재할 때 이를 무방향 가중 그래프(Undirected Weighted Graph)라 하며, 방향 그래프에 가중치가 있을 때는 이를 방향 가중 그래프(Directed Weighted Graph)라 한다. 방향 가중 그래프를 네트워크(Network)라고도 부른다.

완전 그래프(Complete Graph)

완전 그래프(Complete Graph)는 그래프 내의 모든 노드가 일대일 간선으로 연결된 경우, 즉 연결 가능한 최대 한건수를 가진 그래프를 말한다.

부분 그래프(Sub Graph)

원래의 그래프에서 일부 노드나 간선을 제외하여 만든 그래프를 부분 그래프(Sub Graph)라 한다.

다중 그래프(Multi Graph)

다중 그래프(Multi Graph)는 중복된 간선을 포함하는 그래프를 말한다.

그래프 관련 용어

인접(Adjacent)

두 개의 노드를 연결하는 간선이 존재하는 경우 두 노드는 인접(Adjacent)되었다고 한다.

부속(Incident)

두개의 노드를 연결하는 간선이 존재하는 경우 이 간선은 두 노드에 각각 부속(Incident)되었다고 한다.

차수(Degree)

노드에 부속된(연결된) 간선의 개수를 차수(Degree)라 한다.

경로(Path)

두 노드 A에서 노드 B까지의 경로(Path)는 노드 A에서 노드 B에 이르는 간선들의 인접(Adjacent)노드를 순서대로 나열한 리스트를 말한다.

루프(Loop)

그래프의 임의의 노드에서 자기 자신으로 이어지는 간선을 루프(Loop)라고 한다.