重みあり有向グラフの隣接行列と隣接リスト

今回は paiza の「重みあり有向グラフの隣接行列と隣接リスト」の問題に挑戦！

問題概要

問題のテーマ

• 重み付き有向グラフを
  • 隣接行列
  • 隣接リスト
    の 2つの表現で出力する 問題

入力として与えられるもの

• N：頂点の数
• M：辺の数
• 各辺について
  • a → b：向きのある辺
  • k：その辺の重み

グラフの条件

• 有向グラフ（向きあり）
• 重みあり
• 多重辺なし
• 自己ループなし

出力内容（合計 2N 行）

① 隣接行列（N 行）

• サイズ：N × N
• 意味：
  • i → j に重み k の辺がある → g[i-1][j-1] = k
  • 辺がない → 0
• 各行は 数値をスペースなしで連結して出力

② 隣接リスト（N 行）

• 各行は「その頂点から出る辺」を表す
• 出力ルール：
  • 接続先の頂点番号で 昇順ソート
  • b(k) の形式で横に並べる
  • 辺がなければ 「空行」

入力例:

10 2
5 9 8070
9 10 2464

出力例:

0000000000
0000000000
0000000000
0000000000
0000000080700
0000000000
0000000000
0000000000
0000000002464
0000000000




8(8070)



9(2464)

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const points = lines.slice(1).map(p => p.split(' ').map(Number));
    
    const gMatrix = Array.from({ length: N }, () => Array(N).fill(0)); // 隣接行列
    const gList = Array.from({ length: N }, () => []); // 隣接リスト
    
    for (let i = 0; i < M; i++) {
        const [a, b, k] = points[i]; // 頂点a→bと重みk
        
        gMatrix[a-1][b-1] = k;
        
        gList[a-1].push([b-1, k]);
    }
    
    gMatrix.forEach(g => console.log(g.join('')));
    
    for (let i = 0; i < N; i++) {
        gList[i].sort((a, b) => a[0] - b[0]); // 頂点番号でソート
        for (const val of gList[i]) {
            const [b, k] = val;
            process.stdout.write(`${b}(${k})`);
        }
        console.log();
    }
});

🔍 コードの流れ

• readline を使って 標準入力を1行ずつ配列 lines に格納
• 入力終了後（close）に処理開始
• 1行目から
  • 頂点数 N
  • 辺の数 M
    を取得
• 2行目以降から
  • 各辺の情報 [a, b, k]
    を配列 points にまとめて格納
• 隣接行列 gMatrix
  • サイズ N × N
  • 初期値はすべて 0
• 隣接リスト gList
  • 長さ N
  • 各要素は空配列で初期化
• 各辺について繰り返し処理
  • a → b に重み k の辺を
    • 隣接行列：gMatrix[a-1][b-1] = k
    • 隣接リスト：gList[a-1] に [b-1, k] を追加
• 隣接行列を 各行ごとに連結して出力
• 各頂点 i について
  • 隣接リスト gList[i] を 接続先頂点番号で昇順ソート
  • b(k) の形式で横に並べて出力
  • 接続先がなければ空行を出力

📝まとめ

グラフ表現について

• 隣接行列
  • 全頂点間の関係を一気に見られる
  • 実装がシンプル
  • サイズは常に N × N
• 隣接リスト
  • 実際に辺がある部分だけを持つ
  • 可変長配列が必要

「重みあり」で増えたポイント

• 辺の情報は
  • 「行き先の頂点」
  • 「重み」
    を セットで扱う必要がある
• 隣接リストでは
  • [行き先, 重み]
    のような構造で管理するのが基本

実装上の重要ポイント

• 入力は 1-index
• 配列は 0-index
  → 内部処理では -1 して扱う
• 出力は 問題の仕様・例に完全に従う
• 隣接リストは頂点でソートしてから出力する必要がある