인접 행렬 vs 인접 리스트 — 그래프 표현의 트레이드오프

그래프 예시:
  0 --- 1
  |   / |
  |  /  |
  2 --- 3

// 위 그래프의 인접 행렬
int[][] matrix = {
    //  0  1  2  3
    {0, 1, 1, 0},  // 0번 정점
    {1, 0, 1, 1},  // 1번 정점
    {1, 1, 0, 1},  // 2번 정점
    {0, 1, 1, 0}   // 3번 정점
};

public class AdjacencyMatrix {
    private int[][] matrix;
    private int vertices;

    public AdjacencyMatrix(int vertices) {
        this.vertices = vertices;
        this.matrix = new int[vertices][vertices];
    }

    // 간선 추가: O(1)
    public void addEdge(int u, int v) {
        matrix[u][v] = 1;
        matrix[v][u] = 1; // 무방향 그래프
    }

    // 간선 존재 여부: O(1)
    public boolean hasEdge(int u, int v) {
        return matrix[u][v] == 1;
    }

    // u의 이웃 정점들: O(V)
    public List<Integer> neighbors(int u) {
        List<Integer> result = new ArrayList<>();
        for (int v = 0; v < vertices; v++) {
            if (matrix[u][v] == 1) {
                result.add(v);
            }
        }
        return result;
    }

    // 간선 삭제: O(1)
    public void removeEdge(int u, int v) {
        matrix[u][v] = 0;
        matrix[v][u] = 0;
    }
}

// 위 그래프의 인접 리스트
// 0: [1, 2]
// 1: [0, 2, 3]
// 2: [0, 1, 3]
// 3: [1, 2]

public class AdjacencyList {
    private List<List<Integer>> adjList;
    private int vertices;

    public AdjacencyList(int vertices) {
        this.vertices = vertices;
        this.adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    // 간선 추가: O(1)
    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u); // 무방향 그래프
    }

    // 간선 존재 여부: O(degree(u))
    public boolean hasEdge(int u, int v) {
        return adjList.get(u).contains(v);
    }

    // u의 이웃 정점들: O(1) — 리스트 자체를 반환
    public List<Integer> neighbors(int u) {
        return adjList.get(u);
    }

    // 간선 삭제: O(degree)
    public void removeEdge(int u, int v) {
        adjList.get(u).remove(Integer.valueOf(v));
        adjList.get(v).remove(Integer.valueOf(u));
    }
}

// BFS — 인접 리스트 기반: O(V + E)
public void bfs(int start) {
    boolean[] visited = new boolean[vertices];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int u = queue.poll();
        // 인접 리스트: 실제 이웃만 순회 → 효율적
        for (int v : adjList.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                queue.offer(v);
            }
        }
    }
}

// 인접 집합: 각 정점의 이웃을 HashSet으로 저장
List<Set<Integer>> adjSet = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
    adjSet.add(new HashSet<>());
}

// 간선 존재 확인: O(1) 평균
boolean hasEdge = adjSet.get(u).contains(v);

// 이웃 순회: O(degree)
for (int v : adjSet.get(u)) { ... }

// 간선을 (u, v, weight) 튜플의 리스트로 저장
List<int[]> edges = new ArrayList<>();
edges.add(new int[]{0, 1, 5});  // 0→1, 가중치 5
edges.add(new int[]{0, 2, 3});  // 0→2, 가중치 3

// Kruskal 알고리즘(MST) 등에서 유용
// 간선을 가중치 기준으로 정렬하기 편함
edges.sort(Comparator.comparingInt(e -> e[2]));

-- users 테이블 (정점)
CREATE TABLE users (
    id BIGINT PRIMARY KEY,
    name VARCHAR(100)
);

-- friendships 테이블 (간선 — 인접 리스트)
CREATE TABLE friendships (
    user_id BIGINT REFERENCES users(id),
    friend_id BIGINT REFERENCES users(id),
    PRIMARY KEY (user_id, friend_id)
);

-- 특정 사용자의 친구 목록 → 인접 리스트의 neighbors(u)
SELECT friend_id FROM friendships WHERE user_id = ?;

-- 두 사용자가 친구인지 확인 → hasEdge(u, v)
SELECT 1 FROM friendships WHERE user_id = ? AND friend_id = ?;

@Entity
public class User {
    @Id @GeneratedValue
    private Long id;

    // 인접 리스트: 이 사용자의 친구 목록
    @ManyToMany
    @JoinTable(
        name = "friendships",
        joinColumns = @JoinColumn(name = "user_id"),
        inverseJoinColumns = @JoinColumn(name = "friend_id")
    )
    private Set<User> friends = new HashSet<>();
}