dfs(깊이우선탐색), bfs(너비우선탐색), dijkstra(최단거리 탐색, 다익스트라)
그래프(또는 네트워크) 탐색 알고리즘
import javafx.util.Pair;
import java.util.*;
public class MyGraph {
/**
* DFS 인접리스트 : 깊이우선탐색
*
* @param nodeList : 각 노드에 연결된 노드 리스트를 갖는 배열
* @param visited : 방문여부 확인을 위한 배열
* @param node : 방문할 노드
*/
public static void dfs(ArrayList<Integer>[] nodeList, boolean[] visited, int node) {
if (visited[node]) return; // 방문한 노드인 경우 바로 종료
visited[node] = true; // 방문한 노드로 표기
// 여기에 필요한 결과값을 리턴하도록 코딩하면 됨
System.out.print(node + " "); // 방문한 노드 화면출력
for (int nextNode : nodeList[node]) { // 노드에 연결된 모든 노드를 방문한다.
dfs(nodeList, visited, nextNode);
}
}
/**
* DFS 인접행렬 : 깊이우선탐색
*
* @param nodeArray : 각 노드를 행/렬로 하고, 연결된 노드는 1로 표기하는 2차원 배열
* @param visited : 방문여부 확인을 위한 배열
* @param node: : 방문할 노드
*/
public static void dfs(int[][] nodeArray, boolean[] visited, int node) {
if (visited[node]) return; // 방문한 노드인 경우 바로 종료
visited[node] = true; // 방문한 노드로 표기
// 여기에 필요한 결과값을 리턴하도록 코딩하면 됨
System.out.print(node + " "); // 방문한 노드 화면출력
for (int i = 1; i < nodeArray.length; i++) {
if (nodeArray[node][i] == 1) {
dfs(nodeArray, visited, i);
}
}
}
/**
* BFS 인접리스트 : 너비우선탐색
*
* @param nodeList : 각 노드에 연결된 노드 리스트를 갖는 배열
* @param visited : 방문여부 확인을 위한 배열
* @param node : 노드
*/
public static void bfs(ArrayList<Integer>[] nodeList, boolean[] visited, int node) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(node); // 큐에 루트 노드를 넣는다.
while (!queue.isEmpty()) {
node = queue.poll(); // 큐에 들어간 노드들을 꺼낸다.
if (visited[node]) continue; // 이미 방문한 노드는 건너뜀
// 여기에 필요한 결과값을 리턴하도록 코딩하면 됨
System.out.print(node + " "); // 방문한 노드를 화면에 표기한다.
visited[node] = true; // 방문한 노드를 배열에 저장
for (int nextNode : nodeList[node]) {
queue.add(nextNode);
}
}
}
/**
* BFS 인접행렬 : 너비우선탐색
*
* @param nodeArray : 각 노드를 행/렬로 하고, 연결된 노드는 1로 표기하는 2차원 배열
* @param visited : 방문여부 확인을 위한 배열
* @param node: : 방문할 노드
*/
public static void bfs(int[][] nodeArray, boolean[] visited, int node) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(node); // 큐에 루트 노드를 넣는다.
while (!queue.isEmpty()) {
node = queue.poll(); // 큐에 들어간 노드들을 꺼낸다.
if (visited[node]) continue; // 이미 방문한 노드는 건너뜀
// 여기에 필요한 결과값을 리턴하도록 코딩하면 됨
System.out.print(node + " "); // 방문한 노드를 화면에 표기한다.
visited[node] = true; // 방문한 노드를 배열에 저장
for (int i = 1; i < nodeArray.length; i++) {
if (nodeArray[node][i] == 1) {
queue.add(i);
}
}
}
}
/**
* 다익스트라 알고리즘(인접행렬) : 시작노드로부터 각 노드로의 최단거리값을 반환한다.
*
* @param nodeArray : 각 노드를 행/렬로 하고 연결된 노드는 0 이상의 숫자로 표기하는 2차원 배열, 인덱스는 1부터 사용한다.
* 숫자가 클 수록 거리가 멀다. 0인 경우 노드는 연결되지 않음
* @param startNode : 최초 시작노드(정점)
*/
public static void dijkstra(int[][] nodeArray, int startNode) {
int n = nodeArray.length - 1; // 노드(정점)의 개수
boolean[] visited = new boolean[n + 1];
int[] distance = new int[n + 1];
Arrays.fill(distance, Integer.MAX_VALUE); // 최단거리 계산을 위해 매우 큰값(연산된 최대값보다도 훨씬 큰 값)으로 초기화
// 최초 시작 노드값 세팅(방문처리)
visited[startNode] = true;
distance[startNode] = 0;
// 최초 시작노드와 연결된 노드에 가중치(거리) 할당
for (int i = 1; i <= n; i++) {
if (nodeArray[startNode][i] != 0 && !visited[i]) {
distance[i] = nodeArray[startNode][i];
}
}
StringBuffer path = new StringBuffer("노드 이동경로 : ").append(startNode);
// visited가 모두 true가 될 때까지 반복해야 하며, 최초노드는 방문했으므로 1회를 뺀다.
for (int i = 1; i <= n - 1; i++) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
// 방문한 적이 없고, 연결된 노드 중 가장 가까운 거리에 있는 노드 구하기
for (int j = 1; j <= n; j++) {
if (!visited[j] && distance[j] != Integer.MAX_VALUE) {
if (distance[j] < min) {
min = distance[j];
minIndex = j;
}
}
}
visited[minIndex] = true; // 위에서 구해진 (가장 가까운 거리에 있는) 노드를 방문처리
path.append(", ").append(minIndex); // 노드 이동경로 확인
// 현재 노드(위에서 구해진 노드, minIndex)에 연결된 미방문 노드(k)의 기존 최단거리 distance[k]와
// 현재 노드(minIndex)에서 해당 노드(k)를 방문할 때 걸리는 거리값(distance[minIndex] + nodeArray[minIndex][k])을 비교하여
// 기존 최단거리 distance[k] 값을 더 짧은 값으로 갱신한다.
for (int k = 1; k <= n; k++) {
if (!visited[k] && nodeArray[minIndex][k] != 0) {
if (distance[k] > distance[minIndex] + nodeArray[minIndex][k]) {
distance[k] = distance[minIndex] + nodeArray[minIndex][k];
}
}
}
}
// 노드이동경로 출력
System.out.println(path);
// 결과출력
for (int i = 1; i <= n; i++) {
System.out.print(distance[i] + ", ");
}
}
/**
* 다익스트라 알고리즘(인접리스트) : 시작노드로부터 각 노드로의 최단거리값을 반환한다.
*
* @param nodeList : 각 노드에 연결된 리스트를 같는 1차원 배열, 인덱스는 1부터 사용한다. 노드간의 거리는 숫자로 표현, 숫자가 클 수록 거리가 멀다
* @param startNode : 최초 시작노드(정점)
*/
public static void dijkstra(ArrayList<Pair<Integer, Integer>>[] nodeList, int startNode) {
int n = nodeList.length - 1; // 노드(정점)의 개수
boolean[] visited = new boolean[n + 1];
int[] distance = new int[n + 1];
Arrays.fill(distance, Integer.MAX_VALUE); // 최단거리 계산을 위해 매우 큰값(연산된 최대값보다도 훨씬 큰 값)으로 초기화
// 최초 시작 노드값 세팅(방문처리)
visited[startNode] = true;
distance[startNode] = 0;
// 최초 시작노드와 연결된 노드에 가중치(거리) 할당
for (Pair<Integer, Integer> pair : nodeList[startNode]) {
int node = pair.getKey();
int weight = pair.getValue();
if (!visited[node]) {
distance[node] = weight;
}
}
StringBuffer path = new StringBuffer("노드 이동경로 : ").append(startNode);
// visited가 모두 true가 될 때까지 반복해야 하며, 최초노드는 방문했으므로 1회를 뺀다.
for (int i = 1; i <= n - 1; i++) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
// 방문한 적이 없고, 연결된 노드 중 가장 가까운 거리에 있는 노드 구하기
for (int j = 1; j <= n; j++) {
if (!visited[j] && distance[j] != Integer.MAX_VALUE) {
if (distance[j] < min) {
min = distance[j];
minIndex = j;
}
}
}
visited[minIndex] = true; // 위에서 구해진 (가장 가까운 거리에 있는) 노드를 방문처리
path.append(", ").append(minIndex); // 노드 이동경로 확인
// 현재 노드(위에서 구해진 노드, minIndex)에 연결된 미방문 노드(k)의 기존 최단거리 distance[k]와
// 현재 노드(minIndex)에서 해당 노드(k)를 방문할 때 걸리는 거리값(distance[minIndex] + nodeArray[minIndex][k])을 비교하여
// 기존 최단거리 distance[k] 값을 더 짧은 값으로 갱신한다.
for (Pair<Integer, Integer> pair : nodeList[minIndex]) {
int node = pair.getKey();
int weight = pair.getValue();
if (!visited[node]) {
if (distance[node] > distance[minIndex] + weight) {
distance[node] = distance[minIndex] + weight;
}
}
}
}
// 노드이동경로 출력
System.out.println(path);
// 결과출력
for (int i = 1; i <= n; i++) {
System.out.print(distance[i] + ", ");
}
}
/**
* 다익스트라 알고리즘(인접 해쉬맵-해쉬셋) : 시작노드로부터 각 노드로의 최단거리값을 반환한다.
*
* @param nodeMap : (문자열로 된) 노드에 연결 된 노드리스트를 해시셋으로 가진 해쉬맵 구조
* 문자열에는 중복이 없다고 가정,
* 간선(노드 간 연결)에는 가중치가 모두 1로 동일하다는 가정
* @param startNode : 시작노드
*/
public static void dijkstra(HashMap<String, HashSet<String>> nodeMap, String startNode) {
int n = nodeMap.size(); // 노드(정점)의 개수
HashMap<String, Boolean> visited = new HashMap<>(); // 노드 방문여부 검사
HashMap<String, Integer> distance = new HashMap<>(); // 노드간 연결(간선) 거리(가중치), 여기서는 모두 1로 가정한다.
for (String node : nodeMap.keySet()) {
visited.put(node, false); // 방문 여부 확인을 위해 미방문으로 모두 초기화
distance.put(node, Integer.MAX_VALUE); // 최단거리 계산을 위해 매우 큰값(연산된 최대값보다도 훨씬 큰 값)으로 초기화
}
// 연결된 노드를 찾지 못하면 건너뜀
if (visited.get(minIndex) == null) continue;
visited.put(startNode, true); // 시작 노드값 세팅(방문처리)
distance.put(startNode, 0); // 시작노드에서 시작노드까지의 거리는 0이다
// 최초 시작노드와 연결된 노드에 가중치(거리) 할당
for (String node : nodeMap.get(startNode)) {
if (!visited.get(node)) {
distance.put(node, 1); // 여기서는 가중치가 모두 동일하게 1로 세팅
}
}
StringBuffer path = new StringBuffer("노드 이동경로 : ").append(startNode);
// visited가 모두 true가 될 때까지 반복해야 하며, 최초 시작노드는 방문했으므로 1회를 뺀다.
for (int i = 1; i <= n - 1; i++) {
int min = Integer.MAX_VALUE;
String minIndex = "";
// 방문한 적이 없고, 연결된 노드 중 가장 가까운 거리에 있는 노드 구하기
for (String node : visited.keySet()) {
if (!visited.get(node) && distance.get(node) != Integer.MAX_VALUE) {
if (distance.get(node) < min) {
min = distance.get(node);
minIndex = node;
}
}
}
visited.put(minIndex, true); // 위에서 구해진 (가장 가까운 거리에 있는) 노드를 방문처리
path.append(", ").append(minIndex); // 노드 이동경로 확인
// 현재 노드(위에서 구해진 노드, minIndex)에 연결된 미방문 노드(k)의 기존 최단거리 distance[k]와
// 현재 노드(minIndex)에서 해당 노드(k)를 방문할 때 걸리는 거리값(distance[minIndex] + nodeArray[minIndex][k])을 비교하여
// 기존 최단거리 distance[k] 값을 더 짧은 값으로 갱신한다.
for (String linkedNode : nodeMap.get(minIndex)) {
if (!visited.get(linkedNode)) {
if (distance.get(linkedNode) > distance.get(minIndex) + 1) { // 모든 간선의 거리(가중치)는 1로 계산
distance.put(linkedNode, distance.get(minIndex) + 1);
}
}
}
}
// 노드이동경로 출력
System.out.println(path);
// 결과출력
for (String node : distance.keySet()) {
System.out.print(node + "(" + distance.get(node) + "), ");
}
}
}
import javafx.util.Pair;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class MyGraphTest {
MyGraph graph = new MyGraph();
// 인접행렬
int[][] array;
// 인접리스트
ArrayList<Integer>[] list;
ArrayList<Pair<Integer, Integer>>[] weightList;
// 노드명이 문자열인 해시맵 구조
HashMap<String, HashSet<String>> map = new HashMap<>();
// 노드(정점)을 방문여부를 검사하기 위한 배열
boolean[] visited;
@BeforeEach
void setUp() {
/* 아래와 같이 그래프가 주어진 경우
예) ┌ ① ┐
┌ ② ┐ ③ ┐
④ ⑤ ⑥
노드 수 : n = 6
간선 수 : m = 5
시작 노드 : ①
ㅇ 인접행렬로 표기 (각 행/열은 노드를 의미, 노드가 만나는 곳의 값이 1인 경우 간선이 연결
- 공간복잡도 : n * n = n ^ 2
① ② ③ ④ ⑤ ⑥
① 0 1 1 0 0 0
② 1 0 0 1 1 0
③ 1 0 0 0 0 1
④ 0 1 0 0 0 0
⑤ 0 1 0 0 0 0
⑥ 0 0 1 0 0 0
ㅇ 인접리스트로 표기 (각 노드에 간선으로 연결된 노드들을 리스트로 갖고 있다)
- 공간복잡도 : n + m
① : ②, ③
② : ①, ④, ⑤
③ : ①, ⑥
④ : ②
⑤ : ②
⑥ : ③
*/
// 노드의 개수
int n = 6;
// 인접행렬(각 행렬의 0번 index는 사용하지 않음)
array = new int[n + 1][n + 1];
//array[0] = new int[]{-1, -1, -1, -1, -1, -1, -1};
array[1] = new int[]{-1, 0, 1, 1, 0, 0, 0};
array[2] = new int[]{-1, 1, 0, 0, 1, 1, 0};
array[3] = new int[]{-1, 1, 0, 0, 0, 0, 1};
array[4] = new int[]{-1, 0, 1, 0, 0, 0, 0};
array[5] = new int[]{-1, 0, 1, 0, 0, 0, 0};
array[6] = new int[]{-1, 0, 0, 1, 0, 0, 0};
// 인접리스트(0번 index는 사용하지 않음)
list = new ArrayList[n + 1];
list[1] = new ArrayList<Integer>() {
{
add(2);
add(3);
}
};
list[2] = new ArrayList<Integer>() {
{
add(1);
add(4);
add(5);
}
};
list[3] = new ArrayList<Integer>() {
{
add(1);
add(6);
}
};
list[4] = new ArrayList<Integer>() {
{
add(2);
}
};
list[5] = new ArrayList<Integer>() {
{
add(2);
}
};
list[6] = new ArrayList<Integer>() {
{
add(3);
}
};
visited = new boolean[n + 1];
// 가중치가 있는 인접리스트(최단 거리 구하기에 주로 이용)
// 예) ┌ ① ┐
// ┌ ② ┐ ③ ┐
// ④ ⑤ ⑥
weightList = new ArrayList[n + 1];
// 여기에서는 가중치를 모두 1로 계산하였다. 필요시 Pair 2번째 인자값을 변경한다.
weightList[1] = new ArrayList<Pair<Integer, Integer>>() {
{
add(new Pair<>(2, 1));
add(new Pair<>(3, 1));
}
};
weightList[2] = new ArrayList<Pair<Integer, Integer>>() {
{
add(new Pair<>(1, 1));
add(new Pair<>(4, 1));
add(new Pair<>(5, 1));
}
};
weightList[3] = new ArrayList<Pair<Integer, Integer>>() {
{
add(new Pair<>(1, 1));
add(new Pair<>(6, 1));
}
};
weightList[4] = new ArrayList<Pair<Integer, Integer>>() {
{
add(new Pair<>(2, 1));
}
};
weightList[5] = new ArrayList<Pair<Integer, Integer>>() {
{
add(new Pair<>(2, 1));
}
};
weightList[6] = new ArrayList<Pair<Integer, Integer>>() {
{
add(new Pair<>(3, 1));
}
};
// 가중치가 모두 1로 동일한 해시맵 구조(최단 거리 구하기에 주로 이용)
// 예) ┌ ① ┐
// ┌ ② ┐ ③ ┐
// ④ ⑤ ⑥
map.put("1", new HashSet<String>() {
{
add("2");
add("3");
}
}
);
map.put("2", new HashSet<String>() {
{
add("1");
add("4");
add("5");
}
}
);
map.put("3", new HashSet<String>() {
{
add("1");
add("6");
}
}
);
map.put("4", new HashSet<String>() {
{
add("2");
add("3");
}
}
);
map.put("5", new HashSet<String>() {
{
add("2");
}
}
);
map.put("6", new HashSet<String>() {
{
add("3");
}
}
);
}
@Test
void dfsTest() {
graph.dfs(list, visited, 1);
// 방문여부 다시 초기화
for (int i = 1; i < visited.length; i++) {
visited[i] = false;
}
System.out.println();
graph.dfs(array, visited, 1);
}
@Test
void bfsTest() {
graph.bfs(list, visited, 1);
// 방문여부 다시 초기화
for (int i = 1; i < visited.length; i++) {
visited[i] = false;
}
System.out.println();
graph.bfs(array, visited, 1);
}
@Test
void digkstraTest() {
// 입력값이 2차원 배열인 경우
graph.dijkstra(array, 1);
System.out.println();
// 입력값이 1차원 리스트 배열인 경우
graph.dijkstra(weightList, 1);
System.out.println();
// 노드명이 문자열인 해쉬맵 구조
graph.dijkstra(map, "1");
}
}
최신 댓글