1. 그래프 표현 방식
1) 인접행렬
- 노드의 개수가 N일 때, N*N 행렬(N*N의 2차원 배열)을 만들어 x행과 y행이 연결 되어 있으면 1, 되어 있지 않으면 0을 행렬 값으로 가지도록 표현
- 무방향 그래프
- 모든 간선이 양 방향으로 이동이 가능한 것이라 간주
- x번째 노드와 y번째 노드가 연결되어 있고 그 배열을 adj라 하자 => adj[x][y] = adj[y][x] = 1
- 행렬은 왼쪽 대각을 기준으로 양쪽이 대칭이 됨 => 대각을 기준으로 양쪽을 모두 사용하지 않고 행 <열인 경우 또는 열> 행인 경우 중 하나만 사용해도 됨
- 가중 그래프
- 행렬의 값을 가중치로 저장
- 가중치>=0 이라면 간선이 없는 곳의 값을 -1 로 하
- 특징
- 구현 간단
- 특정 두 노드가 인접한지 상수시간에 파악 가능
- 메모리 낭비 심함(정점에 비해 간선이 적은 경우)
- 특정 노드와 연결된 정점들을 탐색하고자 한다면, 모든 노드를 돌아야 함
- 구현 코드
public class 그래프_01_인접행렬 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt(); // 정점의 개수를 입력을 받는다. (6 이다. 시작정점이 0번인지 / 1번인지)
int E = sc.nextInt(); // 간선의 수가 입력 된다.
int[][] adjArr = new int[V + 1][V + 1];
// 간선을 입력을 받자.
for (int i = 0; i < E; i++) {
int st = sc.nextInt();
int ed = sc.nextInt();
adjArr[st][ed] = 1;
//무향그래프일때 아래도 같이 작성을 해준다.
adjArr[ed][st] = 1;
adjArr[st][ed] = adjArr[ed][st] = 1; //한줄적기 가넝
}
}
}
2) 인접 리스트
- 각 노드에 연결된 간선을 리스트로 저장
- 즉, 각 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장
- 배열과 달리 각 노드 다음에 그 다음 노드를 연결(chaining 필요)
- 예
- 0에 연결된 노드가 1,3, 4 라면 LinkedList인 adjList(인접리스트)의 0번 index에는 [1,3,4]를 노드로 가지는 연결리스트가 연결됨
- 무향 그래프
- 연결리스트의 노드 수 = 간선의 수 *2 (양방향 모드 저장되므로)
- 각 정점의 노드 수 = 정점의 차수
- 유향 그래프
- 연결리스트의 노드 수 = 간선의 수
- 각 정점의 노드 수 = 그 정점에서 진출해 나가는 차수
- 특징
- 메모리 효율적으로 사용 가능
- 특정 정점들끼리 인접한지를 확인할 시, 오래 걸림
- 구현 코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ConcurrentHashMap;
public class 그래프_02_인접리스트 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt(); // 정점의 개수를 입력을 받는다. (6 이다. 시작정점이 0번인지 / 1번인지)
int E = sc.nextInt(); // 간선의 수가 입력 된다.
List<Integer>[] adjList = new ArrayList[V+1];
for(int i = 0 ; i<V+1; i++) {
adjList[i] = new ArrayList<>();
}
// 간선을 입력을 받자.
for (int i = 0; i < E; i++) {
int st = sc.nextInt();
int ed = sc.nextInt();
adjList[st].add(ed);
//무향그래프일때 아래도 같이 작성을 해준다.
adjList[ed].add(st);
}
for(int i = 0 ; i<V+1; i++) {
Collections.sort(adjList[i]);
}
}
}
3) 간선 리스트
- 정점과 정점의 연결 정보인 간선을 배열에 저장
- 간선을 표현하는 두 정점의 정보를 배열 혹은 객체로 저장할 수 있음
- 무방향 그래프
- x, y를 바꿔서 두번 저장하거나 간선 당 한번씩만 저장하고 처리할 때 고려해서 처리
- 가중치 그래프
- 가중치도 저장해야하므로 정점의 정보를 저장하는 방법이 배열이라면 가중치를 저장할 수 있도록 크기를 1 늘리거나, 객체라면 클래스 생성 시, 가중치 값 필드를 생성하기
- 특징
- 구현 간단
- 모든 간선 탐색 시 유리
- 특정 노드가 이웃한지 알아보기 위해서는 모든 간선 탐색 필요
- 특정 노드에 연결된 간선을 알아보기 위해서는 모든 간선 탐색 필
- 구현 코드
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class 그래프_03_간선배열 {
static class Edge {
int st, ed;
public Edge(int st, int ed) {
this.st = st;
this.ed = ed;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt(); // 정점의 개수를 입력을 받는다. (6 이다. 시작정점이 0번인지 / 1번인지)
int E = sc.nextInt(); // 간선의 수가 입력 된다.
// 2가지
Edge[] edges = new Edge[E];
List<Edge> edges2 = new ArrayList<>();
int[][] edges3 = new int[E][2]; //[i][0] : 시작정점, [i][1] : 끝정점
for (int i = 0; i < E; i++) {
int st = sc.nextInt();
int ed = sc.nextInt();
edges[i] = new Edge(st, ed);
}
}
}
2. 그래프 표현방식 비교
V : 노드의 개수
E : 간선의 개수
1) 간선리스트 vs 인접행렬 vs 인접 리스트
| 간선 리스트 | 인접 행렬 | 인접 리스트 | |
| 중심 | 간선 | 노드 | 노드 |
| 시간복잡도 | - | 느림 | 빠름 |
| 공간복잡도 | O(E) | O(V^2) | O(E) |
| 구조 | [] | adf[시작노드][종료노드] | adj[시작노드] |
| 입력 | (시작노드 ,도착노드, 가중치) | 가중치 | (도착노드, 가중치) |
| 알고리즘 | 벨만-포드 MST 크루스칼 |
플로이드-워셜 | 다익스트라 |
2) 인접행렬 vs 인접 리스트
| 인접 행렬 | 인접 리스트 | |
| 간선(x,y) 검색 | O(1) | O(degree(y)) |
| 정점의 차수 계산(v) | O(V) | O(degree(v)) |
| 전체 노드 탐색 | O(V^2) | O(E) |
| 메모리 | V^2 | V+E |
| 구현 난이도 | 비교적 쉬움 | 비교적 어려움 |
3. DFS
- 루트 노드(시작정점, 출발위치)에서 출발하여 한 방향으로 갈 수 있는 경로의 끝까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드로 탐색을 반복하여 결국 모든 노드를 방문하는 순회방법
- 백트래킹과의 차이점 : DFS는 해당 경로가 도중해 해가 되지 않는지 판단하지 않고 끝까지 가본 후 되돌아오는 반면, 백트래킹은 도중에 해가 되지 않는다면 끝까지 탐색하지 않고 되돌아옴.(가지치기 유무의 차이)
- 구현
- 탐색방법(Stack)
- 루트노드 stack push
- stack이 빌 때까지 반복
- stack에서 pop
- pop한 노드의 curr의 모든 자식을 push
- 방식
- 재귀 활용
- 현재 노드 방문(v)
- v의 자식 노드 w를 차례로 재귀 호출
- 빠짐없이 탐색하는 것이 Point. 순서는 중요치 않음
- 재귀 활용
- 구현코드
public class 그래프01_DFS {
static int N = 7;
//인접행렬 방식
static int[][] adj = {
{ 0, 1, 1, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 0, 0 } };
static boolean[] visited = new boolean[N];
public static void main(String[] args) {
DFS(0);
}
static void DFS(int v) {
//v에 대한 방문처리를 하겠다.
visited[v] = true;
System.out.println(v+1);
//나와 연결되어 있으면서(간선이 존재하면서) 아직 방문하지 않은 정점을 재귀 호출
for(int i=0; i<N; i++) {
if(!visited[i] && adj[v][i]==1) {
DFS(i);
}
}
}
}4. BFS
- 탐색 루트 노드(시작 정점, 출발 위치)의 자식노드들을 모두 차례로 방문한 후에 방문했던 자식 노드(인접노드)들을 시작점으로 하여 다시 해당 자식노드들을 차례로 방문하는 방식
- 최단 길이를 구하는 문제에 많이 활용. 인접한 노드들을 차례로 방문하므로, 방문횟수(RANK)를 카운트 가능하고, 가장 빠른 해를 찾는 순간 탐색을 멈추기 때문에 그 때의 RANK값이 최단길이가 됨.
- 구현
- 큐(Queue)를 사용 : 자식노드들에 대한 탐색을 모두 완료한 후, 그 자식의 자식 노드들에 대해서 탐색해야 하므로 선입선출 방식읠 자료구조가 필요하기 때문
- 루트노드를 큐에 삽입
- 큐가 공백이 될 때까지 반복 수행
- 큐에서 원소 v 꺼내기
- v 방문처리
- v의 자식 노드를 다시 큐에 삽입
- 구현코드
public class 그래프02_BFS {\
static int N = 7;
static int[][] adj = {
{ 0, 1, 1, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 0, 0 } };
static boolean[] visited = new boolean[N];
static Queue<Integer> queue = new LinkedList<>();
public static void main(String[] args) {
BFS(0);
}
static void BFS(int v) {
//시작정점을 큐에 넣는다.
queue.add(v);
visited[v] = true; //방문처리
//큐가 공백이 될 때까지 반복문 수행
//큐가 공백이 아니라면 반복문 수행
while(!queue.isEmpty()) {
//정점을 하나 꺼내
int curr = queue.poll();
System.out.print(curr + "->");
//나와 연결되어 있으면서 방문하지 않은 친구들을 Q에 넣는다.
for(int i=0; i<adj.length; i++) {
if(!visited[i] && adj[curr][i]==1) {
queue.add(i);
visited[i] = true;
}
}
}
}
}
5. 관련문제 정리
1)
'Learning-log -CS > Data Structure & Algorithm' 카테고리의 다른 글
| (자료구조 & 알고리즘 정리) 최소 비용 신장 트리, Kruskal, Prim (2023.06.25) (0) | 2023.06.25 |
|---|---|
| (자료구조 & 알고리즘 정리) 서로소집합, 유니온파인드 (2023.06.24) (0) | 2023.06.24 |
| (자료구조 & 알고리즘 정리) 분할정복 (2023.06.15) (0) | 2023.06.15 |
| (자료구조 & 알고리즘 정리) 완전 탐색, 백트래킹 (2023.06.14) (0) | 2023.06.14 |
| (자료구조 & 알고리즘 정리) 트리(Tree) (2023.06.13) (0) | 2023.06.13 |