그래프(Graph)
정의: 정점(Vertex)과 간선(Edge)들의 유한 집합으로, 정점들 사이의 연결 관계를 표현하는 자료구조. N:N 관계를 표현하는데 용이하며 100점짜리 자료구조임.
핵심 요소
구성 요소 | 설명 |
정점 (Vertex/Node) | 데이터가 저장되는 위치 |
간선 (Edge) | 정점 간의 연결을 나타내는 선 |
인접 (Adjacent) | 두 정점이 간선으로 직접 연결된 상태 |
차수 (Degree) | 하나의 정점에 연결된 간선의 수 |
그래프 탐색
•
너비 우선 탐색 - BFS
•
깊이 우선 탐색 - DFS
너비 우선 탐색 - BFS
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
(입력예시)
1
7 6
1 7
1 2
2 4
2 5
1 3
3 6
6 7
(그래프 예시)
1
/ \
2 3
/ \ \
4 5 6
|
7
*/
public class bfs_Samplecode {
static int T, N, M, A, B;
// 정점을 담을 큐 (row, col, cost)
static Queue<Integer> que = new LinkedList<Integer>();
// 출발지 S, 목적지 E
static int S, E;
// 인접 행렬
static int MAT[][] = new int[101][101];
static int visited[] = new int[101];
// 방문 횟수
static int cnt = 0;
public static void bfs() {
// 1. 시작점을 큐에 넣는다.
que.add(S);
visited[S] = 1;
cnt++;
// 5. 큐가 비어있는지 않다면 반복
while(!que.isEmpty()) {
// 2. 큐에서 한 점을 꺼내서 기준점으로 삼는다.
System.out.println("now : " + que.peek());
int now = que.poll();
// 3. 기준점이 목적지이면 탐색을 종료한다.
if( now == E )
break;
// 4. 그렇지 않은 경우 기준점에서 갈 수 있는 다른 정점들을 큐에 넣는다.
else {
for (int i = 1; i <= N; i++) {
// 기존에 방문하지 않고
// 현재 정점과 연결된 점을 탐색
if( visited[i] == 0 && MAT[now][i] == 1 ) {
visited[i] = 1;
cnt++;
// 해당 지점을 큐에 넣는다.
que.add(i);
System.out.println(i + "번 정점 방문");
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
// N : 정점의 수
// M : 간선의 수
N = sc.nextInt();
M = sc.nextInt();
// S : 출발지
// E : 목적지
S = sc.nextInt();
E = sc.nextInt();
// visited배열 초기화
for (int i = 1; i <= N; i++) {
visited[i] = 0;
}
// 인접배열 초기화
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
MAT[i][j] = 0;
}
}
// 인접배열 정점간의 관계 지정
for (int i = 1; i <= M; i++) {
A = sc.nextInt();
B = sc.nextInt();
MAT[A][B] = 1;
}
// 인접배열 출력
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
System.out.print(MAT[i][j] + " ");
}
System.out.println();
}
// 그래프 탐색 - BFS(Breadth First Search)
bfs();
System.out.println(cnt + "개의 정점 방문");
}
}
}
Java
복사
깊이 우선 탐색 - DFS
import java.util.Scanner;
/*
깊이 우선 탐색(Depth First Search, DFS)
- 깊이 우선탐색은 트리나 그래프를 탐색하는 알고리즘 중 하나로,
한 정점에서 출발하여 가능한 멀리까지 탐색하는 방법이다.
- dfs는 지나온 경로를 쉽게 파악할 수 있는 장점이 있으며,
스택(Stakc) 이나 재귀함수(Recursion Func)로 구현할 수 있다.
(입력예시)
1
6 5
1 2
2 3
2 4
1 5
5 6
(그래프 예시)
1
/ \
2 5
/ \ \
3 4 6
*/
public class dfs_Samplecode {
static int T, N, M, A, B;
// i번째 정점을 방문했는지 여부를 체크할 배열
// i번째 정점을 방문(O) visited[i] = 1
// i번째 정점을 방문(x) visited[i] = 0
static int visited[] = new int[101];
// 인접 배열
static int MAT[][] = new int[101][101];
// 방문 횟수
static int cnt = 0;
// void dfs(int idx, int depth)
// - idx : 현재위치, depth : 깊이 2가지를 기본적인 인자로 가진다.
public static void dfs(int idx, int depth) {
System.out.println("depth: " + depth);
// 종료조건
if( idx == N ) {
}
// 탐색조건
else {
for (int i = 1; i <= N; i++) {
// 기존에 방문한 정점이 아니고
// 현재 정점과 연결된 정점인 경우에만 탐색
if( visited[i] == 0 && MAT[idx][i] == 1 ) {
// i번째 정점을 방문
System.out.println(i + "번 정점 방문 " );
cnt++;
visited[i] = 1;
dfs(i, depth+1);
// 탐색이 끝나면 해제
System.out.println(i + "번으로 돌아옴");
visited[i] = 0;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
// N : 정점의 수
// M : 간선의 수
N = sc.nextInt();
M = sc.nextInt();
// visisted배열 초기화
for (int i = 0; i < N; i++) {
visited[i] = 0;
}
// 인접배열 초기화
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
MAT[i][j] = 0;
}
}
// 인접배열 정점간의 관계 지정
for (int i = 1; i <= M; i++) {
A = sc.nextInt();
B = sc.nextInt();
MAT[A][B] = 1;
}
// 인접배열 출력
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
System.out.print(MAT[i][j] + " ");
}
System.out.println();
}
// 그래프 탐색 - DFS(Depth First Search)
dfs(1, 1);
// root(+1) 포함 정점 방문 수
System.out.println(cnt+1 + "개의 정점 방문");
}
}
}
Java
복사
Java로 구현한 기본 그래프 예시
public class Graph {
private int V; // 정점의 개수
private LinkedList<Integer>[] adj; // 인접 리스트
// 그래프 생성자
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 간선 추가
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v); // 무방향 그래프의 경우
}
}
Java
복사
Java Collections를 활용한 그래프 구현
import java.util.*;
public class GraphWithCollections {
private Map<Integer, List<Integer>> adjacencyList;
public GraphWithCollections() {
adjacencyList = new HashMap<>();
}
// 정점 추가
public void addVertex(int vertex) {
adjacencyList.putIfAbsent(vertex, new ArrayList<>());
}
// 간선 추가
public void addEdge(int source, int destination) {
// 정점이 없다면 추가
adjacencyList.putIfAbsent(source, new ArrayList<>());
adjacencyList.putIfAbsent(destination, new ArrayList<>());
// 양방향 간선 추가
adjacencyList.get(source).add(destination);
adjacencyList.get(destination).add(source);
}
// 인접 정점 가져오기
public List<Integer> getAdjVertices(int vertex) {
return adjacencyList.get(vertex);
}
}
Java
복사