グラフィック

グラフバー

データ構造はButexとEdgeで構成されています
頂点
Edge:Vertex接続幹線

種類

たんほうこうず

片方にしか移動できません

[
	[0,1,0,0,0,1],
  	[0,0,1,0,1,0],
  	[0,0,0,1,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,1,0],
]

双方向グラフィックス

2つのノード間で移動可能

[
	[0,1,0,0,0,1],
  	[1,0,1,0,1,0],
  	[0,1,0,1,0,0],
  	[0,0,1,0,0,0],
  	[0,1,0,0,0,1],
  	[1,0,0,0,1,0],
]

加重パターン

ウェイト値を含む移動

[
	[0,2,0,0,0,5],
  	[0,0,3,0,6,0],
  	[0,0,0,3,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,1,0],
]

きほんもんだい

DFS利用

function solution(n, arr) {
        let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
        let checkArr = Array.from(Array(n + 1)).fill(0);
        for (let i = 0; i < arr.length; i++) {
          graph[arr[i][0]][arr[i][1]] = 1;
        }
        let route = [];
        let result = [];
        let count = 0;
        console.log(graph);
        function dfs(v) {
          if (v === n) {
            // result = [...result, route];
            console.log(route);
            count++;
          } else {
            graph[v].forEach((el, idx) => {
              if (el === 1 && checkArr[idx] === 0) {
                checkArr[idx] = 1;
                route.push(idx);
                dfs(idx);
                checkArr[idx] = 0;
                route.pop(idx);
              }
            });
          }
          return count;
        }
        checkArr[1] = 1;
        route.push(1);
        return dfs(1);
      }

      let arr = [
        [1, 2],
        [1, 3],
        [1, 4],
        [2, 1],
        [2, 3],
        [2, 5],
        [3, 4],
        [4, 2],
        [4, 5],
      ];
      console.log(solution(5, arr));