グラフアルゴリズムパターン

- グラフの表現（隣接リスト）
class Graph {
    private int V; // 頂点数
    private List<List<Integer>> adj; // 隣接リスト
    
    public Graph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }
    
    // 辺を追加（無向グラフの場合）
    public void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v); // 有向グラフの場合はこの行を削除
    }
    
    // 深さ優先探索（DFS）
    public void dfs(int start) {
        boolean[] visited = new boolean[V];
        dfsUtil(start, visited);
    }
    
    private void dfsUtil(int v, boolean[] visited) {
        // 現在のノードを訪問済みとしてマーク
        visited[v] = true;
        System.out.print(v + " ");
        
        // 隣接するすべての頂点を再帰的に探索
        for (Integer neighbor : adj.get(v)) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }
    
    // 幅優先探索（BFS）
    public void bfs(int start) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        
        // 開始ノードを訪問済みとしてマークし、キューに追加
        visited[start] = true;
        queue.add(start);
        
        while (!queue.isEmpty()) {
            // キューから頂点を取り出し、表示
            int v = queue.poll();
            System.out.print(v + " ");
            
            // 隣接するすべての未訪問の頂点をキューに追加
            for (Integer neighbor : adj.get(v)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
    
    // ダイクストラ法（単一始点最短経路）
    public int[] dijkstra(int start) {
        int[] dist = new int[V]; // 最短距離を格納する配列
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        // 訪問済みの頂点を追跡
        boolean[] visited = new boolean[V];
        
        // 全頂点について処理
        for (int count = 0; count < V - 1; count++) {
            // 未訪問の頂点の中から最短距離の頂点を選択
            int u = minDistance(dist, visited);
            
            // 選択した頂点を訪問済みとしてマーク
            visited[u] = true;
            
            // 選択した頂点の隣接頂点の距離を更新
            for (int v = 0; v < V; v++) {
                // 未訪問で、辺が存在し、パスが存在し、新しいパスがより短い場合
                if (!visited[v] && adj.get(u).contains(v) && 
                    dist[u] != Integer.MAX_VALUE && 
                    dist[u] + 1 < dist[v]) { // ここでは重みを1と仮定
                    dist[v] = dist[u] + 1;
                }
            }
        }
        
        return dist;
    }
    
    // 未訪問の頂点の中から最短距離の頂点を見つける補助メソッド
    private int minDistance(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        
        return minIndex;
    }
}