数据结构

发表于 | 更新于: | 分类于
字数统计: 4,147 字 | 阅读时长 ≈ 22 分钟

日常吐槽

平时的项目中，很少会用到数据结构与算法的相关知识。作为学习进阶的一个环节，最终还是把数据结构与算法提上了日程。突然有种感觉，这次的学习可能是这一辈子最深入的一次吧😌

列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

/**
 *  描述： List：列表是一组有序的数据。
 * 列表中的数据项称为元素，元素可以是任意数据类型
 * @class
 **/
class List {
  constructor() {
    /** 当前元素位置；
     * @type {number}
     * @private
     * **/
    this.position = 0;

    /** 列表元素容器；
     * @type {Array}
     * @private
     * **/
    this.dataStore = [];
  }

  /**
  * 从列表中查找某个元素；
  * @protected
  * @params {*} element 待查找的元素；
  * @return {number} 元素位置；
  **/
  find(element) {
    return this.dataStore.indexOf(element);
  }
  
 /**
  * 向列表中插入某个元素；
  * @protected
  * @params {*} element 待插入的元素；
  * @params {*=} pre 待插入位置的前一元素，可选；
  **/
  insert(element, prev) {
    let prevAt = this.find(prev);
    if (prevAt > -1) {
      this.dataStore.splice(prevAt, 0, element);
    } else {
      this.dataStore.push(element)
    }
  }

 /**
  * 从列表中删除某个元素；
  * @protected
  * @params {*} element 待删除的元素；
  **/
  remove(element) {
    let elementAt = this.find(element);
    if (elementAt > -1) {
      this.dataStore.splice(elementAt, 1)
    }
  }

 /**
  * 清空列表；
  * @protected
  **/
  clear() {
    this.dataStore.length = 0;
  }

 /**
  * 第一个元素位置；
  * @protected
  **/
  front() {
    this.position = 0;
  }

 /**
  * 最后一个元素位置；
  * @protected
  **/
  end() {
    this.position = this.dataStore.length - 1;
  }

 /**
  * 前一个元素位置；
  * @protected
  **/
  prev() {
    --this.position;
  }

 /**
  * 后一个元素位置；
  * @protected
  **/
  next() {
    if (this.position < this.dataStore.length) {
      ++this.position;
    }
  }

 /**
  * 将元素移到某个位置；
  * @params {number} positon 位置索引；
  * @protected
  **/
  moveTo(position) {
    this.position = position;
  }

 /**
  *当前元素是否存在前一个元素；
  * @protected
  * @return {boolean} 是否存在；
  **/
  hasNext() {
    return this.position < this.dataStore.length;
  }

 /**
  * 当前元素是否存在下一个元素；
  * @protected
  * @return {boolean} 是否存在；
  **/
  hasPrev() {
    return this.position >= 0;
  }

 /**
  * 获取当前元素；
  * @protected
  * @return {*} 当前元素；
  **/
  getElement() {
    return this.dataStore[this.position]
  }

 /**
  * 获取当前列表元素数；
  * @protected
  * @return {number} 当前列表长度；
  **/
  length() {
      return this.dataStore.length;
  }
}

let names = new List();
names.insert('a');
names.insert('b');
names.insert('c');
names.insert('d');
names.front();
names.next();
names.next();
names.prev();
names.hasNext();
names.moveTo(0);
names.remove('c');
for (names.front(); names.hasNext(); names.next()) {
  console.log(names.getElement());
}

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/**
 *  描述： Stack：栈内的元素只能通过列表的一端访问，这一端称为栈顶。
 * 栈被称为一种后入先出的数据结构。
 * @class
 **/
class Stack {
  constructor() {
    /** 栈元素容器；
     * @type {Array}
     * @private
     * **/
    this.dataStore = [];
  }

  /**
  * 查看栈顶元素；
  * @protected
  * @return {*} 栈顶元素；
  **/
  peek() {
    let topAt = this.dataStore.length - 1;
    return this.dataStore[topAt];
  }

  /**
  * 将元素压入栈；
  * @protected
  * @params {*} element 待压入栈的元素；
  **/
  push(element) {
    this.dataStore.push(element);
  }

  /**
  * 将元素弹出栈；
  * @protected
  * @params {*} element 待弹出栈的元素；
  * @return {*} 弹出栈的元素；
  **/
  pop() {
    return this.dataStore.pop();
  }

  /**
  * 清空栈；
  **/
  clear() {
    this.dataStore.length = 0;
  }

 /**
  * 获取当前栈元素数；
  * @protected
  * @return {number} 当前栈长度；
  **/
  length() {
    return this.dataStore.length;
  }
}

let names = new Stack();
names.push('a');
names.push('b');
names.push('c');
names.peek();
names.clear();
names.length();

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/**
 *  描述： Queue: 队列只能在队尾插入元素，队首删除元素。
 * 队列是一种先进先出的数据结构。
 * @class
 **/
class Queue {
  constructor() {
    /** 队列元素容器；
     * @type {Array}
     * @private
     * **/
    this.dataStore = [];
  }

  /**
  * 查看队首元素；
  * @protected
  * @return {*} 队首元素；
  **/
  head() {
    let headAt = 0;
    return this.dataStore[headAt];
  }

  /**
  * 查看队尾元素；
  * @protected
  * @return {*} 队尾元素；
  **/
  end() {
    let endAt = this.dataStore.length - 1;
    return this.dataStore[endAt];
  }

  /**
  * 入队；
  * @protected
  **/
  enqueue(element) {
    this.dataStore.push(element)
  }

  /**
  * 出队；
  * @protected
  **/
  dequeue() {
    return this.dataStore.shift();
  }

  /**
  * 清空队列；
  **/
  clear() {
    this.dataStore.length = 0;
  }

 /**
  * 获取当前队列元素数；
  * @protected
  * @return {number} 当前队列长度；
  **/
  length() {
    return this.dataStore.length;
  }
}

let names = new Queue();
names.enqueue('a');
names.enqueue('b');
names.enqueue('c');
names.head();
names.end();

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

/**
 *  描述： 链表节点
 * @class
 **/
class Node {
  constructor(element) {
    /** 保存节点数据；
     * @type {*}
     * @private
     * **/
    this.element = element;

    /** 保存指向下一个节点；
     * @type {null}
     * @private
     * **/
    this.next = null
  }
}
/**
 *  描述： LinkList: 链表是由一组节点组成的集合。
 * 每个节点使用一个对象的引用指向下一个节点。
 * 指向另一个节点的引用叫做链
 * @class
 **/
class LinkList {
  constructor() {
    /** 头节点；
     * @type {Objec}
     * @private
     * **/
    this.head = new Node('head');
  }

  /**
  * 查找节点；
  * params {*} element 节点元素；
  * @protected
  * @return {Objec} 节点；
  **/
  find(element) {
    let currentNode = this.head;
    while (currentNode && currentNode.element != element) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  /**
  * 查找链表最后一个节点；
  * @protected
  * @return {Objec} 节点；
  **/
  findLast() {
    let currentNode = this.head;
    while (currentNode.next) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  /**
  * 插入节点；
  * params {*} element 待插入节点元素；
  * params {*} prevElement 上一个节点元素；
  * @protected
  * @return {Objec} 节点；
  **/
  insert(element, prevElement) {
    let currentNode = new Node(element);
    let prevNode = this.find(prevElement) || this.findLast();
    currentNode.next = prevNode.next;
    prevNode.next = currentNode;
  }

  /**
  * 查找上一个节点；
  * params {*} element 当前节点元素；
  * @protected
  * @return {Objec} 节点；
  **/
  findPrev(element) {
    let currentNode = this.head;
    while (currentNode.next && currentNode.next.element != element) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  /**
  * 删除节点；
  * params {*} element 节点元素；
  * @protected
  **/
  remove(element) {
    let prevNode = this.findPrev(element);
    if (prevNode.next) {
      prevNode.next = prevNode.next.next;
    }
  }

  /**
  * 展示链表；
  * params {*} element 当前节点元素；
  * @protected
  **/
  display() {
    let currentNode = this.head;
    while (currentNode.next) {
      console.log(currentNode.next.element);
      currentNode = currentNode.next;
    }
  }
}

let names = new LinkList();
names.insert('a');
names.insert('b');
names.insert('c');
names.remove('b');
names.display();

字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/**
 *  描述： Dictionary: 字典是一种以键-值对形式存储数据的数据结构。
 * @class
 **/
class Dictionary {
  constructor() {
    /** 字典容器；
     * @type {Array}
     * @private
     * **/
    this.dataStore = {}
  }

 /**
  * 向字典中添加键值对；
  * @params {string} key 字典的健；
  * @params {*} value 字典的值；
  * @protected
  **/
  add(key, value) {
    this.dataStore[key] = value;
  }

 /**
  * 查找字典中元素；
  * @params {string} key 待查找的健；
  * @protected
  * @return {number} 代查找的值；
  **/
  find(key) {
    return this.dataStore[key];
  }

 /**
  * 删除字典中元素；
  * @params {string} key 待删除的健；
  * @protected
  **/
  remove(key) {
    delete this.dataStore[key];
  }

 /**
  * 清空字典中元素；
  * @protected
  **/
  clear() {
    Object.keys(this.dataStore).forEach(key => {
      delete this.dataStore[key];
    })
  }

 /**
  * 展示字典中元素；
  * @protected
  **/
  display() {
    Object.keys(this.dataStore).forEach(key => {
      console.log(`${key}: ${this.dataStore[key]}`);
    })
  }
}

let names = new Dictionary();
names.add('a', '1');
names.add('b', 2);
names.add('c', '3');
names.remove('b');
names.display();

散列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
 *  描述： HashTable: 通过散列函数尽量将键均匀地映射到数组中。
 * @class
 **/
class HashTable {
  constructor() {
    /** 散列表容器；
     * @type {Array}
     * @private
     * **/
    this.table = new Array(137);
  }

 /**
  * 散列算法；
  * @params {string} str 待转换的字符，使用除留余数法；
  * @protected
  * @return {number} 转换后的值；
  **/
  hashFunc(str) {
    const H = 37;
    let total = 0;
    for (let i = 0; i < str.length; i++) {
      total += H * total + str.charCodeAt(i);
    }
    total
    total = total % this.table.length;
    if (total < 0) {
      total += this.table.length + 1;
    }
    return parseInt(total);
  }

 /**
  * 将数据存入散列表；
  * @params {string} key 待存入数据的键；
  * @params {string} data 待存入的数据；
  * @protected
  **/
  put(key, data) {
    let position = this.hashFunc(key);
    this.table[position] = data;
  }

 /**
  * 获取对应键的值；
  * @params {string} key 待取数据的键；
  * @protected
  * @return {number} 对应键的值；
  **/
  get(key) {
    let position = this.hashFunc(key);
    return this.table[position];
  }

 /**
  * 删除对应键的值；
  * @params {string} key 待删除数据的键；
  * @protected
  **/
  remove(key) {
    let position = this.hashFunc(key);
    delete this.table[position]
  }

 /**
  * 展示散列表；
  **/
  display() {
    this.table.forEach((item, index) => {
      if (item) {
        console.log(item, index);
      }
    })
  }

  // 防止碰撞常用方法。碰撞：将两个键映射成同一个值的现象。
  /*
    // 开链法；将数组元素展开为二维数组。
    buildChains() {
      for (let i = 0; i < this.table.length; i++) {
        this.table[i] = new Array();
      }
    }
    put(key, data) {
      let position = this.hashFunc(key);
      let index = 0;
      while (this.table[position][index] != undefined) {
        index++;
      }
      this.table[position][index] = key;
      this.table[position][index + 1] = data;
    }
    get(key) {
      let position = this.hashFunc(key);
      let index = 0;
      while (this.table[position][index] != key) {
        if (index > this.table[position].length) return;
        index++;
      }
      return this.table[position][index + 1];
    } */


  /*
    // 线性探测法；在附近的空位塞入数据。
    values = [];
    put(key, data) {
      let position = this.hashFunc(key);
      while (this.table[position] != undefined) {
        position++;
      }
      this.table[position] = key;
      this.values[position] = data
    }
    get(key) {
      let position = this.hashFunc(key);
      while (this.table[position] != key) {
        if (position > this.table.length) return;
        position++;
      }
      return this.values[position]
    } */
}

let names = new HashTable();
names.put('a', 1);
names.put('b', 4);
names.put('c', 112);
names.put('d', 112);
names.remove('b');
names.display()

集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

/**
 *  描述： Set: 集合是由一组无序但彼此之间又有一定相关性的成员构成，每个成员在集合中只能出现一次。
 * @class
 **/
class Set {
  constructor() {
    /** 集合容器；
     * @type {Array}
     * @private
     * **/
    this.dataStore = [];
  }

 /**
  * 添加成员；
  * @params {*} element 待添加的成员；
  * @protected
  * @return {boolean} 添加成功返回真否则返回假；
  **/
  add(element) {
    if (!this.dataStore.includes(element)) {
      this.dataStore.push(element);
      return true;
    }
    return false;
  }

 /**
  * 删除成员；
  * @params {*} element 待删除的成员；
  * @protected
  * @return {boolean} 删除成功返回真否则返回假；
  **/
  remove(element) {
    let position = this.dataStore.indexOf(element);
    if (~position) {
      this.dataStore.splice(position, 1);
      return true;
    }
    return false;
  }

 /**
  * 与其它集合的并集；
  * @params {Set} set 待合并的集合；
  * @protected
  * @return {Set} 合并后的集合；
  **/
  union(set) {
    let tempSet = new Set();
    this.dataStore.forEach(element => {
      tempSet.add(element);
    })
    set.dataStore.forEach(element => {
      if (!tempSet.dataStore.includes(element)) {
        tempSet.add(element);
      }
    })
    return tempSet;
  }

 /**
  * 交集；
  * @params {Set} set 其它集合；
  * @protected
  * @return {Set} 两集合共同存在成员组成的集合；
  **/
  intersect(set) {
    let tempSet = new Set();
    this.dataStore.forEach(element => {
      if (set.dataStore.includes(element)) {
        tempSet.add(element);
      }
    })
    return tempSet;
  }

 /**
  * 补集
  * @params {Set} set 其它集合；
  * @protected
  * @return {Set} 属于该集合而不属于其它集合的成员组成的集合；
  **/
  difference(set) {
    let tempSet = new Set();
    this.dataStore.forEach(element => {
      if (!set.dataStore.includes(element)) {
        tempSet.add(element);
      }
    })
    return tempSet;
  }

 /**
  * 判断是否是其它集合子集；
  * @params {Set} set 其它集合；
  * @protected
  * @return {boolean} 是其它集合子集返回真否则返回假；
  **/
  subset(set) {
    if (this.dataStore.length > set.dataStore.length) {
      return false;
    } else {
      return !this.dataStore.find(element => set.dataStore.includes(element))
    }
  }
  /**
 * 展示散列表；
 **/
  display() {
    this.dataStore.forEach((element, index) => {
      if (element) {
        console.log(element, index);
      }
    })
  }

}
let names = new Set()
names.add('a');
names.add('b');
names.add('c');
names.remove('b');
let names_1 = new Set();
names_1.add('a');
names_1.add('e');
names.subset(names_1)

二叉树和二叉查找树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207

/**
 *  描述： 树节点
 * @class
 **/
class Node {
  constructor(data, left, right) {
    /** 节点保存的数据；
     * @type {*}
     * @private
     * **/
    this.data = data;

    /** 左节点；
     * @type {Node}
     * @private
     * **/
    this.left = left;

    /** 右节点；
     * @type {Node}
     * @private
     * **/
    this.right = right;
  }
}

/**
 *  描述：树是一种非线性的数据结构，以分层的方式存储数据。
 * 树由一组以边连接的节点组成。
 * 从一个节点到另一个节点的这一组边称为路径，以某种特定顺序访问树中所有的节点成为树的遍历。
 * 二叉树子节点不超过两个。
 * BST： 二叉查找树是一种特殊的二叉树，相对小的值保存在左节点中，较大的值保存在右节点中。
 * @class
 **/
class BST {
  constructor() {
    /** 根节点；
     * @type {Node}
     * @private
     * **/
    this.root = null;
  }

 /**
  * 向树中插入新节点；
  * @params {*} data 插入的数据；
  * @protected
  **/
  insert(data) {
    let n = new Node(data, null, null);
    if (this.root == null) {
      this.root = n;
    } else {
      let current = this.root;
      let parent;
      while (true) {
        parent = current;
        if (data < current.data) {
          current = current.left;
          if (current == null) {
            parent.left = n;
            break;
          }
        } else {
          current = current.right;
          if (current == null) {
            parent.right = n;
            break;
          }
        }
      }
    }
  }

 /**
  * 中序遍历；
  * @params {Node} node 遍历的根节点；
  * @protected
  **/
  inOrder(node) {
    if (node) {
      this.inOrder(node.left);
      console.log(node.data);
      this.inOrder(node.right);
    }
  }
  /*
    // 先序遍历；
     preOrder(node) {
      if (node) {
        console.log(node.data);
        this.preOrder(node.left);
        this.preOrder(node.right);
      }
    }
    // 后序遍历；
    postOrder(node) {
      if (node) {
        this.postOrder(node.left);
        this.postOrder(node.right);
        console.log(node.data);
      }
    } */

 /**
  * 获取最小值节点；
  * @params {Node} node 待查找的节点；
  * @protected
  * @return {Node} 拥有最小值的节点；
  **/
  getMin(node) {
    let current = node || this.root;
    while (current.left) {
      current = current.left;
    }
    return current;
  }

 /**
  * 获取最大值节点；
  * @params {Node} node 待查找的节点；
  * @protected
  * @return {Node} 拥有最大值的节点；
  **/
  getMax(node) {
    let current = node || this.root;
    while (current.right) {
      current = current.right;
    }
    return current;
  }

 /**
  * 查找指定数据的节点；
  * @params {*} data 待查找的数据；
  * @protected
  * @return {Node} 拥有指定数据的节点；
  **/
  find(data) {
    let current = this.root;
    while (current != null) {
      if (current.data == data) {
        return current;
      } else if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return null;
  }

 /**
  * 删除指定数据的节点；
  * @params {*} data 待删除的数据；
  * @protected
  **/
  remove(data) {
    let self = this;
    this.root = removeNode(this.root, data);
    function removeNode(node, data) {
      if (node == null) return null;
      if (data == node.data) {
        // 没有子节点；
        if (node.left == null && node.right == null) {
          return null;
        }
        // 只有右节点；
        if (node.left == null) {
          return node.right;
        }
        // 只有左节点；
        if (node.right == null) {
          return node.left;
        }
        // 有左、右子节点；
        let tempNode = self.getMin(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        /*
        // 或者左节点最大值；
        let tempNode = self.getMax(node.left);
        node.data = tempNode.data;
        node.left = removeNode(node.left, tempNode.data); */
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    }
  }
}

let names = new BST();
names.insert(12);
names.insert(6);
names.insert(18);
names.insert(3);
names.insert(9);
names.insert(15);
names.insert(21);
names.inOrder(names.root);
names.remove(6);

图和图算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

/**
 *  描述： Graph: 图由边的集合及顶点的集合组成。
 * 邻接表或邻接表数组：将边存储为由顶点的相邻顶点列表构成的数组，并以此顶点作为索引。
 * @class
 **/
class Graph {
  constructor(v) {
    /** 顶点数；
     * @type {number}
     * @private
     * **/
    this.vertices = v;

    /** 边数；
     * @type {number}
     * @private
     * **/
    this.edges = 0;

    /** 邻接表数组；
     * @type {Array}
     * @private
     * **/
    this.adj = Array.from({ length: v }).map(() => ([]));

    /** 顶点访问状态；
     * @type {Array}
     * @private
     * **/
    this.marked = Array.from({ length: v }).map(() => (false));
  }

 /**
  * 添加顶点；
  * @params {} v 顶点；
  * @params {} w 顶点；
  * @protected
  **/
  addEdge(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
  }

 /**
  * 深度优先搜索；
  * @params {} v 顶点；
  * @protected
  **/
  dfs(v) {
    this.marked[v] = true;
    // 打印遍历路径；
    if (!this.adj[v] != undefined) {
      console.log('visted:', v);
    }
    for (let vertex of this.adj[v]) {
      if (!this.marked[vertex]) {
        this.dfs(vertex);
      }
    }
  }

 /**
  * 广度优先搜索；
  * @params {} v 顶点；
  * @protected
  **/
  bfs(v) {
    let queue = [];
    this.marked[v] = true;
    queue.push(v);
    while (queue.length > 0) {
      let v = queue.shift();
      // 打印遍历路径；
      if (!this.adj[v] != undefined) {
        console.log('visted:', v);
      }
      for (let vertex of this.adj[v]) {
        if (!this.marked[vertex]) {
          this.marked[vertex] = true;
          queue.push(vertex);
        }
      }
    }
  }
}

let names = new Graph(5);
names.addEdge(0, 1);
names.addEdge(0, 2);
names.addEdge(1, 3);
names.addEdge(2, 4);
// names.dfs(0);
names.bfs(0);
------------- The End -------------
显示评论