컴포넌트(Component): 그래프에서 연결된 정점들의 집합을 의미한다. 무향 그래프에서 컴포넌트는 연결 요소(Connected Component)라고도 한다.
이웃(Neighbor): 한 정점과 인접한 정점이다.
강결합(Strongly Connected): 유향 그래프에서 모든 정점 쌍이 서로 도달 가능한 상태이다.
약결합(Weakly Connected): 유향 그래프에서 무향 그래프와 같이 모든 정점 쌍이 서로 도달 가능한 상태이다.
위상 정렬(Topological Sorting): 유향 그래프에서 모든 정점을 방향성에 따라 일렬로 나열하는 것을 의미한다.
사이클이 존재하지 않아야 가능하다.
완전 그래프(Complete Graph) : 모든 정점이 서로 연결되어 있는 그래프를 의미한다.
정점이 n개일 때 간선의 수 = n(n-1)/2* 이다.
Directed Graph vs Undirected Graph
방향성에 따라 방향 그래프와 무방향 그래프로 나뉜다.
Weighted Graph vs Unweighted Graph
간선에 비용/가중치 할당 유무에 따라 가중치 그래프와 비가중치 그래프로 나뉜다.
스패닝 트리(Spanning Tree)
위 그림처럼 그래프의 모든 정점을 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
신장 트리라고도 하며, 그래프의 최소 연결 부분 그래프이다.
n개의 정점을 (n-1)개의 간선으로 연결한 상태이다.
그래프의 구현 방법
1. 인접 그래프(Adjacency Graph = Adjacent Matrix) 활용
그래프의 정점과 간선을 2차원 배열로 나타내는 방법이다.
장점
그래프의 연결 관계를 2차원 배열로 표현하기 때문에 연결 관계를 빠르게 확인할 수 있다. O(1)의 시간복잡도로 확인 가능하다.
각 정점의 차수를 쉽게 계산할 수 있다.
단점
정점의 개수가 많아지면 차지하는 메모리 공간이 크게 증가한다. (2차원 배열)
특정 정점과 연결된 모든 노드를 찾으려면 해당 배열을 전부 탐색해야 하므로 O(N)의 시간복잡도를 갖는다.
인접 그래프 생성
int[][] graph;
public AdjacencyMatrix(int size) {
graph = new int[size][size];
}
정점 연결
public void addEdge(int from, int to) {
graph[from][to] = 1;
graph[to][from] = 1; // 무향 그래프인 경우 반대 방향도 추가
}
정점 삭제
public void removeEdge(int from, int to) {
graph[from][to] = 0;
graph[to][from] = 0; // 무향 그래프인 경우 반대 방향도 제거
}
인접 그래프 출력
public void printGraph() {
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[i].length; j++) {
System.out.print(graph[i][j] + " ");
}
System.out.println();
}
}
2. 인접 리스트(Adjacency List) 활용
그래프의 각 정점에 대해 인접한 정점들을 리스트로 나타내는 방법이다.
장점
정점의 연결 정보만을 저장하기 때문에, 정점의 개수가 많아질 경우 인접 그래프 방식보다 더 적은 메모리 공간을 차지한다.
특정 정점과 연결된 정점들을 찾는 경우 시간복잡도가 O(차수)로 줄어든다.
그래프 구조가 유동적으로 변경되는 상황이라면, 수정이 훨씬 빠르다.
단점
각 노드간 연결 상태를 확인하는데 O(N)의 시간복잡도를 갖는다.
인접 리스트 생성
Map<Integer, List<Integer>> graph;
public AdjacencyList() {
graph = new HashMap<>();
}
정점 연결
public void addEdge(int from, int to) {
//새로 추가되는 정점일 경우
if (!graph.containsKey(from)) {
graph.put(from, new ArrayList<>());
}
//from 정점과 to 정점을 연결
graph.get(from).add(to);
//to 정점이 없는 경우 새로 추가
if (!graph.containsKey(to)) {
graph.put(to, new ArrayList<>());
}
graph.get(to).add(from); // 무향 그래프인 경우 반대 방향도 추가
}
정점 삭제
public void removeEdge(int from, int to) {
if (graph.containsKey(from)) {
graph.get(from).remove(Integer.valueOf(to));
}
if (graph.containsKey(to)) {
graph.get(to).remove(Integer.valueOf(from)); // 무향 그래프인 경우 반대 방향도 제거
}
}
인접 리스트 출력
public void printGraph() {
for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
System.out.print(entry.getKey() + ": ");
for (int v : entry.getValue()) {
System.out.print(v + " ");
}
System.out.println();
}
}
