グラフとは
グラフは有限個のノードとそれらを結ぶエッジで構成されます。
無向グラフ
ノード間のエッジは双方向です。ノード1はノード2へ、ノード2はノード1へトラバースできます。
有向グラフ
ノード間を結ぶエッジは一方通行です。ノード1からノード2にしか行くことができず、ノード2からノード1に行くことはできません。
グラフの表現方法
隣接結合表
各ノードを格納するために配列を使用し、配列の長さはノードの数です。配列の各ビットには、i 番目のノードに隣接するノードのリストが格納されます。
コロケーション行列
matrix[i][j] は、ノード i から j がエッジを持つことを表します。
無向グラフの実装
隣接表の実装
/**
*
*/
class Graph {
constructor () {
// key ～ ノード
// value ～ 隣接ノードのリスト
this.adjacencyList = new Map();
}
/**
* ノードを追加する
*/
addNode (node) {
if (!this.adjacencyList.has(node)) {
this.adjacencyList.set(node, []);
} else {
throw new Error('ノードはすでに存在する')
}
}
/**
*
* to
* form
*/
addEdge (to, from) {
if (
this.adjacencyList.has(to) &&
this.adjacencyList.has(from)
) {
// 重み付けを取り除く
let toAdjacent = this.adjacencyList.get(to)
let fromAdjacent = this.adjacencyList.get(from)
toAdjacent = [...new Set([...toAdjacent, from])];
fromAdjacent = [... new Set([...fromAdjacent, to])];
// 辺が2辺を結ぶ無向グラフ
this.adjacencyList.set(to, toAdjacent);
this.adjacencyList.set(from, fromAdjacent);
}
}
print () {
const nodes = this.adjacencyList.keys();
for (let node of nodes) {
const neighbors = this.adjacencyList.get(node);
const neighborsString = neighbors.join(' ');
console.log(` ${node}, 隣接ノード${neighborsString}`);
}
}
}
グラフの作成例
const graph = new Graph()
// ノードを追加する
graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('E')
graph.addNode('F')
//
graph.addEdge('A', 'B')
graph.addEdge('A', 'D')
graph.addEdge('A', 'E')
graph.addEdge('B', 'A')
graph.addEdge('B', 'C')
graph.addEdge('C', 'B')
graph.addEdge('C', 'E')
graph.addEdge('C', 'F')
graph.addEdge('D', 'A')
graph.addEdge('D', 'E')
graph.addEdge('E', 'A')
graph.addEdge('E', 'C')
graph.addEdge('E', 'D')
graph.addEdge('E', 'F')
graph.addEdge('F', 'C')
graph.addEdge('F', 'E')
//
graph.print()
// ノードA、隣接ノードB D E
// ノードB、隣接ノードA C
// ノードC、隣接ノードB E F
// ノードD、隣接ノードA E
// ノードE、隣接ノードA C D F
// ノードF、隣接ノードC E
グラフの幅優先走査
/**
*
*/
class Graph {
// ...
/**
* グラフを幅優先で走査する
* node 探索の開始点
*/
bfs (node) {
if (this.adjacencyList.has(node)) {
const result = [];
const hash = {};
const queue = [];
const nodes = this.adjacencyList.keys();
for (let node of nodes) {
hash[node] = false;
}
hash[node] = true;
queue.push(node);
result.push(node);
while (queue.length > 0) {
let q = queue.shift();
let list = this.adjacencyList.get(q);
for (let i = 0; i < list.length; i++) {
let temp = list[i]
if (!hash[temp]) {
result.push(temp)
hash[temp] = true
queue.push(temp)
}
}
}
return result;
}
return null
}
}
グラフの深さ優先走査
/**
*
*/
class Graph {
// ...
/**
* グラフを深さ優先で走査する
* node 探索の開始点
*/
dfs (node) {
const result = [];
const hash = {};
const nodes = this.adjacencyList.keys();
for (let node of nodes) {
hash[node] = false;
}
const DFS = (node) => {
let list = this.adjacencyList.get(node);
for (let i = 0; i < list.length; i++) {
let temp = list[i];
if (!hash[temp]) {
hash[temp] = true;
result.push(temp);
DFS(temp);
}
}
}
if (this.adjacencyList.has(node)) {
hash[node] = true;
result.push(node);
DFS(node);
return result;
}
return null;
}
}
コロケーション行列の実装
/**
*
*/
class Graph {
constructor () {
this.matrix = [];
}
/**
* ノードを追加する
*/
addNode () {
this.matrix.push([]);
const L = this.matrix.length;
for (let i = 0; i < L; i++) {
let start = this.matrix[i].length;
while (start < L) {
this.matrix[i][start] = 0;
start += 1
}
}
}
/**
*
*/
addEdge (to, from) {
if (
(to < this.matrix.length && to >= 0) &&
(from < this.matrix.length && from >= 0)
) {
this.matrix[to][from] = 1;
this.matrix[from][to] = 1;
}
}
print () {
const L = this.matrix.length;
for (let i = 0; i < L; i++) {
const current = i;
let neighbors = this.matrix[i].map((m, index) => {
if (
index !== i &&
m === 1
) {
return index;
}
return null;
});
neighbors = neighbors.filter(n => n !== null);
const neighborsString = neighbors.join(' ');
console.log(` ${current}, 隣接ノード${neighborsString}`);
}
}
}
グラフの幅優先走査
/**
*
*/
class Graph {
// ....
bfs (node) {
if (node >= 0 && node < this.matrix.length) {
const result = [];
const hash = {};
const queue = [];
for (let i = 0; i < this.matrix.length; i++) {
hash[i] = false;
}
hash[node] = true;
result.push(node);
queue.push(node);
while(queue.length > 0) {
let q = queue.shift();
let list = this.matrix[q];
for (let i = 0; i < list.length; i++) {
if (
list[i] === 1 &&
!hash[i]
) {
result.push(i);
hash[i] = true;
queue.push(i);
}
}
}
return result;
}
return -1;
}
dfs (node) {
if (node >= 0 && node < this.matrix.length) {
}
}
}
グラフの深さ優先走査
/**
*
*/
class Graph {
// ...
dfs (node) {
if (node >= 0 && node < this.matrix.length) {
const result = [];
const hash = {};
for (let i = 0; i < this.matrix.length; i++) {
hash[i] = false;
}
hash[node] = true;
result.push(node);
const DFS = (node) => {
let list = this.matrix[node];
for (let i = 0; i < list.length; i++) {
if (
list[i] === 1 &&
!hash[i]
) {
result.push(i);
hash[i] = true;
DFS(i);
}
}
};
DFS(node);
return result;
}
return -1;
}
}
有向グラフの実装
カラーテーブルによる有向グラフの実現
/**
*
*/
class Graph {
constructor () {
this.adjacencyList = new Map();
}
addNode (node) {
if (!this.adjacencyList.has(node)) {
this.adjacencyList.set(node, []);
} else {
throw new Error('ノードはすでに存在する')
}
}
addEdge (to, from) {
if (
this.adjacencyList.has(to) &&
this.adjacencyList.has(from)
) {
let toAdjacent = this.adjacencyList.get(to)
toAdjacent = [...new Set([...toAdjacent, from])];
// 有向グラフ。> from
this.adjacencyList.set(to, toAdjacent);
}
}
print () {
const nodes = this.adjacencyList.keys();
for (let node of nodes) {
const neighbors = this.adjacencyList.get(node);
const neighborsString = neighbors.join(' ');
console.log(` ${node}, 隣接ノード${neighborsString}`);
}
}
}
コロケーション行列を用いた有向グラフの実現
/**
*
*/
class Graph {
constructor () {
this.matrix = [];
}
addNode () {
this.matrix.push([]);
const L = this.matrix.length;
for (let i = 0; i < L; i++) {
let start = this.matrix[i].length;
while (start < L) {
this.matrix[i][start] = 0;
start += 1
}
}
}
addEdge (to, from) {
if (
(to < this.matrix.length && to >= 0) &&
(from < this.matrix.length && from >= 0)
) {
this.matrix[to][from] = 1;
}
}
print () {
const L = this.matrix.length;
for (let i = 0; i < L; i++) {
const current = i;
let neighbors = this.matrix[i].map((m, index) => {
if (
index !== i &&
m === 1
) {
return index;
}
return null;
});
neighbors = neighbors.filter(n => n !== null);
const neighborsString = neighbors.join(' ');
console.log(` ${current}, 隣接ノード${neighborsString}`);
}
}
}
加重グラフの実装
辺に重みを持つグラフ
襟テーブル実現の加重図
各ノードを格納するために配列が使用され、配列の長さはノードの数です。配列の長さはノードの数で、配列の各ビットには、i 番目のノードに隣接するノードのリストと、現在のノードに隣接する各ノードの重みが格納されます。
class Graph {
constructor () {
// key ~ ノード
// [value, weight] ~ 隣接ノードと重みのリスト
this.adjacencyList = new Map();
}
addNode (node) {
if (!this.adjacencyList.has(node)) {
this.adjacencyList.set(node, []);
} else {
throw new Error('ノードはすでに存在する')
}
}
/**
*
* to
* form
* weight
*/
addEdge (to, from, weight) {
if (
this.adjacencyList.has(to) &&
this.adjacencyList.has(from) &&
typeof weight === 'number'
) {
let toAdjacent = this.adjacencyList.get(to);
let fromAdjacent = this.adjacencyList.get(from);
toAdjacent = [...toAdjacent, [from, weight]];
fromAdjacent = [...fromAdjacent, [to, weight]];
this.adjacencyList.set(to, toAdjacent);
this.adjacencyList.set(from, fromAdjacent);
}
}
}
重み付きグラフのコロケーション行列実装
Lはノードの数。 matrix[i][j]は、ノードiからjのエッジの重み値を表します。
class Graph {
constructor () {
this.matrix = [];
}
addNode () {
this.matrix.push([]);
const L = this.matrix.length;
for (let i = 0; i < L; i++) {
let start = this.matrix[i].length;
while (start < L) {
this.matrix[i][start] = '*';
start += 1
}
}
}
/**
* to 端点1
* from
* weight 端点1と端点2の重み
*/
addEdge (to, from, weight) {
if (
(to < this.matrix.length && to >= 0) &&
(from < this.matrix.length && from >= 0) &&
typeof weight === 'number'
) {
this.matrix[to][from] = weight;
this.matrix[from][to] = weight;
}
}
}
最短経路問題
重みのないグラフの最短経路問題は、BFSを使えば十分です。
/**
* 無向グラフにおいて、ある頂点から他の頂点への最短経路を求める
* graph
* node 開始頂点
* 重みなしグラフ、辺の距離はデフォルトで1である
*/
const shortestPath = (graph, node) => {
// bfsを使用する
if (
graph &&
graph.adjacencyList &&
graph.adjacencyList.has(node)
) {
const hash = {};
const queue = [];
const nodes = graph.adjacencyList.keys();
for (let node of nodes) {
hash[node] = false;
}
hash[node] = 0;
queue.push(node);
while (queue.length > 0) {
let q = queue.shift();
let list = graph.adjacencyList.get(q);
for (let i = 0; i < list.length; i++) {
let temp = list[i]
if (hash[temp] !== false && hash[temp] > hash[q] + 1) {
hash[temp] = hash[q] + 1;
}
if (hash[temp] === false) {
hash[temp] = hash[q] + 1;
queue.push(temp)
}
}
}
return hash;
}
return -1;
}
重み付きグラフの最短経路問題
Dijkstra
ダイクストラ・アルゴリズムは、グラフのノード間の最短経路を求めるアルゴリズム。1956年にオランダの科学者、エッガース・ダイクストラが提唱。
まず、重み付きグラフを作成します。
// 加重グラフの作成
const graph = new Graph();
// ノードを追加する
graph.addNode('start')
graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('finish')
// 重みと同様に辺を追加する
graph.addEdge('start', 'A', 5)
graph.addEdge('start', 'B', 2)
graph.addEdge('A', 'B', 8)
graph.addEdge('A', 'C', 4)
graph.addEdge('A', 'D', 2)
graph.addEdge('B', 'D', 7)
graph.addEdge('C', 'D', 6)
graph.addEdge('C', 'finish', 3)
graph.addEdge('D', 'finish', 1)
/**
* Dijkstra
* @param graph
* @param startNode 先頭のノード
* @param endNode の末尾にあるノード
*/
const Dijkstra = (graph, startNode, endNode) => {
if (
graph.adjacencyList.has(startNode) &&
graph.adjacencyList.has(endNode) &&
endNode !== startNode
) {
const queue = new Queue();
const path = [];
const timeHash = {};
const backHash = {};
const nodes = graph.adjacencyList.keys();
for (let node of nodes) {
// デフォルトの距離は無限大
timeHash[node] = Number.POSITIVE_INFINITY
}
// 始点の距離を0とする
timeHash[startNode] = 0;
queue.enqueue([startNode, 0]);
while (!queue.isEmpty()) {
const [currentNode] = queue.dequeue();
const list = graph.adjacencyList.get(currentNode);
for (let i = 0; i < list.length; i++) {
const [nextNode, nextNodeWeight] = list[i];
let time = timeHash[currentNode] + nextNodeWeight;
// 常に最短経路をとる
if (time < timeHash[nextNode]) {
timeHash[nextNode] = time;
backHash[nextNode] = currentNode;
queue.enqueue([nextNode, time]);
}
}
}
let lastNode = endNode
// バックトラックオブジェクトを使い、最短経路を照会る
while (startNode !== lastNode) {
path.unshift(lastNode)
lastNode = backHash[lastNode];
}
path.unshift(startNode);
return `最短経路: ${path.join(' --> ')}, 所要時間: ${timeHash[endNode]}`
}
return -1
}
// 最短経路: start --> A --> D --> finish, 所要時間: 8
Dijkstra(graph, 'start', 'finish')
