TypeScriptで実装するデータ構造
GitHub - uraway/data-structures.ts at master
LinkedList
LinkedListは、各要素が次の要素を参照を持っているシーケンスなデータ構造です。配列と似た形でデータを保存しますが、インデックスによるアクセスは苦手で、時間計算量は配列がO(1)であるのに対して、LinkedListは最悪O(n)です。
仕様
- push(value) -
O(1): データを追加する
- pop() -
O(1): 最後に追加されたデータを削除する
- find(index) -
O(n): indexの要素を検索する
- findBy(callback) -
O(n): 要素を検索する
- insertAt(index) -
O(n): indexに要素を追加
- removeFrom(index) -
O(n): indexの要素を削除
実装
export class LinkedListNode<T> {
value: T;
nextNode: LinkedListNode<T> | null;
constructor(value: T, next = null) {
this.value = value;
this.nextNode = next;
}
}
export class LinkedList<T> {
headNode: LinkedListNode<T> | null = null;
tailNode: LinkedListNode<T> | null = null;
length = 0;
constructor(values: T[]) {
values.forEach((value) => this.push(value));
}
push(value: T): LinkedListNode<T> {
const newNode = new LinkedListNode<T>(value);
if (!this.headNode || !this.tailNode) {
this.headNode = newNode;
this.tailNode = newNode;
} else {
this.tailNode.nextNode = newNode;
this.tailNode = newNode;
}
this.length += 1;
return newNode;
}
pop(): LinkedListNode<T> | null {
const deletedNode = this.tailNode;
if (this.headNode && this.tailNode) {
let curentNode = this.headNode;
while (curentNode !== null) {
if (curentNode.nextNode) {
curentNode = curentNode.nextNode;
} else {
curentNode == null;
}
}
this.tailNode = curentNode;
this.length -= 1;
}
return deletedNode;
}
find(index: number): LinkedListNode<T> | null {
let currentIndex = 0;
let currentNode = this.headNode;
if (index > this.length) {
throw new Error(`Node index(${index}) does not exist in the list.`);
}
while (currentIndex < index) {
if (currentNode?.nextNode) {
currentIndex += 1;
currentNode = currentNode?.nextNode;
}
}
return currentNode;
}
findBy(
callback: (currentNode: LinkedListNode<T>) => boolean
): LinkedListNode<T> | null {
let currentNode = this.headNode;
while (currentNode !== null) {
if (callback(currentNode)) {
return currentNode;
}
if (currentNode?.nextNode) {
currentNode = currentNode?.nextNode;
}
}
return null;
}
insertAt(value: T, index: number): LinkedList<T> {
if (index > this.length) {
throw new Error(`Node index(${index}) does not exist in the list.`);
}
const newNode = new LinkedListNode(value);
let currentIndex = 0;
let currentNode = this.headNode;
let prevNode = null;
if (index === 0) {
newNode.nextNode = this.headNode;
this.headNode = newNode;
this.length += 1;
return this;
}
while (currentIndex < index) {
if (currentNode?.nextNode) {
currentIndex += 1;
prevNode = currentNode;
currentNode = currentNode?.nextNode;
}
}
if (prevNode) {
newNode.nextNode = currentNode;
prevNode.nextNode = newNode;
}
this.length += 1;
return this;
}
removeFrom(index: number): LinkedList<T> {
if (index > this.length) {
throw new Error(`Node index(${index}) does not exist in the list.`);
}
let currentIndex = 0;
let currentNode = this.headNode;
let prevNode = null;
if (index === 0 && currentNode?.nextNode) {
this.headNode = currentNode?.nextNode;
this.length -= 1;
return this;
}
while (currentIndex < index) {
if (currentNode?.nextNode) {
currentIndex += 1;
prevNode = currentNode;
currentNode = currentNode?.nextNode;
}
}
if (prevNode?.nextNode && currentNode) {
prevNode.nextNode = currentNode.nextNode;
}
this.length -= 1;
return this;
}
values(): T[] {
const array = [];
let currentNode = this.headNode;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.nextNode;
}
return array;
}
*[Symbol.iterator](): Generator {
let currentNode = this.headNode;
while (currentNode !== null) {
currentNode = currentNode.nextNode;
yield currentNode;
}
}
}
const list = new LinkedList([1, 2, 3]);
console.log(list.push(1));
console.log(list.values());
console.log(list.insertAt(10, 1).values());
console.log(list.length);
console.log(list.removeFrom(4).values());
console.log(list.find(2)?.value);
console.log(list.find(10)?.value);
Stack
Stackは、LIFO(Last In First Out)のデータ構造です。データを'A','B','C'という順番に入れた場合、'C','B','A'といった順番で取り除くことができます。LinkedListの応用で実装できます。
仕様
- push(value) -
O(1): データを追加する
- pop() -
O(1): 最後に追加されたデータを削除する
- peek() -
O(1): 最後に追加されたデータを返す
実装
export class StackNode<T> {
value: T;
nextNode: StackNode<T> | null;
constructor(value: T, next = null) {
this.value = value;
this.nextNode = next;
}
}
export class Stack<T> {
headNode: StackNode<T> | null = null;
length = 0;
constructor(values: T[]) {
values.forEach((value) => this.push(value));
}
push(value: T): StackNode<T> {
const newNode = new StackNode(value);
newNode.nextNode = this.headNode;
this.headNode = newNode;
this.length += 1;
return newNode;
}
pop(): StackNode<T> | null {
const deletedNode = this.headNode;
if (this.headNode) {
this.headNode = this.headNode.nextNode;
this.length -= 1;
}
return deletedNode;
}
peek(): StackNode<T> | null {
return this.headNode;
}
values(): T[] {
const array = [];
let currentNode = this.headNode;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.nextNode;
}
return array;
}
*[Symbol.iterator](): Generator {
let currentNode = this.headNode;
while (currentNode !== null) {
currentNode = currentNode.nextNode;
yield currentNode;
}
}
}
const stack = new Stack([1, 2, 3]);
console.log(stack.push(4).value);
console.log(stack.values());
console.log(stack.pop()?.value);
console.log(stack.pop()?.value);
console.log(stack.peek()?.value);
Queue
Queueは、FIFO(First In First Out)のデータ構造です。データを'A','B','C'という順番に入れた場合、'A','B','C'といった順番で取り除くことができます。LinkedListの応用で実装できます。
仕様
- enqueue(value) -
O(1): データを追加する
- dequeue() -
O(1): 最も古いデータを削除する
- peek() -
O(1): 最も古いデータを返す
export class QueueNode<T> {
value: T;
nextNode: QueueNode<T> | null;
constructor(value: T, next = null) {
this.value = value;
this.nextNode = next;
}
}
export class Queue<T> {
headNode: QueueNode<T> | null = null;
tailNode: QueueNode<T> | null = null;
length = 0;
constructor(values: T[]) {
values.forEach((value) => this.enqueue(value));
}
enqueue(value: T): QueueNode<T> {
const newNode = new QueueNode(value);
if (!this.headNode) {
this.headNode = newNode;
}
if (!this.tailNode) {
this.tailNode = newNode;
} else {
this.tailNode.nextNode = newNode;
this.tailNode = newNode;
}
this.length += 1;
return newNode;
}
dequeue(): QueueNode<T> | null {
const deletedNode = this.headNode;
if (this.headNode) {
this.headNode = this.headNode.nextNode;
this.length -= 1;
}
return deletedNode;
}
peek(): QueueNode<T> | null {
return this.headNode;
}
values(): T[] {
const array = [];
let currentNode = this.headNode;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.nextNode;
}
return array;
}
*[Symbol.iterator](): Generator {
let currentNode = this.headNode;
while (currentNode !== null) {
currentNode = currentNode.nextNode;
yield currentNode;
}
}
}
const queue = new Queue([1, 2, 3]);
console.log(queue.enqueue(4).value);
console.log(queue.values());
console.log(queue.dequeue()?.value);
console.log(queue.dequeue()?.value);
console.log(queue.peek()?.value);
HashTable
HashTableは、Objectと同じくキーバリューペアでデータを保存します。キーのハッシュ値をインデックスとして、テーブル内にデータを保存します。データを検索する場合は、検索キーをハッシュし、配列にアクセスします。
JavaScriptでは、Object/Mapで事足りるはずなので、自分で実装する必要はありません。
仕様
- hash(key): キーのハッシュ関数
- set(key, value) -
O(1): 値をハッシュキーで保存する
- get(key) -
O(1): キーから値を取得する
実装
export class HashTable {
size: number;
table: Array<unknown>;
constructor(size: number) {
this.size = size;
this.table = [];
}
hash(key: string): number {
let id = 0;
for (let i = 0; i < key.length; i++) {
id += key.charCodeAt(i) * 100;
}
return id % this.size;
}
set(key: string, value: unknown): void {
const id = this.hash(key);
this.table[id] = value;
}
get(key: string): unknown {
const id = this.hash(key);
const value = this.table[id];
return value;
}
}
const hashTable = new HashTable(100);
hashTable.set('A', 'a');
hashTable.set('B', 'b');
console.log(hashTable.hash('A'));
console.log(hashTable.hash('B'));
console.log(hashTable.get('A'));
console.log(hashTable.get('B'));
ハッシュ関数が不完全またはHashTableのサイズが小さい場合、異なるキーから同一のインデックスが生成されることがあります。これを「衝突」と呼び、解決する方法の一つに、連鎖法があります。
実装には、コンストラクタで定義するtableに、LinkedListを使用します。ハッシュ値が衝突した場合、同一インデックスのLinkedListにデータをpushします。
import { LinkedList, LinkedListNode } from './list';
export class HashTableWithLinkedList {
size: number;
table: LinkedList<{ key: string; value: unknown }>[];
constructor(size: number) {
this.size = size;
this.table = Array({ length: size }).map(() => new LinkedList([]));
}
hash(key: string): number {
let id = 0;
for (let i = 0; i < key.length; i++) {
id += key.charCodeAt(i) * 100;
}
return id % this.size;
}
set(key: string, value: unknown): void {
const id = this.hash(key);
const linkedList = this.table[id];
linkedList.push({ value, key });
}
get(key: string): LinkedListNode<{ key: string; value: unknown }> | null {
const id = this.hash(key);
const linkedList = this.table[id];
return linkedList.findBy((currentNode) => currentNode.value.key === key);
}
}
const hashTableWithLinkedList = new HashTableWithLinkedList(100);
hashTableWithLinkedList.set('A', 'a');
hashTableWithLinkedList.set('B', 'b');
console.log(hashTableWithLinkedList.hash('A'));
console.log(hashTableWithLinkedList.hash('B'));
console.log(hashTableWithLinkedList.get('A')?.value);
console.log(hashTableWithLinkedList.get('B')?.value);
Tree
Treeは、階層性があるデータを表すのに適したデータ構造です。それぞれのNodeは、自身のデータとほかのNodeへの参照(親子関係)を持ちます。
仕様
Node
- value: 値
- parent: 親Nodeへの参照
- children[]: 子Nodeへの参照
Tree
- root: ルートNode(親Nodeを持たないNode)への参照
- traverseWithDepthFirst(): 深さ優先探索(親Nodeから子Nodeへの走査を優先する)
- traverseWithBreadthFirst(): 幅優先探索(深さが同じNodeの走査を優先する)
- find(callback, traversal): Nodeを指定した探索方法で検索する
- add(value, parentValue, traversal): parentValueを指定した探索方法で検索し、その子Nodeとしてvalueを追加する
- remove(value, parentValue, traversal): parentValueを指定した探索方法で検索し、その子Nodeにvalueがあれば削除する
traverseWithDepthFirst
深さ優先探索では、以下のようなTree構造があった場合走査順は、G -> E -> C -> D -> A -> B -> F とします。
G
/ \
E F
/ \
C D
/ \
A B
単純な再帰呼び出しで実装することができます。
traverseWithBreadthFirst
幅優先探索では、以下のようなTree構造があった場合走査順は、G -> E -> F -> C -> D -> A -> B とします。
G
/ \
E F
/ \
C D
/ \
A B
子Nodeをキュー(Queue)に登録しておき、現在のNodeを探索したあとで、キューに登録されたNodeを探索することで実装することができます。
実装
import { Queue } from './queue';
export class Node<T> {
value: T;
parent: Node<T> | null;
children: Node<T>[];
constructor(value: T) {
this.value = value;
this.parent = null;
this.children = [];
}
}
type Traversal<T> =
| Tree<T>['traverseWithBreadthFirst']
| Tree<T>['traverseWithDepthFirst'];
export class Tree<T> {
root: Node<T>;
constructor(value: T) {
this.root = new Node(value);
}
traverseWithDepthFirst(callback: (node: Node<T>) => void): void {
const traverse = (node: Node<T>) => {
for (let i = 0; i < node.children.length; i++) {
traverse(node.children[i]);
}
callback(node);
};
traverse(this.root);
}
traverseWithBreadthFirst(callback: (node: Node<T>) => void): void {
const queue = new Queue([this.root]);
let currentTree = queue.dequeue()?.value;
while (currentTree) {
for (let i = 0, length = currentTree.children.length; i < length; i++) {
queue.enqueue(currentTree.children[i]);
}
callback(currentTree);
currentTree = queue.dequeue()?.value;
}
}
find(callback: (node: Node<T>) => void, traversal: Traversal<T>): void {
traversal.call(this, callback);
}
add(value: T, parentValue: T, traversal: Traversal<T>): Node<T> {
let parentNode = null;
const newNode = new Node(value);
this.find((node) => {
if (node.value === parentValue) {
parentNode = node;
parentNode.children.push(newNode);
newNode.parent = parentNode;
}
}, traversal);
if (!parentNode) {
throw new Error('Cannot add node to a non-existence parent.');
}
return newNode;
}
remove(value: T, parentValue: T, traversal: Traversal<T>): Node<T> | null {
let deletedNode: Node<T> | null = null;
this.find((node) => {
if (node.value === parentValue) {
const deletedNodeIndex = node.children.findIndex(
(node) => node.value === value
);
if (!deletedNode) {
throw new Error('Node to remove does not exist.');
}
deletedNode = node.children[deletedNodeIndex];
node.children.splice(deletedNodeIndex, 1);
}
}, traversal);
return deletedNode;
}
}
const tree = new Tree('G');
tree.add('E', 'G', tree.traverseWithBreadthFirst);
tree.add('F', 'G', tree.traverseWithBreadthFirst);
tree.add('C', 'E', tree.traverseWithBreadthFirst);
tree.add('D', 'E', tree.traverseWithBreadthFirst);
tree.add('A', 'D', tree.traverseWithBreadthFirst);
tree.add('B', 'D', tree.traverseWithBreadthFirst);
Heap
Heapとは、子要素は親要素より常に大きいか等しい(または常に小さいか等しい)という制約を持つバイナリーツリー(ノードが持つ子要素が最大2である)構造のことです。ヒープメモリと混同しないように注意が必要です。
ここでは、MinHeap(子要素は親要素より常に小さい)を実装します。
仕様
- getMin() -
O(1): 最小値を返す
- insert(value) -
O(log n): 要素を追加する
- remove(value) -
O(log n): 要素を削除する
add
MinHeapにおいて、Nodeを追加するプロセスを図解してみます。Heapは配列としても表現できます:
1.Node(10)を追加する
Node(10)をルートとして追加します
10
[10]
2.Node(49)を追加する
バイナリーツリーでは、ある要素に新しい要素を追加する際左から追加します
10
/
49
[10, 49]
3.Node(26)を追加する
10
/ \
49 26
[10, 49, 26]
4.1.Node(13)を追加する
一時的に、Node(49)の子要素として追加します
10
/ \
49 26
/
13
[10, 49, 26, 13]
配列において、Node(13)のインデックスがn-1であるとき、その親のNode(49)のインデックスはMath.floor((n-1)/2)と表すことができます。
4.2.Node(13)を正しい場所に移動する
13 < 49 なので、Node(13)とNode(49)の場所をスワップします。10 < 13 なのでこれ以上入れ替えません。
10
/ \
13 26
/
49
[10, 13, 26, 49]
次に、時間計算量を考えます。上記(4)では、要素の入れ替えのためにルートの片側の親要素すべてと比較しました。したがって、時間計算量はMinHeapの高さhです。
MinHeapの要素数と、高さ(h)は次のような関係にあります。
| heapの要素数 |
h |
| 1 |
1 |
| 2 |
2 |
| 3 |
2 |
| 4 |
3 |
| 5 |
3 |
| 6 |
3 |
| 7 |
3 |
| 8 |
3 |
| 9 |
4 |
| <= [tex: 2k] |
 |
よって時間計算量は、
となります。
remove
次の概念図におけるMinHeapから、特定のNodeを削除するプロセスを見てみましょう:
10
/ \
13 26
/ \ / \
33 40 51 69
[10, 13, 26, 33, 40, 51, 69]
1.1.Node(10)を削除する
最も右(the last Node)を一時的にNode(10)のあった場所に据えます
69
/ \
13 26
/ \ /
33 40 51
[69, 13, 26, 33, 40, 51]
1.2.Node(69)を正しい場所に移動します
13 < 69 なので、Node(13)とNode(69)の場所をスワップします
13
/ \
69 26
/ \ /
33 40 51
[13, 69, 26, 33, 40, 51]
1.3.さらに、Node(69)を正しい場所に移動します
33 < 69 なので、Node(33)とNode(69)の場所をスワップします
13
/ \
33 26
/ \ /
69 40 51
[13, 33, 26, 69, 40, 51]
次に、時間計算量を考えます。最も入れ替えのコストが重い場合(最小の要素を削除する場合)を考えてみましょう。addと同じように、MinHeapの高さに比例します。
よって時間計算量は、となります。
実装
export class MinHeap {
heap: Array<number>;
constructor() {
this.heap = [];
}
swap(currentIndex: number, targetIndex: number): void {
const tmp = this.heap[targetIndex];
this.heap[targetIndex] = this.heap[currentIndex];
this.heap[currentIndex] = tmp;
}
add(value: number): void {
this.heap.push(value);
const currentIndex = this.heap.length - 1;
this.heapifyUp(currentIndex);
}
remove(value: number): void {
if (this.heap.length < 1) return;
for (let index = 0; index < this.heap.length; index++) {
if (this.heap[index] !== value) continue;
const lastItem = this.heap.pop() as number;
if (index === this.heap.length - 1) break;
this.heap[index] = lastItem;
this.heapifyUp(index);
this.heapifyDown(index);
}
}
heapifyUp(index: number): void {
let currentIndex = index - 1;
const parentIndex = Math.floor((currentIndex - 1) / 2);
while (
currentIndex > 1 &&
this.heap[parentIndex] > this.heap[currentIndex]
) {
this.swap(currentIndex, parentIndex);
currentIndex = parentIndex;
}
}
heapifyDown(index: number): void {
let currentIndex = index;
const currentValue = this.heap[index];
while (true) {
let indexToSwap = null;
const rightChildIndex = (currentIndex + 1) * 2;
const leftChildIndex = rightChildIndex - 1;
const rightChild = this.heap[rightChildIndex];
const leftChild = this.heap[leftChildIndex];
if (rightChild) {
if (rightChild < currentValue) {
indexToSwap = rightChildIndex;
}
}
if (leftChild) {
if (leftChild < (indexToSwap === null ? currentValue : rightChild)) {
indexToSwap = leftChildIndex;
}
}
if (indexToSwap === null) break;
this.swap(currentIndex, indexToSwap);
currentIndex = indexToSwap;
}
}
}
Trie
Trie)とは、ノードには自身に対応するプレフィックスがあるツリー構造。詳しくはwiki参照。
例えば、to/tea/tenが端NodeであるTrie構造は次のようになります。
null
/
t
/ \
to te
/ \
tea ten
仕様
- insert -
O(m): 単語を追加する。計算量は文字列の長さm
- findWords(prefix) -
O(m): prefixに続く単語を検索する。計算量は最短でも文字列の長さm
実装
export class TrieNode {
value: string;
children: { [x: string]: TrieNode };
isWord: boolean;
constructor(value: string, isWord: boolean) {
this.value = value;
this.children = {};
this.isWord = isWord;
}
addChild(value: string, isWord: boolean): TrieNode {
this.children[value] = new TrieNode(value, isWord);
return this.children[value];
}
removeChild(value: string): void {
delete this.children[value];
}
getWords(): string[] {
const results: string[] = [];
if (this.isWord) results.push(this.value);
Object.values(this.children).forEach((child) => {
const words = child.getWords();
words.forEach((word) => results.push(word));
});
return results;
}
}
export class Trie {
root: TrieNode;
constructor() {
this.root = new TrieNode('', false);
}
insert(word: string): void {
let currentNode = this.root;
const characters = Array.from(word);
let value = '';
characters.forEach((chr, i) => {
const isWord = i === characters.length - 1;
value += chr;
if (currentNode.children[value]) {
currentNode = currentNode.children[value];
} else {
currentNode = currentNode.addChild(value, isWord);
}
});
}
findWords(prefix: string): string[] {
let currentNode = this.root;
const results: string[] = [];
const characters = Array.from(prefix);
let value = '';
characters.forEach((chr, i) => {
value += chr;
const child = currentNode.children[value];
if (i === characters.length - 1) {
child.getWords().forEach((word) => {
results.push(word);
});
}
currentNode = child;
});
return results;
}
}
BinarySearchTree
「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つバイナリツリー。
実装
- insert -
O(log n): 要素を追加する
- find -
O(log n): 要素を検索する
時間計算量は、ツリーの高さがkであるとき、ノード数はk^2より小さいことから、
よって時間計算等は
仕様
export class BinarySearchTreeNode {
value: number;
right: null | BinarySearchTreeNode;
left: null | BinarySearchTreeNode;
constructor(value: number) {
this.value = value;
this.right = null;
this.left = null;
}
insert(value: number): void {
if (value === this.value) {
return;
}
if (value < this.value) {
if (this.left) {
this.left.insert(value);
} else {
const newNode = new BinarySearchTreeNode(value);
this.left = newNode;
}
}
if (this.value < value) {
if (this.right) {
return this.right.insert(value);
} else {
const newNode = new BinarySearchTreeNode(value);
this.right = newNode;
}
}
}
find(value: number): BinarySearchTreeNode | null {
if (value === this.value) {
return this;
}
if (value < this.value && this.left) {
return this.left.find(value);
}
if (this.value < value && this.right) {
return this.right.find(value);
}
return null;
}
}
export class BinarySearchTree {
root: BinarySearchTreeNode;
constructor(value: number) {
this.root = new BinarySearchTreeNode(value);
}
insert(value: number): void {
return this.root.insert(value);
}
find(value: number): BinarySearchTreeNode | null {
return this.root.find(value);
}
}
Graph
ノード(Vertex)の集合とエッジ(Edge)の集合によるデータ構造です。ノード同士がどのようにエッジによって結ばれるのかの関係を表現します。ベイジアンネットワークやニューラルネットワークの元になるデータ構造です。
4 - 5 - 1
/ \ \ /
6 3 - 2
仕様
- traverseWithDepthFirst(): 深さ優先探索(開始Vertexから次のVertexへの走査を優先する)
- traverseWithBreadthFirst(): 幅優先探索(開始Vertexから深さが同じVertexの走査を優先する)
traverseWithDepthFirst
スタックを使って、深さ優先探索を実装します。擬似コードは次のようになります。
function traverseWithDepthFirst
スタック、結果配列、走査済みマップを初期化
開始Vertexをスタックと走査済みマップに追加
while スタックが空でない間:
currentVertexをスタックから取り出す
currentVertexを結果配列に保存
adjacencyListからcurrentVertexにつながっているVertexを取り出し、
各Vertexが走査済みではないなら、走査済みマップとスタックに追加
return 結果配列
開始Vertexを4とすると、
- 4につながるVertexをスタックと走査済みマップに追加 Stack(
3, 5, 6) Visited(4, 3, 5, 6) Result(4)
- スタックをpopし、6を取り出す。6につながる未走査Vertexはないので次へ Stack(
3, 5) Visited(4, 3, 5, 6) Result(4, 6)
- スタックをpopし、5を取り出す。5につながる未走査Vertexをスタックと走査済みマップに追加 Stack(
3, 1, 2) Visited(4, 3, 5, 6, 1, 2) Result(4, 6, 5)
- スタックをpopし、2を取り出す。1につながる未操作Vertexはないので次へ Stack(
3, 1) Visited(4, 3, 5, 6, 1, 2) Result(4, 6, 5, 2)
- 以後繰り返し
traverseWithBreadthFirst
キューを使って、深さ優先探索を実装します。擬似コードは次のようになります。
function traverseWithBreadthFirst
キュー、結果配列、走査済みマップを初期化
開始Vertexをキューと走査済みマップに追加
while キューが空でない間:
currentVertexをキューから取り出す
currentVertexを結果配列に保存
adjacencyListからcurrentVertexにつながっているVertexを取り出し、
各Vertexが走査済みではないなら、走査済みマップとキューに追加
return 結果配列
開始Vertexを4とすると、
- キューに
3, 5, 6を追加 Queue(3, 5, 6) Result(4, 3, 5, 6)
- キューから3を取り出す。3につながる未走査Vertex(
2)をキューと走査済みマップに追加。 Queue(5, 6, 2) Result(4, 3, 5, 6, 2)
- キューから5を取り出す。5につながる未走査Vertex(
1)をキューと走査済みマップに追加。 Queue(6, 2, 1) Result(4, 3, 5, 6, 2, 1)
- キューから6を取り出す。6につながる未走査Vertexはない
- 以後繰り返し
実装
import { Queue } from './queue';
import { Stack } from './stack';
export class Graph {
adjacencyList: { [x: string]: string[] };
constructor() {
this.adjacencyList = {};
}
addVertex(vertex: string): void {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(source: string, destination: string): void {
if (!this.adjacencyList[source]) {
this.addVertex(source);
}
if (!this.adjacencyList[destination]) {
this.addVertex(destination);
}
this.adjacencyList[source].push(destination);
this.adjacencyList[destination].push(source);
}
removeEdge(source: string, destination: string): void {
this.adjacencyList[source] = this.adjacencyList[source].filter(
(vertex) => vertex !== destination
);
this.adjacencyList[destination] = this.adjacencyList[destination].filter(
(vertex) => vertex !== source
);
}
removeVertex(vertex: string): void {
while (this.adjacencyList[vertex]) {
const adjacentVertex = this.adjacencyList[vertex].pop();
if (adjacentVertex) {
this.removeEdge(vertex, adjacentVertex);
}
}
delete this.adjacencyList[vertex];
}
traverseWithDepthFirst(start: string): string[] {
const stack = new Stack([start]);
const result = [];
const visited: { [x: string]: boolean } = {};
visited[start] = true;
let currentVertex;
while (stack.length) {
currentVertex = stack.pop()?.value;
if (!currentVertex) continue;
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}
traverseWithBreadthFirst(start: string): string[] {
const queue = new Queue([start]);
const result = [];
const visited: { [x: string]: boolean } = {};
visited[start] = true;
let currentVertex;
while (queue.length) {
currentVertex = queue.dequeue()?.value;
if (!currentVertex) continue;
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.enqueue(neighbor);
}
});
}
return result;
}
}
const graph = new Graph();
['1', '2', '3', '4', '5', '6'].forEach((vertex) => {
graph.addVertex(vertex);
});
[
['1', '2'],
['1', '5'],
['2', '5'],
['2', '3'],
['3', '4'],
['4', '5'],
['4', '6'],
].forEach(([source, target]) => {
graph.addEdge(source, target);
});
console.log(graph);
console.log(graph.traverseWithDepthFirst('4'));
console.log(graph.traverseWithBreadthFirst('4'));
参考
