[DataStructure] 그래프

[그래프의 종류와 구현]

그래프

• 그래프(Graph) : 정점이라 불리는 데이터를 간선 혹은 링크로 연결한 형태
  • 데이터 간의 연결 관계를 표현
• 연결 그래프(connected graph) : 임의의 두 정점 사이의 경로가 존재하는 그래프
• 비연결 그래프(disconnected graph) : 정점 사이에 경로가 존재하지 않을 수 있는 그래프
• 방향 그래프(directed graph) : 간선에 방향이 있는 그래프
• 무방향 그래프(undirected graph) : 간선에 방향이 없는 그래프
• 가중치 그래프(weighted graph) : 간선에 가중치가 부여된 그래프
  • 비용(cost) : 간선에 부여된 값
• 서브 그래프(subgraph) : 특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프

인접 행렬 기반 그래프 표현

• N X N 크기의 행렬로 그래프 표현하는 방법

  • 무방향 그래프

    

  • 방향 그래프

    

인접 리스트 기반 그래프 표현

• 그래프의 특정 정점과 연결된 정점들을 연결 리스트로 표현하는 방법

  

---

[깊이 우선 탐색과 너비 우선 탐색]

깊이 우선 탐색

• DFS(Depth-First Search) : 그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법

    import java.util.*;
  
    public class DFSExample {
        private static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
            // 현재 노드를 방문 처리
            visited[node] = true;
            System.out.print(node + " ");
  
            // 인접한 노드를 재귀적으로 방문
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    dfs(neighbor, visited, graph);
                }
            }
        }
  
        public static void main(String[] args) {
            int n = 5; // 노드 개수
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                graph.add(new ArrayList<>());
            }
  
            // 그래프 연결 정보 설정
            graph.get(1).add(2);
            graph.get(1).add(3);
            graph.get(2).add(4);
            graph.get(3).add(5);
  
            boolean[] visited = new boolean[n + 1];
            System.out.print("DFS: ");
            dfs(1, visited, graph);
        }
    }
  

너비 우선 탐색

• BFS(Breadth-First Search) : 그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 넓게 탐색하기를 반복하는 탐색 방법

    import java.util.*;
  
    public class BFSExample {
        private static void bfs(int start, List<List<Integer>> graph) {
            Queue<Integer> queue = new LinkedList<>();
            boolean[] visited = new boolean[graph.size()];
  
            queue.add(start);
            visited[start] = true;
  
            while (!queue.isEmpty()) {
                int node = queue.poll();
                System.out.print(node + " ");
  
                for (int neighbor : graph.get(node)) {
                    if (!visited[neighbor]) {
                        queue.add(neighbor);
                        visited[neighbor] = true;
                    }
                }
            }
        }
  
        public static void main(String[] args) {
            int n = 5; // 노드 개수
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                graph.add(new ArrayList<>());
            }
  
            // 그래프 연결 정보 설정
            graph.get(1).add(2);
            graph.get(1).add(3);
            graph.get(2).add(4);
            graph.get(3).add(5);
  
            System.out.print("BFS: ");
            bfs(1, graph);
        }
    }
  

---

[최단 경로 알고리즘]

최단 경로 알고리즘

• 최단 경로 알고리즘 : 한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고리즘
• 실생활 예
  • 지도 서비스 (원하는 목적지까지의 최단 거리)
  • 컴퓨터 네트워크

다익스트라 알고리즘

• Dijkstra’s Algorithm : 간선의 가중치가 음이 아닌 수라는 가정 하에 사용 가능한 최단 경로 알고리즘

• 동작 방식

  • 시작 정점 제외한 정점 초기화

  • (시작) 정점 방문

  • 경로 상 가중치 합과 최단 거리 테이블 상 값 비교

  • 최단 거리 테이블 갱신 가능하면 갱신

  • 방문하지 않은 정점 중 최단 거리가 가장 작은 정점 방문

  • 더 이상 방문할 정점이 없을 때까지 반복

    import java.util.*;
    
    public class DijkstraExample {
      static class Node implements Comparable<Node> {
          int vertex;
          int distance;
    
          public Node(int vertex, int distance) {
              this.vertex = vertex;
              this.distance = distance;
          }
    
          // 우선순위 큐에서 거리 오름차순으로 정렬하기 위한 비교 함수
          @Override
          public int compareTo(Node other) {
              return Integer.compare(this.distance, other.distance);
          }
      }
    
      public static int[] dijkstra(int start, List<List<Node>> graph, int n) {
          PriorityQueue<Node> pq = new PriorityQueue<>();
          int[] distances = new int[n + 1];
          Arrays.fill(distances, Integer.MAX_VALUE);
          distances[start] = 0;
    
          pq.add(new Node(start, 0));
    
          while (!pq.isEmpty()) {
              Node current = pq.poll();
              int currentVertex = current.vertex;
              int currentDistance = current.distance;
    
              // 이미 처리된 노드의 최단 경로보다 큰 경우 무시
              if (currentDistance > distances[currentVertex]) continue;
    
              // 인접 노드 확인
              for (Node neighbor : graph.get(currentVertex)) {
                  int newDist = distances[currentVertex] + neighbor.distance;
    
                  // 더 짧은 경로가 발견되면 갱신
                  if (newDist < distances[neighbor.vertex]) {
                      distances[neighbor.vertex] = newDist;
                      pq.add(new Node(neighbor.vertex, newDist));
                  }
              }
          }
    
          return distances;
      }
    
      public static void main(String[] args) {
          int n = 5; // 노드 개수
          List<List<Node>> graph = new ArrayList<>();
          for (int i = 0; i <= n; i++) {
              graph.add(new ArrayList<>());
          }
    
          // 그래프 연결 설정 (노드, 가중치)
          graph.get(1).add(new Node(2, 2));
          graph.get(1).add(new Node(3, 5));
          graph.get(2).add(new Node(3, 3));
          graph.get(2).add(new Node(4, 1));
          graph.get(3).add(new Node(4, 2));
          graph.get(4).add(new Node(5, 1));
    
          int start = 1; // 시작 노드
          int[] distances = dijkstra(start, graph, n);
    
          System.out.println("노드 " + start + "에서 각 노드까지의 최단 거리:");
          for (int i = 1; i <= n; i++) {
              System.out.println("노드 " + i + " : " + distances[i]);
          }
      }
    }

---

💡 참고 자료

• adjacency matrix of a graph
• adjacency list of a graph
• DFS
• BFS
• Dijkstra Algorithm