隣接リストの出力《グラフ理論》

グラフ構造の入力メニュー【隣接リストの出力(無向グラフ)・隣接リストの出力(有向グラフ)】

問題【STEP: 1】隣接リストの出力・無向グラフ
Task
無向グラフ の頂点数 n と m 組の頂点 が与えられるので 隣接リスト を出力してね。

【STEP: 1】コード

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b + 1);
      List[b].push(a + 1);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
   const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   List.forEach(value => {
      console.log(value.length ? value.join(' ') : -1);
   });
});
hogeちゃんの画像

隣接リスト…頂点 i と辺で直接つながっている頂点を並べたもの。
無向グラフ…辺に向きがつけられていないグラフ。

top
問題【STEP: 2】隣接リストの出力・有向グラフ 1
Task
有向グラフ の頂点数 n と m 組の頂点 が与えられるので 隣接リスト を出力してね。

【STEP: 2】コード

reader.on('close', () => {
   function adjacency_List(a, b) {
      List[a].push(b + 1);
      // List[b].push(a + 1);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   List.forEach(value => {
      console.log(value.length ? value.join(' ') : -1);
   });
});
hogeちゃんの画像

有向グラフ…辺に向きがつけられてるグラフ。

top
問題【FINAL】隣接リストの出力・有向グラフ 2
Task
有向グラフ の頂点数 n と m 組の頂点 ・重み が与えられるので 重み を出力してね。

【FINAL】コード

reader.on('close', () => {
   function adjacency_List(a, b, w) {
      List[a].push(w);
   }
   const List = [];  // 隣接リスト
   const [N, M] = lines[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i <= M; i++) {
      const [A, B, W] = lines[i].split(' ').map(Number);
      adjacency_List(A - 1, B - 1, W);
   }
   List.forEach(value => {
      console.log(value.length ? value.join(' ') : -1);
   });
});
hogeちゃんの画像

重みつき有向グラフ…辺に 重み と呼ばれる数がつけられた有向グラフ。

top

コメント