그래프(Graph)

그래프(Graph)

그래프(Graph)는 노드/정점(Node, Vertex)와 간선(Edge)로 구성된 비선형 자료구조를 의미한다.

트리와 다르게 정점과 정점 사이의 간선이 여러 개 있을 수 있고, 순환(Cycle)이나 자체 순환(Self-Loop)도 가능하다.

그래프는 간선에 가중치(Weight)가 부여되는 경우가 많다.

트리는 그래프의 부분 집합이다.

---

그래프와 트리 차이

---

용어

• 정점(vertex): 위치라는 개념. (node 라고도 부름)
• 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
• 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
• 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
• 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

---

종류

그래프는 다음과 같은 기준에 따라 종류가 달라진다.

크게 방향성, 가중치 유무, 연결성, 순환 유무, 완전성으로 나뉜다.

1. 방향성 : 정점과 정점 사이에 방향성이 있음. ex) A → B로 갈 수 있으나, B → A는 갈 수 없음

2. 가중치 유무 : 간선에 가중치가 있는 경우

3. 연결성 : 무방향 그래프에서 모든 노드쌍에 대해 항상 경로가 존재하는 경우

4. 순환 유무 : 경로의 시작점과 도착점이 동일한 경우

5. 완전성 : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 경우

기 준	有	無
방향성	방향 그래프(Directed Graph)	무방향 그래프(Undirected Graph)
가중치 유무	가중치 그래프(Weighted Graph)	-
연결성	연결 그래프(Connected Graph)	비연결 그래프(Disconnected Graph)
순환 유무	순환 그래프(Cycle Graph)	비순환 그래프(Acyclic Graph)
완전성	완전 그래프(Complete Graph)	-

그래프 종류는 이 중 반드시 하나로 정해지는 것은 아니다.

예를 들어 방향성이 없고, 가중치가 있으며, 연결되어 있는 그래프를 무방향 가중치 연결 그래프 Directed Weighted Connected Graph라고 합쳐 부른다.

---

구현

그래프를 구현하는 방법은 크게 2가지가 존재한다.

1. 인접 행렬(Adjacency Matrix)

인집 행렬은 정점이 N개 일때, N x N 행렬을 통해 두 정점의 간선 및 가중치를 표시하는 방법이다.

가중치가 없다면 타입을 Boolean으로 지정해도 된다.

예를 들어, i → j 로 가는 간선의 가중치가 3 이라면 graph[i][j] = 3 으로 표현된다.

 

인접 행렬 방식의 경우 간선의 수와 무관하게 $N^2$개의 메모리 공간이 필요하다.

무방향 그래프의 경우 graph[i][i]를 기준으로 대칭인 대칭 행렬(Symmetric Matrix)이다.

 

경로를 찾기 위해서 인접 정점을 확인해야 하는데, 인접 행렬의 경우 모든 정점을 확인해야한다는 단점이 있다.

 

2. 인접 리스트(Adjacency Matrix)

위와 같은 인접 행렬의 단점으로 그래프를 구현할 때에는 주로 인접 리스트를 사용한다.

각 정점은 본인과 인접한 정점을 동적인 리스트 구조로 가지고 있어 굳이 다른 정점을 확인할 필요가 없다.

 

(b)는 인접 리스트, (c)는 인접 행렬로 각각 구현 시 자료 저장 형태

class Node{
    public int nodeNum;
    public int weight;
    public LinkedList<Node> adj;
}

class Graph{
    public Node[] graph;
}

무방향 그래프는 A ↔ B 간선이 있다면, A → B 와 B → A로 두 번 저장해야한다.

따라서 정점이 N개, 간선이 E개인 무방향 그래프의 경우 N개의 배열과 N개의 리스트, 2E개의 노드가 필요하다.

구현 방법	장점	단점
인접 리스트	메모리 공간을 적게 사용. 그래프에 존재하는 모든 간선의 수를 $O(N+E)$ 안에 알 수 있음.	인접 정점을 조회할 때, 간선 수가 많아지면 정점 i의 리스트를 조회하기 위해 정점의 차수 만큼 시간 소요
인접 행렬	두 정점을 연결하는 간선을 $O(1)$안에 알 수 있음.	인접한 노드를 찾기 위해서는 모든 노드를 순회해야 함. 그래프에 존재하는 모든 간선의 수를 $O(N^2)$ 안에 알 수 있음.

---

탐색

그래프에서 탐색은 크게 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search)로 수행한다.

1. 깊이 우선 탐색(DFS, Depth-First Search)

깊이 우선 탐색은 갈 수 있는 만큼 최대한 깊이 들어가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식이다.

재귀호출이나 스택을 사용하여 구현한다.

일반적으로, 모든 노드를 방문하고자 하는 경우에 깊이 우선 탐색을 수행한다.

2. 너비 우선 탐색(BFS, Breadth-First Search)

너비 우선 탐색은 시작 정점에서 인접한 정점을 모두 방문하고, 그 인접한 정점 중 다시 인접한 정점을 우선적으로 탐색하는 방식이다.

큐를 사용하여 지금 위치에서 갈 수 있는 모든 노드를 모두 큐에 넣는 형식으로 구현한다.

일반적으로, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 수행한다.

---

Ref.

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

https://coding-factory.tistory.com/610

https://velog.io/@vagabondms/DFS-vs-BFS