그래프 알고리즘 종류와 활용 방법 관련

Java > Article(s)

---

Article(s)

• 그래프 알고리즘 개요
  • 1) 그래프의 기본 개념
  • 2) 그래프 구현 방법
• 그래프 알고리즘 종류
  • 1) 그래프 탐색 알고리즘
  • 2) 최단 경로 알고리즘
  • 3) 그 밖의 그래프 알고리즘
• 너비 우선 탐색과 깊이 우선 탐색 비교
  • 1) BFS 작동 방식
  • 2) DFS 작동 방식
  • 3) 두 알고리즘의 비교 및 장단점
• 그래프 탐색 알고리즘 활용 방법
  • 1) 컴퓨터 네트워킹에서의 활용
  • 2) 소셜 네트워크 및 온라인 분야에서의 활용
  • 3) 인공지능 및 머신러닝에서의 활용
• 마치며

---

그래프 알고리즘 종류와 활용 방법 | 요즘IT

그래프 알고리즘(Graph Algorithms)은 네트워크 분석, 경로 찾기, 최적화 문제 등 다양한 문제를 해결하는 데 사용되는 중요한 알고리즘입니다. 이번 글에서는 그래프에 관한 기본 개념과 구현 방법을 살펴보고, 그래프 알고리즘 중 가장 많이 사용되는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)의 작동 방식을 알아보겠습니다. 또한 어떤 분야에서 그래프 알고리즘을 활용할 수 있는지도 함께 정리해 보았습니다.

그래프 알고리즘(Graph Algorithms)은 네트워크 분석, 경로 찾기, 최적화 문제 등 다양한 문제를 해결하는 데 사용되는 중요한 알고리즘입니다. 이번 글에서는 그래프에 관한 기본 개념과 구현 방법을 살펴보고, 그래프 알고리즘 중 가장 많이 사용되는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)의 작동 방식을 알아보겠습니다. 또한 어떤 분야에서 그래프 알고리즘을 활용할 수 있는지도 함께 정리해 보았습니다.

---

그래프 알고리즘 개요

1) 그래프의 기본 개념

그래프는 정점(Vertex, 또는 노드(Node)라고도 함)과 이들을 연결하는 간선(Edge)으로 구성된 자료구조를 말합니다. 방향성이 있는 방향 그래프(Directed Graph)와 방향성이 없는 무방향 그래프(Undirected Graph)로 나뉘며, 간선에 가중치(Weight)가 있을 수도 있습니다. 이러한 그래프 자료구조는 컴퓨터 네트워크, 교통 시스템, 소셜 미디어와 같은 다양한 현실 세계의 문제를 모델링하는데 사용됩니다.

그래프 자료구조

2) 그래프 구현 방법

그래프를 구현하는 방법으로는 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 방법이 있습니다. 인접 리스트는 각 정점에 대해 연결된 모든 정점의 리스트를 저장하는 방식으로, 특정 정점과 인접한 정점들을 바로 알 수 있다는 장점이 있습니다.

반면 인접 행렬은 2차원 배열을 사용하여 노드 간의 연결 관계를 행렬 형태로 나타내는 방식입니다. 노드 간의 연결 여부를 빠르게 확인할 수 있다는 장점이 있지만, 모든 각 정점에 관한 관계를 기록하기 때문에 메모리 소비가 더 크다는 단점이 있습니다. 따라서 인접 행렬은 그래프 간선이 많은 그래프에 주로 사용하고, 인접 리스트는 상대적으로 간선이 적은 그래프에서 주로 사용합니다.

---

그래프 알고리즘 종류

1) 그래프 탐색 알고리즘

그래프 탐색 알고리즘(Graph Search Algorithms)은 그래프에서 특정 정점을 찾는 알고리즘을 말합니다. 이렇게 그래프 내 특정 정점을 찾기 위해서는 그래프의 각 정점을 순회하면서 방문해야 하므로, 그래프 순회 알고리즘(Graph Traversal Algorithms)으로 부르기도 합니다. 기본적인 그래프 탐색 알고리즘 종류로는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있습니다.

2) 최단 경로 알고리즘

최단 경로 알고리즘은 가중치가 있는 그래프에서 두 정점 간의 최소 가중치 합을 가지는 경로를 찾는 알고리즘을 말합니다. 대표적인 최단 경로 알고리즘으로는 다익스트라 알고리즘(Dijkstra Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 플로이드 알고리즘(Floyd Algorithm) 등이 있으며, 네트워크 설계, 교통 시스템 최적화, 지리적 경로 탐색 등 다양한 분야에서 경로 최적화 문제를 해결하는 데 활용됩니다.

3) 그 밖의 그래프 알고리즘

그래프 알고리즘에는 그래프 탐색과 최단 경로 찾기 외에도 다양한 알고리즘이 있습니다. 그중 하나인 위상 정렬(Topological Sorting) 알고리즘은 방향성이 있는 그래프에서 각 정점을 선후 관계에 따라 나열하는 알고리즘입니다. 이는 주로 의존성이 있는 여러 작업을 순서대로 정렬하는 데 사용되며, 프로젝트 스케줄링이나 컴파일러의 작업 순서 결정 등에 활용되고 있습니다.

이 밖에그래프의 모든 정점을 최소한의 간선으로 연결하는 부분 그래프를 찾는 **최소 신장 트리(Minimum Spanning Tree)**알고리즘도 있습니다. 최소 신장 트리 알고리즘은 네트워크 설계, 클러스터링, 물리적 인프라 계획 등에서 중요한 역할을 합니다. 대표적인 최소 신장 트리 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다.

---

너비 우선 탐색과 깊이 우선 탐색 비교

1) BFS 작동 방식

이번에는 그래프 알고리즘 중에서 가장 많이 사용되는 너비 우선 탐색(BFS, Breath-First Search)과 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘의 작동 방식과 장단점을 살펴보겠습니다. 먼저 BFS는 그래프 탐색 시 가까운 인접 정점을 모두 방문한 후, 그다음 가까운 인접 정점을 방문하는 방식의 그래프 탐색 알고리즘을 말합니다.

위와 같은 무방향 그래프에서 같은 레벨인 경우 오름차순으로 방문한다고 했을 때, BFS는 정점 1번부터 시작해서 인접한 정점들을 모두 방문하고 다음 차례의 정점에 대해 인접한 정점 중 아직 방문하지 않은 정점을 방문하는 식으로 탐색이 진행됩니다.

따라서 위 그래프의 BFS 탐색은 1번에 인접한 같은 레벨의 정점인 2, 3, 8번을 오름차순으로 방문하면서 시작합니다. 다음으로 2번 정점에 인접하면서 아직 방문하지 않은 정점인 6번 정점을 방문하고, 다음으로 3번 정점에 인접하면서 아직 방문하지 않은 정점인 4, 5를 오름차순으로 방문합니다. 마지막으로 6번 정점과 인접한 7번 정점을 방문하고 탐색이 종료됩니다.

이제 BFS를 구현한 자바 코드 예시를 보겠습니다.

.BFS.java

BFS(1/3)

BFS 클래스에는 그래프를 구현하기 위한 인접 리스트와 정점과 간선을 추가할 수 있는 메서드가 있습니다.

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;

public class BFS {

  // BFS 탐색을 위한 인접 리스트
  private final Map<Integer, List<Integer>> graph;

  // 생성자, 인접 리스트 초기화
  public BFS() {
    graph = new HashMap<>();
  }

  // 정점 추가
  public void addVertex(int vertex) {
    graph.put(vertex, new ArrayList<>());
  }

  // 간선 추가
  public void addEdge(int source, int destination) {
    if (!graph.containsKey(source)) {
      addVertex(source);
    }

    if (!graph.containsKey(destination)) {
      addVertex(destination);
    }

    graph.get(source).add(destination);
  }

  // ... 생략 ...
}

BFS(2/3)

다음으로 선입선출(FIFO) 자료 구조인 큐(Queue) 를 사용하여 BFS 메서드를 작성합니다. 앞서 설명한 것처럼 BFS 메서드에서는 방문한 정점의 인접 정점부터 차례대로 순회하면서 탐색을 진행합니다.

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;

public class BFS {
  // ... 생략 ...

  // BFS 탐색
  public void bfs(int source) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();

    queue.offer(source);
    visited.add(source);

    while(!queue.isEmpty()) {
      int current = queue.poll();
      System.out.print(current + " ");

      for (Integer neighbor : graph.get(current)) {
        if (!visited.contains(neighbor)) {
          queue.offer(neighbor);
          visited.add(neighbor);
        }
      }
    }
  }

  // ... 생략 ...
}

BFS(3/3)

다음 코드는 그래프를 출력하고, 실제로 BFS가 어떻게 탐색을 진행했는지 결과를 나타내는 테스트 코드입니다.

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;

public class BFS {
  // ... 생략 ...

  // 그래프 출력
  public void printGraph() {
    for (Integer vertex : graph.keySet()) {
      System.out.print(vertex + " -> ");
      for (Integer neighbor : graph.get(vertex)) {
        System.out.print(neighbor + " ");
      }
      System.out.println();
    }
  }

  public static void main(String[] args) {
    BFS bfs = new BFS();

    bfs.addEdge(1, 2);
    bfs.addEdge(1, 3);
    bfs.addEdge(1, 8);
    bfs.addEdge(2, 6);
    bfs.addEdge(2, 8);
    bfs.addEdge(3, 4);
    bfs.addEdge(3, 5);
    bfs.addEdge(4, 5);
    bfs.addEdge(6, 7);

    bfs.printGraph();

    System.out.println("BFS: start from vertex 1");
    bfs.bfs(1);
  }
}

앞서 살펴본 예시 그래프에 대해 BFS를 수행하면 1 > 2 > 3 > 8 > 6 > 4 > 5 > 7로 탐색 결과가 나오는 것을 볼 수 있습니다.

java -cp ./BFS.class
#
# BFS 테스트 결과
# 1 -> 2 3 8
# 2 -> 6 8
# 3 -> 4 5
# 4 -> 5
# 5
# 6 -> 7
# 7 ->
# 8 ->
# BFS: start from vertex 1
# 1 2 3 8 6 4 5 7

2) DFS 작동 방식

DFS는 출발 정점에서 최대한 깊이 갈 수 있는 정점까지 가보고, 더 이상 진행 못하지 못하는 경우 다시 돌아와서(Back Tracking) 갈림길에 있는 미방문 정점부터 탐색을 시작하는 방식을 말합니다.

위 그래프에서 DFS를 하면 출발 정점 1번부터 시작하여 2 > 6 > 7번 순으로 탐색을 진행합니다. 그리고 막다른 길인 7번에서 다시 뒤로 돌아와서, 갈림길이 있는 2번 정점에서 다시 8번으로 내려가는 방식으로 진행됩니다. 이와 같은 DFS를 구현하기 위해서는 자료 구조로 스택(Stack)을 사용하거나 재귀 호출 방식(Recursion)을 이용합니다.

다음 코드는 재귀 호출을 이용한 DFS 구현 코드 예시입니다.

.DFS.java

DFS(1/3)

이전의 BFS 예시 코드와 같이 먼저 DFS 클래스 내에 그래프를 구현하기 위한 인접 리스트를 생성하고, 정점과 간선을 추가할 수 있는 메서드를 만듭니다.

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;

public class DFS {
  // DFS 탐색을 위한 인접 리스트
  private final Map<Integer, List<Integer>> graph;

  // 생성자, 인접 리스트 초기화
  public DFS() {
    graph = new HashMap<>();
  }

  // 정점 추가
  public void addVertex(int vertex) {
    graph.put(vertex, new ArrayList<>());
  }

  // 간선 추가
  public void addEdge(int source, int destination) {
    if (!graph.containsKey(source)) {
      addVertex(source);
    }

    if (!graph.containsKey(destination)) {
      addVertex(destination);
    }

    graph.get(source).add(destination);
  }

  // ... 생략 ...
}

DFS(2/3)

DFS는 스택 자료 구조를 사용하여 만들 수도 있지만, 여기서는 재귀 호출을 이용 하여 구현했습니다. DFS 메서드에서는 정점의 방문 여부를 처리하기 위한 리스트를 생성하고, 재귀 호출 메서드인 dfsRecursive 메서드를 호출합니다. dfsRecursive 메서드에서는 번호가 낮은 순서로 방문 처리되지 않은 정점이 나올 때까지 재귀 호출을 하는 방식으로 탐색을 진행합니다.

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;

public class DFS {
  // ... 생략 ...
  
  // DFS 탐색
  public List<Integer> dfs(int source) {
    List<Integer> visited = new ArrayList<>();
    dfsRecursive(source, visited);
    return visited;
  }

  // DFS 재귀 메서드
  private void dfsRecursive(int node, List<Integer> visited) {
    visited.add(node);

    // 정렬하여 노드 번호가 낮은 순서부터 방문
    Collections.sort(graph.get(node));

    for (int neighbor : graph.get(node)) {
      if (!visited.contains(neighbor)) {
        dfsRecursive(neighbour, visited); // 재귀 호출
      }
    }
  }

  // ... 생략 ...
}

DFS(3/3)

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;

public class DFS {
  // ... 생략 ...

  // 그래프 출력
  public void printGraph() {
    for (Integer vertex : graph.keySet()) {
      System.out.print(vertex + " -> ");
      for (Integer neighbor : graph.get(vertex)) {
        System.out.print(neighbor + " ");
      }
      System.out.println();
    }
  }

  public static void main(String[] args) {
    DFS dfs = new DFS();

    dfs.addEdge(1, 2);
    dfs.addEdge(1, 3);
    dfs.addEdge(1, 8);
    dfs.addEdge(2, 6);
    dfs.addEdge(2, 8);
    dfs.addEdge(3, 4);
    dfs.addEdge(3, 5);
    dfs.addEdge(4, 5);
    dfs.addEdge(6, 7);

    dfs.printGraph();

    System.out.println("DFS: start from vertex 1");
    List<Integer> dfsResult = dfs.dfs(1);

    System.out.println("DFS 탐색 순서: " + dfsResult);
  }
}

마지막으로 그래프를 출력하고, DFS가 어떻게 탐색을 진행했는지 살펴보죠. 아래 테스트 코드를 보면 앞서 살펴본 예시 그래프처럼 1 > 2 > 6 > 7 > 8 > 3 > 4 > 5로 탐색 결과가 나오는 것을 확인할 수 있습니다.

java -cp ./DFS.class
#
# 1 -> 2 3 8
# 2 -> 6 8
# 3 -> 4 5
# 4 -> 5
# 5
# 6 -> 7
# 7 ->
# 8 ->
# DFS: start from vertex 1
# DFS 탐색 순서: [1, 2, 6,7, 8, 3, 4, 5]

3) 두 알고리즘의 비교 및 장단점

두 알고리즘의 시간 복잡도는 그래프의 구조에 따라 달라질 수 있으나, 일반적으로 $\text{O}\left(\text{V}+\text{E}\right)$ 로 표현됩니다. 여기서 V는 정점의 개수를 말하며, E는 간선의 개수를 말합니다.

두 알고리즘의 장단점을 살펴보면 우선 BFS는 최단 경로를 찾는 데 유용하지만, 넓은 범위를 탐색할 때 메모리 소비가 크다는 단점이 있습니다.

반면 DFS는 메모리 소비가 적고 복잡한 경로나 사이클을 찾는 데 유리하지만, 최단 경로를 보장하지 않는다는 단점이 있습니다. 이러한 장단점에 따라 BFS는 주로 네트워크 라우팅, 소셜 네트워킹의 최단 경로 찾기 등에 사용되고, DFS는 퍼즐, 미로 찾기, 트리 구조 분석 등에 주로 사용됩니다.

---

그래프 탐색 알고리즘 활용 방법

1) 컴퓨터 네트워킹에서의 활용

그래프 탐색 알고리즘은 컴퓨터 네트워킹 분야에서 중요한 역할을 합니다. 특히 네트워크 내에서의 데이터 패킷 전송 경로를 최적화하기 위해 최단 경로 알고리즘이 사용되는데요. 예를 들어, 라우터와 스위치는 BFS 또는 다익스트라 알고리즘을 이용하여 효율적인 데이터 전송 경로를 결정합니다.

2) 소셜 네트워크 및 온라인 분야에서의 활용

그래프 알고리즘은 소셜 네트워크 분석에서 사용자 간의 관계 및 커뮤니티 구조를 파악하는 데 사용되기도 합니다. 예를 들어, BFS와 DFS를 이용하여 친구 추천 시스템이나 소셜 네트워크 내에서의 영향력 있는 사용자를 식별하기도 합니다. 또한 온라인 플랫폼에서 웹 페이지 랭킹, 키워드 클러스터링, 연결 네트워크 분석 등에도 그래프 알고리즘이 중요한 역할을 합니다.

3) 인공지능 및 머신러닝에서의 활용

그래프 알고리즘은 인공지능(AI)과 머신러닝(ML) 분야에서도 여러 문제를 해결하는 데 활용됩니다. 예를 들어, 인공 지능과 관련하여 경로 탐색, 퍼즐 해결, 이미지 프로세싱 및 의사 결정 과정에서 그래프 알고리즘이 활용되며, 머신러닝 모델에서 데이터의 복잡한 관계를 파악하고 분류하는 데 사용되기도 합니다. 특히 지식 그래프와 추천 시스템, 자연어 처리(NLP) 등의 복잡한 데이터 집합 간의 숨겨진 패턴과 연결성을 탐색하고, 더욱 정확한 예측 모델을 구축하는 데 활용됩니다.

---

마치며

지금까지 그래프의 개념과 구현 방법, 그래프 탐색 알고리즘의 기초인 BFS, DFS의 작동 방식과 활용 방법을 살펴봤습니다. 그래프 알고리즘은 다양한 분야의 문제를 해결하는 데 활용되고 있으며, 특히 인공지능과 머신러닝 분야에서 많이 사용합니다. 해당 분야에 관심이 있다면 미리 기본적인 내용을 학습해 두는 것을 추천합니다.