그래프

그래프 구현 방식 -> 인접 행렬, 인접 리스트

3번 정점과 연결되어 있는 정점을 확인한다?

3행 전부 살펴보면 된다.

공간 복잡도 -> Vertex + Edge

• 인접리스트 기본 틀

1. 문제에서 주어진 정점, 간선 개수 받기
// int N = ...;
// int M = ...;

// 2. Map으로 그래프 자료구조 선언
Map<Integer, List<Integer>> graph = new HashMap<>();

// 3. 간선 정보 입력받아 그래프 만들기
for (int i = 0; i < M; i++) {
    int u = //u 입력
    int v = //v 입력
    
    // u -> v
    graph.computeIfAbsent(u, k-> new ArrayList<>()).add(v);
    // v -> u
    graph.computeIfAbsent(v, k-> new ArrayList<>()).add(u);
}

인접 행렬

1. 정점만 있는 경우

public class GraphMatrix {
    private final int[][] adj;
    private final int size;
    
    public GraphMatrix(int size) {
        this.size = size;
        this.adj = new int[size][size];
    }
    
    public void addEdge(int from, int to) {
        adj[from][to] = 1; // 무방향이면 adj[to][from]도 1
    }
    
    public boolean hasEdge(int from,int to) {
        return adj[from][to] == 1;
    }
}

1. 가중치가 있는 경우

public class WeightedGraphMatrix {
    private final int[][] adj;
    private final int size;
    private static final int INF = Integer.MAX_VALUE; 
    
    public WeightedGraphMatrix(int size) {
        this.size = size;
        this.adj = new int[size][size];
        
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                adj[i][j] = INF;
            }
        }
    }
    
    public void addEdge(int from, int to, int weight) {
        adj[from][to] = weight;
    }
    
    public int getWeight(int from, int to) {
        return adj[from][to];
    }
}

인접 리스트

public class GraphList {
    private final ArrayList<Integer>[] adj;
    
    public GraphList(int size) {
        for (int i = 0; i < size; i++) {
            adj.add(new ArrayList<>();
        }
    }
    
    public void addEdge(int from, int to) {
        add.get(from).add(to);
    }
    
    public List<Integer> getNeighbors(int vertex) {
        return adj.get(vertex);
    }
}

import java.util.*;

public class WeightedGraphList {
    public static class Edge {
        int to, weight;
        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private final List<List<Edge>> adj;

    public WeightedGraphList(int size) {
        adj = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int from, int to, int weight) {
        adj.get(from).add(new Edge(to, weight));
    }

    public List<Edge> getNeighbors(int vertex) {
        return adj.get(vertex);
    }
}

class GraphListTraversal {
    private final List<List<Integer>> adj;
    private final int n;

    public GraphListTraversal(int n) {
        this.n = n;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
        // adj.get(v).add(u);  // 무방향이라면
    }

    public void dfs(int start, boolean[] visited) {
        visited[start] = true;
        System.out.println("DFS visit: " + start);
        for (int neighbor : adj.get(start)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            System.out.println("BFS visit: " + curr);
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

가중치 포함

void dfs(int current, boolean[] visited, int currentCost) {
    visited[current] = true;
    System.out.println("DFS visit: " + current + ", total cost: " + currentCost);

    for (Edge edge : adj.get(current)) {
        if (!visited[edge.to]) {
            dfs(edge.to, visited, currentCost + edge.weight);
        }
    }
}
class Node {
    int v, cost;
    Node(int v, int cost) {
        this.v = v;
        this.cost = cost;
    }
}

void bfs(int start) {
    boolean[] visited = new boolean[n];
    Queue<Node> queue = new LinkedList<>();
    queue.add(new Node(start, 0));
    visited[start] = true;

    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        System.out.println("BFS visit: " + curr.v + ", total cost: " + curr.cost);

        for (Edge edge : adj.get(curr.v)) {
            if (!visited[edge.to]) {
                queue.add(new Node(edge.to, curr.cost + edge.weight));
                visited[edge.to] = true;
            }
        }
    }
}

가중치가 전부 동일한 경우에 한해, 그래프의 방향성 유무와 상관 없이 BFS를 통해 최단 거리를 구할 수 있다.