我的電腦配置
CPU：AMD X4 640
內(nèi)存： 宏想 DDR3 1600MHz 8g
主板：華擎 980DE3/U3S3 R2.0
時間測試函數(shù)
function testRunTime(fn) {
let start = new Date();
let end = null;
fn();
end = new Date();
console.log(`運行時間: ${(end - start) / 1000}秒`);
}
數(shù)據(jù)結(jié)構(gòu)
線性結(jié)構(gòu)
1.數(shù)組
2.鏈表
3.隊列
4.棧
5.最大堆
6.映射
7.二叉樹
8.圖
9.哈希表
**
數(shù)組
// 數(shù)組
class MyArray {
constructor(capacity=10) {
this._data = new Array(capacity);
this._size = 0;
}
get length() {
return this._size;
}
get capacity() {
return this._data.length;
}
// 插入指定位置
insert(index, e) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
for (let i=this._size-1; i>=index; i--) {
this._data[i+1] = this._data[i];
}
this._data[index] = e;
this._size++;
}
// 添加到最后
insertLast(e) {
this.insert(this._size, e);
}
// 添加到開頭
insertFirst(e) {
this.insert(0, e);
}
// 獲取位置為index的元素
get(index) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
return this._data[index];
}
// 刪除位置為index的元素
remove(index) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
let ret = this._data[index];
for (let i=index,len=this._size-1; i<=len; i++) {
this._data[i] = this._data[i+1];
}
this._size--;
return ret;
}
// 更新元素
set(index, e) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
if (this._data[index]) {
this._data[index] = e;
} else { // 不存在就添加
this.insertLast(e);
}
}
// 是否包含元素
includes(e) {
for (let i=0,len=this._size; i<len; i++) {
if (Object.is(this._data[i], e)) {
return true;
}
}
return false;
}
// 查找元素, 返回索引
find(e) {
for (let i=0,len=this._size; i<len; i++) {
if (Object.is(this._data[i], e)) {
return i;
}
}
return -1;
}
toString() {
let str = "[";
for (let i=0,len=this._size; i<len; i++) {
str += this._data[i];
if (i != len-1) {
str += ",";
}
}
str += "]";
return str;
}
}
export default MyArray;
鏈表
單向鏈表
// 鏈表
class LinkedListNode {
constructor(e, next=null) {
this.e = e;
this.next = next;
}
}
class LinkedList {
constructor() {
this._dummyhead = new LinkedListNode(null);
this._tail = null; // 尾指針
this._size = 0;
}
get length() {
return this._size;
}
get isEmpty() {
return this._size == 0;
}
// 插入元素
insert(index, e) {
if (index < 0 || index>this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead;
for (let i=0; i<index; i++) {
cur = cur.next;
}
cur.next = new LinkedListNode(e, cur.next);
if (this._size === index) {
this._tail = cur.next;
}
this._size++;
}
// 插入表頭
insertFirst(e) {
this._dummyhead.next = new LinkedListNode(e, this._dummyhead.next);
if (this._size == 0) {
this._tail = this._dummyhead.next;
}
this._size++;
}
// 插入表尾
insertLast(e) {
if (this._size == 0) {
this._dummyhead.next = new LinkedListNode(e);
this._tail = this._dummyhead.next;
} else {
this._tail.next = new LinkedListNode(e);
this._tail = this._tail.next;
}
this._size++;
}
// 刪除元素
removeElement(e) {
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
while (prev != null) {
if (Object.is(prev.next.e,e)) {
break;
}
prev = prev.next;
}
if (prev != null) {
let ret = prev.next;
prev.next = ret.next;
ret.next = null;
if (Object.is(ret.e, this._tail.e)) {
this._tail = prev;
}
this._size--;
return ret;
}
return null;
}
// 根據(jù)位置刪除元素
removeIndex(index) {
if (index < 0 || index>this._size) {
throw new RangeError("index is invalid");
}
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
let ret;
for (let i=0; i<index; i++) {
prev = prev.next;
}
ret = prev.next;
prev.next = ret.next;
ret.next = null;
if (Object.is(ret.e, this._tail.e)) {
this._tail = prev;
}
this._size--;
return ret;
}
// 查找元素
find(e) {
let cur = this._dummyhead.next;
let index = 0;
while (cur !== null) {
if (Object.is(cur.e, e)) {
break;
}
index++;
cur = cur.next;
}
if (cur == null) {
return -1;
} else {
return index;
}
}
contains(e) {
let result = this.find(e);
return result != -1 ? true : false;
}
// 訪問元素
get(index) {
if (index < 0 || index>this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead.next;
for (let i=0; i<index; i++) {
cur = cur.next;
}
return cur;
}
toString() {
let res = "";
let cur = this._dummyhead.next;
for (let i=0,len=this._size; i<len; i++) {
res += cur.e;
if (i != len-1) {
res += " > ";
}
cur = cur.next;
}
return res;
}
}
export default LinkedList;
雙向鏈表
class LinkedListNode {
constructor(item, next = null, prev = null) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
// 雙向鏈表
class LinkedList {
constructor() {
this._dummyhead = new LinkedListNode(null);
this._tail = null; // 尾指針
this._size = 0;
}
get size() {
return this._size;
}
get isEmpty() {
return this._size === 0;
}
// 插入元素
insert(index, e) {
if (index < 0 || index > this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = new LinkedListNode(e, cur.next, cur);
if (cur.next.next) {
cur.next.next.prev = cur.next;
}
if (this._size === index) {
this._tail = cur.next;
}
this._size++;
}
// 插入表頭
unshift(e) {
this._dummyhead.next = new LinkedListNode(e, this._dummyhead.next);
if (this._size == 0) {
this._tail = this._dummyhead.next;
}
this._size++;
}
// 插入表尾
push(e) {
if (this._size == 0) {
this._dummyhead.next = new LinkedListNode(e, null, this._dummyhead);
this._tail = this._dummyhead.next;
} else {
this._tail.next = new LinkedListNode(e, null, this._tail);
this._tail = this._tail.next;
}
this._size++;
}
// 刪除元素
removeElement(e) {
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
while (prev != null) {
if (prev.next !== null && Object.is(prev.next.item, e)) {
break;
}
prev = prev.next;
}
if (prev != null) {
let ret = prev.next;
prev.next = ret.next;
if (ret.next) {
ret.next.prev = prev; // 調(diào)整上一個元素指向
}
ret.next = null;
if (Object.is(ret.item, this._tail.item)) {
this._tail = prev;
}
this._size--;
return ret;
}
return null;
}
// 根據(jù)位置刪除元素
removeIndex(index) {
if (index < 0 || index > this._size) {
throw new RangeError("index is invalid");
}
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
let ret;
for (let i = 0; i < index; i++) {
prev = prev.next;
}
ret = prev.next;
prev.next = ret.next;
if (ret.next) {
ret.next.prev = prev; // 調(diào)整上一個元素指向
}
ret.next = null;
if (Object.is(ret.item, this._tail.item)) {
this._tail = prev;
}
this._size--;
return ret;
}
pop() {
return this.removeIndex(this.size - 1);
}
shift() {
return this.removeIndex(0);
}
// 查找元素
find(e) {
let cur = this._dummyhead.next;
let index = 0;
while (cur !== null) {
if (Object.is(cur.item, e)) {
break;
}
index++;
cur = cur.next;
}
if (cur == null) {
return -1;
} else {
return index;
}
}
contains(e) {
let result = this.find(e);
return result != -1 ? true : false;
}
// 訪問元素
get(index) {
if (index < 0 || index > this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead.next;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}
toString() {
let res = "";
let cur = this._dummyhead.next;
for (let i = 0, len = this._size; i < len; i++) {
res += cur.item;
if (i != len - 1) {
res += " > ";
}
cur = cur.next;
}
return res;
}
iterator() { // 迭代器
return {
_item: this._dummyhead,
next() {
if (this.hasNext()) {
let ret = this._item.next;
this._item = this._item.next;
return ret;
}
return null;
},
hasNext() {
return this._item.next !== null;
}
}
}
}
棧
- 數(shù)組實現(xiàn)
class Stack {
constructor() {
this._data = [];
}
push(e) {
this._data.push(e);
}
pop() {
return this._data.pop();
}
peek() {
return this._data[0];
}
isEmpty() {
return this._data.length == 0;
}
get length() {
return this._data.length;
}
}
export default Stack;
- 鏈表實現(xiàn)
import LinkedList from "./LinkedList.js";
// 先引入鏈表
class Stack {
constructor() {
this._data = new LinkedList();
}
push(e) {
this._data.insertFirst(e);
}
pop() {
return this._data.removeIndex(0);
}
peek() {
return this._data.get(0);
}
get isEmpty() {
return this._data.isEmpty;
}
get lenght() {
return this._data.length;
}
}
export default Stack;
隊列
- 數(shù)組實現(xiàn)
class Queue {
constructor() {
this._data = [];
}
enqueue(e) {
this._data.push(e);
}
dequeue() {
return this._data.shift();
}
front() {
return this._data[0];
}
get isEmpty() {
return this._data.length == 0;
}
get length() {
return this._data.length;
}
toString() {
return "Front ["+this._data.toString+"]";
}
}
export default Queue;
- 鏈表實現(xiàn)
import LinkedList from "./LinkedList.js";
class Queue {
constructor() {
this._data = new LinkedList();
}
// 進隊
enqueue(e) {
this._data.insertLast(e);
}
// 出隊
dequeue() {
return this._data.removeIndex(0);
}
// 隊首元素
front() {
return this._data.get(0);
}
get isEmpty() {
return this._data.length == 0;
}
get length() {
return this._data.length;
}
toString() {
return "Front "+this._data.toString();
}
}
export default Queue;
二分搜索樹
import Queue from "./LinkedListQueue.js";
class Node {
constructor(e=null) {
this.e = e;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this._root = null;
this._size = 0;
}
get size() {
return this._size;
}
get isEmpty() {
return this._size == 0;
}
// 插入
insert(e) {
let _this = this;
if (this._root == null) {
this._root = new Node(e);
this._size++;
} else {
this._root = _insert(this._root);
}
function _insert(node) {
if (node == null) {
_this._size++;
return new Node(e);
}
if (e < node.e) {
node.left = _insert(node.left);
} else if (e > node.e) {
node.right = _insert(node.right);
}
return node;
}
}
// 最大值
maximum() {
if (this.isEmpty) {
throw new Error("data is empty");
}
return this._maximum(this._root);
}
_maximum(node) {
if (node.right == null) {
return node;
}
return this._maximum(node.right);
}
// 最小值
minimum() {
if (this.isEmpty) {
throw new Error("data is empty");
}
return this._minimum(this._root);
}
_minimum(node) {
if (node.left == null) {
return node;
}
return this._minimum(node.left);
}
// 刪除最小值
removeMin() {
if (this.isEmpty) {
throw new Error("data is empty");
}
let minimum = this.minimum();
this._root = this._removeMin(this._root);
return minimum;
}
_removeMin(node) {
if (node.left == null) {
let rightNode = node.right;
node.right = null;
this._size--;
return rightNode;
}
node.left = this._removeMin(node.left);
return node;
}
// 刪除最大值
removeMax() {
if (this.isEmpty) {
throw new Error("data is empty");
}
let maximum = this.maximum();
this._root = this._removeMax(this._root);
return maximum;
}
_removeMax(node) {
if (node.right == null) {
let leftNode = node.left;
node.left = null;
this._size--;
return leftNode;
}
node.right = this._removeMax(node.right);
return node;
}
// 刪除
remove(e) {
if (this.isEmpty) {
throw new Error("data is empty");
}
let _this = this;
this._root = _remove(this._root);
function _remove(node) {
if (node == null) {
return null;
}
if (e < node.e) {
node.left = _remove(node.left);
return node;
} else if (e > node.e) {
node.right = _remove(node.right);
return node;
} else { // 匹配成功
if (node.left == null) {
let rightNode = node.right;
node.right = null;
_this._size--;
return rightNode;
} else if (node.right == null) {
let leftNode = node.left;
node.left = null;
_this._size--;
return leftNode;
}
// 兩邊都有結(jié)點
let successor = _this._minimum(node.right);
successor.right = _this._removeMin(node.right);
successor.left = node.left;
return successor;
}
}
}
// 查找
find(e) {
if (this.isEmpty) {
throw new Error("data is empty");
}
return _find(this._root);
function _find(node) {
if (node == null) {
return null;
}
if (e < node.e) {
node.left = _find(node.left);
return node.left;
} else if (e > node.e) {
node.right = _find(node.right);
return node.right;
} else {
return node;
}
}
}
// 前序遍歷
preOrder() {
_preOrder(this._root);
function _preOrder(node) {
if (node == null) {
return;
}
console.log(node.e);
_preOrder(node.left);
_preOrder(node.right);
}
}
// 中序遍歷
inOrder() {
_inOrder(this._root);
function _inOrder(node) {
if (node == null) {
return;
}
_inOrder(node.left);
console.log(node.e);
_inOrder(node.right);
}
}
// 后序序遍歷
postOrder() {
_postOrder(this._root);
function _postOrder(node) {
if (node == null) {
return;
}
_postOrder(node.left);
_postOrder(node.right);
console.log(node.e);
}
}
// 層序遍歷
levelOrder() {
let queue = new Queue();
let node;
queue.enqueue(this._root);
while (!queue.isEmpty) {
node = queue.dequeue();
console.log(node.e.e);
if (node.e.left != null) {
queue.enqueue(node.e.left);
}
if (node.e.right != null) {
queue.enqueue(node.e.right);
}
}
}
// 是否包含某個元素
contains(e) {
return _contains(this._root);
function _contains(node) {
if (node == null) {
return false;
}
if (e < node.e) {
node.left = _contains(node.left);
return node.left;
} else if (e > node.e) {
node.right = _contains(node.right);
return node.right;
} else {
return true;
}
}
}
}
export default BST;
集合
- 數(shù)組實現(xiàn)
class Set {
constructor() {
this._data = [];
}
contains(e) {
return this._data.includes(e);
}
add(e) {
if (!this.contains(e)) {
this._data.push(e);
}
}
remove(e) {
let index = this._data.indexOf(e);
this._data.splice(index,1);
return this._data[index];
}
get length() {
return this._data.length;
}
get isEmpty() {
return this.length == 0;
}
}
export default Set;
- 鏈表實現(xiàn)
import LinkedList from "./LinkedList.js";
class Set {
constructor() {
this._data = new LinkedList();
}
contains(e) {
return this._data.contains(e);
}
add(e) {
if (!this.contains(e)) {
this._data.insertFirst(e);
}
}
remove(e) {
return this._data.removeElement(e);
}
get length() {
return this._data.length;
}
get isEmpty() {
return this.length == 0;
}
}
export default Set;
映射
雙向鏈表實現(xiàn)
查找和設(shè)置復(fù)雜度都是O(n)
| 數(shù)據(jù)量 | 雙向鏈表映射 | js自帶的對象 |
|---|---|---|
| 3萬 | 9.965秒 | 0.018秒 |
| 10萬 | 33.22秒 | 0.043秒 |
class Node {
constructor(key,value,prev=null,next=null) {
this.key = key;
this.value = value;
this.next = next;
this.prev = prev;
}
}
class LinkedListMap {
constructor() {
this._root = null;
this._tail = null;
this._size = 0;
}
get size() {return this._size}
get isEmpty() {return this._size === 0}
contains(key) {
if (typeof key !== "string") {throw("key need string type")}
for(let cur=this._root; cur!=null; cur=cur.next) {
if (cur.key === key) {
return cur;
}
}
return null;
}
get(key) {
if (typeof key !== "string") {throw("key need string type")}
let ret = this.contains(key);
return ret ? ret.value : null;
}
put(key, value) {
if (typeof key !== "string") {throw("key need string type")}
let ret = this.contains(key);
if (ret !== null) { // 有則更新
ret.value = value;
} else { // 沒有就創(chuàng)建
let node = new Node(key,value);
if (this.size === 0) {
this._root = node;
this._tail = node;
} else {
node.prev = this._tail;
this._tail.next = node;
this._tail = node;
}
this._size++;
}
}
delete(key) {
if (typeof key !== "string") {throw("key need string type")}
let node = this.contains(key);
if (node !== null) {
if (key === this._root.key) {
let next = this._root.next;
this._root.next = null;
this._root = next;
if (next != null) {
next.prev = null;
} else { // 只有一個節(jié)點
this._tail = null
}
} else {
node.prev.next = node.next;
if (key === this._tail.key) {
this._tail = node.prev;
} else {
node.next = null;
node.next.prev = null;
}
}
this._size--;
}
}
}
最大堆
class MaxHeap {
constructor(arr=[]) {
this._data = arr;
for (let i=this._parent(arr.length-1); i>=0; i--) {
this._shiftDown(i);
}
}
get length() {
return this._data.length;
}
get isEmpty() {
return this._data.length == 0;
}
add(e) {
this._data.push(e);
this._shiftUp(this._data.length-1);
}
get() {
return this._data[0];
}
remove(e) {
let ret = this._data.shift();
this._shiftDown(0);
return ret;
}
// 父節(jié)點的索引
_parent(index) {
if (index == 0) {
throw new RangeError("index-0 doesn't parent");
}
return Math.floor((index-1) / 2);
}
// 左結(jié)點的索引
_leftChild(index) {
return index*2+1;
}
// 右結(jié)點的索引
_rightChild(index) {
return index*2+2;
}
// 大的往上走
_shiftUp(k) {
let data = this._data;
while (k>0 && data[this._parent(k)] < data[k]) {
let parent = data[this._parent(k)];
data[this._parent(k)] = data[k];
data[k] = parent;
k=this._parent(k);
}
}
// 小的往下走
_shiftDown(k) {
let size = this._data.length;
while (this._leftChild(k) < size) {
let j = this._leftChild(k);
let data = this._data;
if (j+1 < size && data[j+1] > data[j]) {
j = this._rightChild(k);
}
if (data[k] > data[j]) {
break;
}
let agent = data[k];
data[k] = data[j];
data[j] = agent;
k=j;
}
}
}
export default MaxHeap;
優(yōu)先隊列
import MaxHeap from "./MaxHeap.js";
class PriorityQueue {
constructor() {
this._data = new MaxHeap();
}
get length() {
return this._data.length;
}
get isEmpty() {
return this._data.isEmpty;
}
enqueue(e) {
this._data.add(e);
}
dequeue() {
return this._data.remove();
}
front() {
return this._data.get();
}
}
export default PriorityQueue;
前綴樹
class Node {
constructor(isWord=false) {
this.isWord = isWord;
this.next = {};
}
}
class Trie {
constructor() {
this._root = new Node();
this._size = 0;
}
get size() {
return this._size;
}
add(word) {
let cur = this._root;
for (let i=0; i<word.length; i++) {
let key = word.charAt(i);
if (cur.next[key] == undefined) {
cur.next[key] = new Node();
}
cur = cur.next[key];
}
if (!cur.isWord) {
cur.isWord = true;
this._size++;
}
}
contains(word) {
let cur = this._root;
for(let i=0; i<word.length; i++) {
let key = word.charAt(i);
if (cur.next[key] == undefined) {
return false;
}
cur = cur.next[key];
}
return cur.isWord;
}
isPrefix(prefix) {
let cur = this._root;
for(let i=0; i<prefix.length; i++) {
let key = prefix.charAt(i);
if (cur.next[key] == undefined) {
return false;
}
cur = cur.next[key];
}
return true;
}
}
export default Trie;
并查集
class UnionFind {
constructor(size) { // size 集合數(shù)量
if (!size) {
throw new TypeError("size is empty");
}
this._parent = new Array(size);
this._rank = new Array(size); // 優(yōu)先級
for (let i=0; i<this._parent.length; i++) {
this._parent[i] = i;
this._rank[i] = 1;
}
}
get size() {
return this._parent.length;
}
_find(p) { // 查找所屬集合
if (p<0 && p>=parent.length) {
throw new RangeError(`${p} is invalid`);
}
while (p != this._parent[p]) {
this._parent[p] = this._parent[this._parent[p]];
p = this._parent[p];
}
return p;
}
isConnected(p, q) {
return this._find(p) == this._find(q);
}
unionElement(p, q) {
let pRoot = this._find(p);
let qRoot = this._find(q);
if (pRoot == qRoot) {
return;
}
if (this._rank[pRoot] < this._rank[qRoot]) { // 小的合并到大的集合
this._parent[pRoot] = qRoot;
} else if (this._rank[pRoot] > this._rank[qRoot]) {
this._parent[qRoot] = pRoot;
} else {
this._parent[qRoot] = pRoot;
this._rank[pRoot] += 1;
}
}
}
export default UnionFind;
哈希表
class HashTable {
constructor(capacity) {
if (!capacity) {
throw new RangeError("capacity is empty");
}
this._data = new Array(capacity);
this._size = 0;
for (let i=0; i<capacity; i++) {
this._data[i] = {}; // 沖突時保持到對象里
}
}
hashCode(key) { // 根據(jù)不同場景設(shè)計不同的哈希函數(shù)
let hash = 5381;
for (let i = 0; i < key.length; i++) {
hash = ((hash << 5) + hash) + key.charCodeAt(i);
}
return Math.abs(hash % this._data.length);
}
get size() {
return this._size;
}
add(key, value) {
let map = this._data[this.hashCode(key)];
if (map[key]) {
map[key] = value;
} else {
map[key] = value;
this._size++;
}
}
remove(key) {
let map = this._data[this.hashCode(key)];
let ret = map[key];
if (map[key]) {
delete map[key];
this._size--;
}
return ret;
}
get(key) {
return this._data[this.hashCode(key)][key];
}
set(key, value) {
let map = this._data[this.hashCode(key)];
if (!map[key]) {
throw new RangeError("key is not found");
}
map[key] = value;
}
contains(key) {
return !!(this.get(key));
}
}
export default HashTable;
圖
// 鄰接矩陣
class DenseGraph {
constructor(n, directed) {
this._n = n; // 點
this._m = 0; // 邊
this._directed = directed; // 是否有向圖
this._g = [];
for (let i = 0; i < n; i++) {
let arr = new Array(n).fill(false);
this._g.push(arr);
}
}
get V() { return this._n }
get E() { return this._m }
addEdge(v, w) {
if (this.hasEdge(v, w)) return;
this._g[v][w] = true;
if (!this._directed) {
this._g[w][v] = true;
}
this._m++;
}
hasEdge(v, w) {
if (v < 0 || v >= this._n) throw RangeError(v + " not exist");
if (w < 0 || w >= this._n) throw RangeError(w + " not exist");
return this._g[v][w];
}
DFS(v) { // 深度優(yōu)先遍歷
if (!this._g[0].includes(v)) {throw new RangeError(v+" is not exist")}
let visited = [];
let _this = this;
_dfs(v);
function _dfs(v) {
visited[v] = true;
console.log(v);
for (let i = v; i < _this._g.length; i++) {
for (let j = 0; j < _this._g[i].length; j++) {
if (_this._g[i][j] && !visited[j]) {
_dfs(j);
}
}
}
// 防止孤立的點沒被遍歷到
// for (let i = 0; i < _this._g.length; i++) {
// for (let j = 0; j < _this._g[i].length; j++) {
// if (_this._g[i][j] && !visited[j]) {
// _dfs(j);
// }
// }
// }
}
}
BFS(v) { // 廣度優(yōu)先遍歷
if (!this._g[0].includes(v)) {throw new RangeError(v+" is not exist")}
let queue = [];
let visited = [];
let node;
queue.push(v);
while (queue.length) {
visited[v] = true;
node = queue.shift();
console.log(node);
for (let i=node; i<this._g.length; i++) {
for (let j=0; j<this._g[i].length; j++) {
if (this._g[i][j] && !visited[j]) {
queue.push(j);
visited[j] = true;
}
}
}
}
}
}
// 鄰接表
class SparseGraph {
constructor(directed) {
this._n = []; // 點
this._edge = {};
this._m = 0; // 邊
this._directed = directed; // 是否有向圖
}
get V() { return this._n.length }
get E() { return this._m }
addEdge(v, w) {
if (!this._edge[v]) {
this._edge[v] = new Set();
this._n.push(v);
}
if (!this._edge[v].has(w)) {
this._edge[v].add(w);
this._m++;
}
if (!this._directed) {
if (!this._edge[w]) {
this._edge[w] = new Set();
this._n.push(w);
}
this._edge[w].add(v);
}
}
DFS(v) {
if (!this._edge[v]) {throw new RangeError(v+" is not exist")}
let visited = {};
let _this = this;
_dfs(v);
function _dfs(v) {
visited[v] = true;
console.log(v);
for (let key in _this._edge) {
_this._edge[key].forEach(item=>{
if (!visited[item]) {
_dfs(item);
visited[item] = true;
}
})
}
}
}
BFS(v) {
if (!this._edge[v]) {throw new RangeError(v+" is not exist")}
let visited = {};
let queue = [];
let node;
visited[v] = true;
queue.push(v);
while (queue.length) {
node = queue.shift();
console.log(node);
this._edge[node].forEach(item=>{
if (!visited[item]) {
queue.push(item);
visited[item] = true;
}
})
}
}
}
