가중치 그래프와 방향 그래프 — 현실 세계를 그래프로 모델링하기

방향 그래프:
  A → B
  ↑   ↓
  D ← C

무방향 그래프:
  A — B
  |   |
  D — C

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

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

    // 방향 그래프: u → v만 추가
    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        // adjList.get(v).add(u);  ← 이 줄이 없음!
    }

    // 진입 차수(in-degree) 계산
    public int[] calculateInDegree() {
        int[] inDegree = new int[vertices];
        for (int u = 0; u < vertices; u++) {
            for (int v : adjList.get(u)) {
                inDegree[v]++;
            }
        }
        return inDegree;
    }
}

// 방향 그래프의 인접 행렬은 비대칭
// A=0, B=1, C=2, D=3
// A→B, B→C, C→D, D→A
int[][] matrix = {
    {0, 1, 0, 0},  // A → B
    {0, 0, 1, 0},  // B → C
    {0, 0, 0, 1},  // C → D
    {1, 0, 0, 0}   // D → A
};

     5
  A ───→ B
  │       │
 3│       │2
  ↓       ↓
  D ←──── C
     4

public class WeightedGraph {
    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private List<List<Edge>> adjList;
    private int vertices;

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

    public void addEdge(int u, int v, int weight) {
        adjList.get(u).add(new Edge(v, weight));
    }

    public List<Edge> neighbors(int u) {
        return adjList.get(u);
    }
}

// 가중치 인접 행렬: 0 대신 가중치 값, 연결 없으면 무한대
int INF = Integer.MAX_VALUE;
int[][] matrix = {
    {0,   5, INF,   3},  // A: B(5), D(3)
    {INF, 0,   2, INF},  // B: C(2)
    {INF, INF, 0,   4},  // C: D(4)
    {INF, INF, INF, 0}   // D: 없음
};

// A가 B를 팔로우 → 방향 간선 A → B
DirectedGraph sns = new DirectedGraph(userCount);
sns.addEdge(alice, bob);     // Alice → Bob (팔로우)
// Bob은 Alice를 팔로우하지 않을 수 있음

// 인기 사용자 = 진입 차수(follower 수)가 높은 정점
int[] inDegree = sns.calculateInDegree();
// inDegree[bob] = Bob의 팔로워 수

// 교차로 = 정점, 도로 = 간선, 거리/시간 = 가중치
WeightedGraph roadNetwork = new WeightedGraph(intersectionCount);

// 일방통행도 표현 가능
roadNetwork.addEdge(gangnam, yeoksam, 5);    // 강남→역삼: 5분
roadNetwork.addEdge(yeoksam, gangnam, 7);    // 역삼→강남: 7분 (역방향 다를 수 있음)

// 네비게이션 = Dijkstra 알고리즘으로 최단 경로 계산
int[] shortestTime = dijkstra(roadNetwork, startIntersection);

// 서비스 = 정점, API 호출 = 간선, 지연 시간 = 가중치
WeightedGraph serviceGraph = new WeightedGraph(serviceCount);

serviceGraph.addEdge(gateway, userService, 10);     // 게이트웨이 → 유저 서비스: 10ms
serviceGraph.addEdge(userService, authService, 5);   // 유저 → 인증: 5ms
serviceGraph.addEdge(gateway, orderService, 15);     // 게이트웨이 → 주문: 15ms
serviceGraph.addEdge(orderService, paymentService, 20); // 주문 → 결제: 20ms

PageRank:
- 웹 페이지 = 정점
- 하이퍼링크 = 방향 간선
- Google의 PageRank는 이 방향 그래프에서 각 페이지의 "중요도"를 계산

// 빌드 시스템: 작업 간 의존성
// compile → test → package → deploy
WeightedGraph buildPipeline = new WeightedGraph(4);
buildPipeline.addEdge(compile, test, 30);      // 컴파일(30초) 후 테스트
buildPipeline.addEdge(test, pack, 60);          // 테스트(60초) 후 패키징
buildPipeline.addEdge(pack, deploy, 10);        // 패키징(10초) 후 배포

     2
  A ───→ B
  │       │
 5│       │-10
  ↓       ↓
  D ←──── C
     3

public int[] bellmanFord(int vertices, List<int[]> edges, int start) {
    int[] dist = new int[vertices];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // V-1번 반복
    for (int i = 0; i < vertices - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 음수 사이클 감지: V번째 반복에서도 갱신이 발생하면 음수 사이클
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            throw new RuntimeException("음수 사이클 존재!");
        }
    }

    return dist;
}

@Component
public class ServiceDependencyGraph {
    private final Map<String, List<Dependency>> graph = new HashMap<>();

    @Data
    @AllArgsConstructor
    static class Dependency {
        String target;
        double avgLatency; // 평균 지연 시간
        int callCount;     // 호출 횟수
    }

    // Micrometer/Zipkin 등에서 수집한 데이터로 그래프 구축
    public void addCall(String from, String to, double latency) {
        graph.computeIfAbsent(from, k -> new ArrayList<>())
             .add(new Dependency(to, latency, 1));
    }

    // 크리티컬 패스 분석: 가장 긴 경로 찾기
    public List<String> findCriticalPath(String start) {
        // DAG에서 최장 경로 = 위상 정렬 후 DP
        // ...
    }
}