그래프(Graph) - 1

이동엽·2023년 9월 9일

자료구조 및 알고리즘 / 자바

목록 보기

8/21

1. 그래프(Graph)란?

그래프는 객체들이 쌍으로 연관되어 집합을 이루는 구조를 의미한다. 말이 어렵다면, 그래프 구조의 일종인 트리(Tree) 구조를 생각하면 된다.
트리(Tree) 구조 또한 노드(Node)들이 부모/자식 관계로 연결되어 있었다. 노드(Node)가 객체이며 그 관계를 연관성으로 하나의 전체 구조를 이루었다고 보면 된다. 트리(Tree) 처럼, 그래프 또한 내부적으로 부분 그래프(Sub Graphs)로 이루어진다.

2. 그래프와 트리의 차이

구분	그래프(Graph)	트리(Tree)
정의	객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조	그래프의 한 종류 방향성이 없으며 순환하지 않음
방향성	무방향 혹은 유방향으로 가능	무방향 그래프
순환성	순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능	순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph)
루트	루트의 개념이 있거나 없을 수 있음	하나의 루트 노드 존재
모델	네트워크 모델	계층 모델
순회	넓이 우선 탐색(BFS) 깊이 우선 탐색(DFS)	전위(Pre) / 중위(In) / 후위(Post) 순회 방식
간선 수	그래프에 따라 다르며 없을 수도 있음	N개의 노드(Node)라면 N-1개

3. 그래프의 구성요소

정점(Node, Vertex) - 객체, 위치의 개념
간선(Edge) - 정점 간의 관계, 연결선(Link, Branch)
인접 정점(Adjacent vertex) - 1개의 간선으로 직접 연결된 정점
정점 차수(Degree) - 하나의 정점에 인접해 있는 간선의 개수
진입 차수(In-Degree) - 방향성이 있는 그래프에서 외부에서 오는 간선의 수(내차수라고도 부른다)
진출 차수(Out-Degree) - 방향성이 있는 그래프에서 외부로 향하는 간선의 수(외차수라고도 부른다)
경로 길이(Path Length) - 정점에서 정점 간 경로 구성 시 사용된 간선의 수
단순 경로(Simple Path) - 구성된 경로 중에서 반복되는 정점이 없는 경우
사이클(Cycle) - 경로 중에서 시작 / 종료의 정점이 동일하여 내부적으로 순환이 발생하는 경우

* 다중 간선(Multi Edge)

A → B로 가는 경로가 2가지 이상인 경우를 의미한다.
아래와 같이 빨간 경로가 있는 경우 다중 간선(Multi Edge)라고 부른다. 이 경우에는 두 간선은 서로 다른 간선이다.

* 차수(Degree)

무방향 그래프에서는 단순히 차수(Degree)를 계산한다. 즉, 특정 정점에 연결된 간선의 개수를 차수라고 본다.
아래의 그림에서 2번 정점은 연결된 간선이 3개 이므로 차수가 3이다.

유방향 그래프에서는 내차수(In-Degree) / 외차수(Out-Degree)를 계산한다. 내차수는 현재 정점 방향으로 이어지는 간선의 개수이며, 외차수는 현재 정점에서 다른 정점 방향으로 이어지는 간선의 개수이다.
즉, 아래의 그림에서 4번 노드는 내차수가 2이고 외차수가 1임을 알 수 있다.

4. 그래프의 종류

1. 무방향 그래프(Undirected Graph)

노드(Node) 혹은 객체가 상호 연결만 되어 있는 형태라고 볼 수 있다. 그 연결을 통해 상호 양방향으로 이동할 수 있다.
트리(Tree) 구조와 같이 부모 / 자식 노드(Node) 간에 상호 연결이 되어 있고 어느 방향으로든 서로를 참조할 수 있는 형태이다.
A→B를 G(A, B) B→A를 G(B, A)라고 표현한다면 그 2가지는 동일하다고 보면 된다.
아래의 그림과 같은 형태를 보면 각 노드들이 상호 연결되어 있으나 특정 방향성은 가지지 않는 것을 알 수 있다.
아래와 같은 무방향 그래프는 실제로는 A → B, B → A를 모두 표현하여 유방향 그래프 처럼 보고 문제를 해결한다.

2. 유방향 그래프(Directed Graph)

노드(Node) 혹은 객체가 연결되어 있으나 특정 방향으로만 이동할 수 있는 경우를 의미한다.
예를 들어, A→B로는 이동이 가능하지만 B→A로는 이동이 불가한 경우가 있을 수 있으며 이러한 형태를 표현 시 적합하다.
아래의 그림을 보면 하나의 노드에서 다른 노드로 방향성이 제시되어 있는 것을 확인할 수 있다.

3. 가중치 그래프(Weighted Graph)

노드(Node) 혹은 객체의 연결에 가중치가 부여된 형태의 경우를 의미하며 '네트워크' 라고도 부른다.
단순 방향 그래프는 G(A, B) 및 G(B, C)가 1이라고 한다면 가중치 그래프는 G(A, B)와 G(B, C)가 다른 값을 가질 수 있다.
예를 들면, 노드(Node) 간 이동 시에 비용이 드는 경우를 생각해볼 수 있다.
가중치 그래프는 방향성을 갖거나 가지지 않을 수 있다.
아래 그림을 보면 각각의 노드(Node) 끼리 연결된 내역에 가중치가 부여되어 있음을 알 수 있으며 각 경로의 비용이라고 본다면 가장 효율적인 비용으로 이동하는 방법을 계산해볼 수도 있다.

4. 연결 그래프(Connected Graph)

무방향 그래프에 있는 모든 정점의 쌍에 대해서 항상 경로가 존재하는 경우를 의미한다.
트리(Tree) 구조 또한 그렇다고 볼 수 있다. 모든 정점들이 계층에 따라 연결되어 있다.
위의 그림들처럼 모든 노드(Node)에 대해 연결되지 않은 것이 없는 경우 모두를 포괄한다고 볼 수 있다.

5. 비연결 그래프(Disconnected Graph)

무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
아래의 그림과 같이 1번 노드(Node)와 4번 노드(Node) 간에는 연결이 되어 있지 않다.

6. 순환 그래프(Cycle Graph)

정점 간의 단순 경로에서 시작 정점 / 종료 정점이 동일하여 경로에 순환이 발생할 수 있는 경우
단순 경로(Simple Path)는 경로 중 반복되는 정점이 없는 경우를 의미
아래의 그림과 같이 3→5→4→3 또는 3→2→3 또는 1→1(이 경우는 Loop 라고도 함) 과 같이 경로에 순환이 발생하는 경우를 의미한다.
이러한 경우, 코드로 처리 시, Cycle Detection(순환 감지) 기능을 넣어야 한다.