#그래프
- 그래프의 정의
▪ 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조
▪ 컴퓨터에서 표현하는 그래프는 XY축을 기준으로 한 그래프와 달리 복잡한 네트워크망과 같은 모습이다.
- 그래프의 구조
- 직접 관계에 있는 두 점은 사이에 이어진 선이 있다.
- 간접 관계이 있는 두 점은 다른 점과 선을 거쳐 이어진다.
- 하나의 점을 정점(vertex), 하나의 선은 간선(edge)라고 한다.
- 그래프의 표현 방식
- 인접 행렬
직접 관계에 있는 두 정점을 인접한다고 말하는데, 인접행렬은 서로 다른 정점들이 인접한 상태를 2차원 배열의 형태에 표시한다.
위 그래프를 인접행렬로 표현한다면 다음과 같다.
int[][] arr = new int[][] {
{0, 1, 0},
{0, 0, 1},
{1, 1, 0}
};
2. 인접 리스트
인접 리스트는 각 정점이 어떤 정잠과 인접하는지를 리스트의 형태로 표현한다.
각 정점마다 하나의 리스트를 가지며, 이 리스트는 자신과 인접한 다른 정점을 담는다.
인접 리스트는 인접 행렬보다 메모리를 효율적으로 사용한다. (인접 행렬은 연결 가능한 모든 경우의 수를 저장)
위의 그래프를 인접 리스트로 표시하면, 다음과 같다.
// A, B, C를 각각의 인덱스로 표시. A = 0, B = 1, C = 2
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
graph.add(new ArrayList<>(Arrays.asList(1, null)));
graph.add(new ArrayList<>(Arrays.asList(2, null)));
graph.add(new ArrayList<>(Arrays.asList(0, 1, null)));
graph.get(0) == [1, null] == 0 -> 1 -> null
graph.get(1) == [2, null] == 1 -> 2 -> null
graph.get(2) == [0, 1, null] == 2 -> 1 -> 0 -> null
- 그래프의 용어
- 정점 (vertex): 데이터가 저장되는 그래프의 기본 원소. 노드(node)라고도 함.
- 간선 (edge): 정점 간의 관계를 나타냄
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점. (직접 관계에 있는 두 정점)
- 가중치 그래프 (weighted Graph): 연결의 강도(두 정점 사이의 추가적인 정보)가 얼마나 되는지 적혀 있는 그래프
- 비가중치 그래프 (inweighted Graph): 연결의 강도가 적혀 있지 않은 그래프
- 무향(부방향) 그래프 (undirected graph): 정점간의 관계에서 연결 가능한 방향이 적혀 있지 않은 무향 그래프. 무향 그래프에서는 간선이 있는 두 정점은 서로 왕복이 가능하다. 반대로 단뱡향 그래프는 간선이 있더라도 A정점에서 B정점으로 갈 수 있더라도 B정점에서 A정점으로는 이동 불가능한 상황을 단방향인 간선으로 표현한다.
- 진입차수 (in-degreee) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)과 진출(나가는 간선)의 개수를 나타냄
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있을 때 두 정점은 인접한 정점이다.
- 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에 진입하는 경우에 자기 루프를 가졌다고 말함. 다른 정점을 거치지 않는다.
- 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있을 때, 사이클이 있다고 표현함.
- 그래프를 코드로 구현하기
- 인접 행렬로 구현하기
import java.util.*; public class GraphInArray { private int[][] graph; public void setGraph(int size) { graph = new int[size][size]; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { graph[i][j] = 0; } } } public int[][] getGraph() { return graph; } public void addEdge(int from, int to) { if (from >= graph.length || to >= graph.lenth) return; // 그래프 범위를 넘어가는 인수 전달 시 작동 X graph[from][to] = 1; } public boolean hasEdge(int from, to) { if (from >= graph.length || to >= graph.lenth) return false; else if (graph[from][to] == 1) return true; else return false; } public void removeEdge(int form, int to) { from >= graph.length || to >= graph.lenth) return; graph[from][to] = 0; } }
- 인접 그래프로 구현하기
import java.util.*; public class GraphInArrayList { private ArrayList<ArrayList<Integer>> graph; public Solution() { graph = new ArrayList<>(); } public void setGraph(int size){ for (int i = 0; i < size; i++) { graph.add(new ArrayList<Integer>()); } } public ArrayList<ArrayList<Integer>> getGraph() { return graph; } public void addEdge(int from, Integer to) { // from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 추가 X if (from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return; graph.get(from).add(to); // from의 인접 리스트에 to를 추가 graph.get(to).add(from); // to의 인접 리스트에 from를 추가 } public boolean hasEdge(int from, int to) { if (from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return false; else return graph.get(from).contains(to); // ArrayList 메서드 contains 사용. } public void removeEdge(int from, int to) { if (from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return; if (graph.get(from).contains(to)) { // from의 인접리스트가 to를 contain하는 경우 간선이 존재 graph.get(from).remove((Integer) to); // 간선 삭제 } if (graph.get(to).contains(from)) { // to의 인접리스트가 from을 contain하는 경우 간선이 존재 graph.get(to).remove((Integer) from); // 간선 삭제 } } }
'개발지 > Today I learn' 카테고리의 다른 글
[1204] 자바 - 시간복잡도(Time Complexity) (2) | 2023.12.04 |
---|---|
[1128] 자바 - Tree traversal(트리 순회) (1) | 2023.11.28 |
[1127] 자바 - Graph Traversal(그래프 탐색) (4) | 2023.11.27 |
[1122] 자바 - 자료구조 (Tree) (1) | 2023.11.23 |
[1122] 자바 - 자료구조 (Queue) (0) | 2023.11.22 |