Graph

자료구조

그래프란?

• 정점(Vertex) 와 간선(Edge)로 구성된 비선형 자료구조
• 정점은 그래프의 Node, 간선은 정점 간의 연결 관계를 나타냄

그래프의 종류

1. 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프
2. 무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프
3. 가중치 그래프(Weighted Graph) : 간선에 가중치가 부여된 그래프
4. 비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프

그래프의 특징

• 인접 정점 : 간선으로 직접 연결된 정점들
• 차수(Degree) : 정점에 연결된 간선의 수
  • 진입 차수(In-degree) : 방향 그래프에서 정점으로 들어오는 간선 수
  • 진출 차수(Out-degree) : 방향 그래프에서 정점에서 나가는 간선의 수
• 경로(Path) : 한 정점에서 다른 정점으로 가는 간선의 연속
• 사이클(Cycle) : 시작 정점과 끝 정점이 같은 경로
• 연결 그래프(Connected Graph) : 모든 정점이 경로로 연결된 그래프
• 비연결 그래프(Disconnected Graph) : 일부 정점이 경로로 연결되지 않은 그래프

그래프 순회 알고리즘

1. DFS

import java.util.*;
 
public class Graph {
 
    private int numVertices;
    private List<List<Integer>> adjList;
 
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new ArrayList<>(numVertices);
        for(int i = 0; i < numVertices; i++) {
            adjList.add(new LinkedList<>());
        }
    }
 
    public void addEdgeUndirected(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }
 
    public void DFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        DFSUtil(startVertex, visited);
    }
 
    private void DFSUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");
        
        for(Integer adj : adjList.get(vertex)) {
            if(!visited[adj]) {
                DFSUtil(adj, visited);
            }
        }
    }
}

2. BFS

import java.util.*;
 
public class Graph {
 
    private int numVertices;
    private List<List<Integer>> adjList;
 
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new ArrayList<>(numVertices);
        for(int i = 0; i < numVertices; i++) {
            adjList.add(new LinkedList<>());
        }
    }
 
    public void addEdgeUndirected(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }
 
    public void BFS(int startVertex) {
    
        boolean[] visited = new boolean[numVertices];
        Queue<Integer> queue = new LinkedList<>();
        visited[startVertex] = true;
        queue.offer(startVertex);
 
        while(!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for(Integer adj : adjList.get(vertex)) {
                if(!visited[adj]) {
                    visited[adj] = true;
                    queue.offer(adj);
                }
            }
        }
    }
}

주요 그래프 알고리즘

1. 다익스트라 알고리즘

• 용도 : 가중치 그래프에서 특정 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘.
• 조건 : 모든 간선의 가중치가 비음수여야 함.
• 구현 방식 : 우선순위 큐를 사용하여 효율적으로 구현 가능
• 시간 복잡도 : O(E + VlogV) (우선순위 큐 사용시)