5-2 图的BFS的JS实现
LinkedList实现方式：
因为js没有LinkedList，以下是自己实现的LinkedList：
function LinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
this.add = function(element) {
var node = new Node(element),current;
if (head==null) {
head = node;
} else {
current = head;
while(current.next) {
current = current.next;
}
current.next = node;
}
length++;
}
this.set = function(index, element) {
var a = this.get(index);
a = element;
}
// 删除最顶端元素
this.remove = function() {
if (this.isEmpty()) {
return undefined;
}
var h = head.element;
head = head.next;
length --;
return h;
}
this.isEmpty = function() {
return length == 0;
}
this.get = function(index) {
var num = 0, current;
if (index < 0) throw new RangeError("Index out of range");
current = head;
while(num++ < index) {
current = current.next;
}
var a = current.element;
return a;
}
}
module.exports = LinkedList;以下是自己实现的队列queue类：
function Queue() {
var queue = {};
var count = 0;
var lowCount = 0;
// 入队
this.add = function(value) {
queue[count++] = value;
}
// 出队
this.remove = function() {
if (this.isEmpty()) {
return undefined;
}
var result = queue[lowCount];
delete queue[lowCount];
lowCount++;
return result;
}
this.isEmpty = function() {
return this.size() == 0;
}
this.peek = function() {
if (this.isEmpty()) {
return null;
}
return queue[lowCount];
}
this.clear = function() {
count = 0;
lowCount = 0;
queue = {};
}
this.size = function() {
return count - lowCount;
}
}
module.exports = Queue;以下是图的广度优先遍历方式：
const LinkedList = require("../util/LinkedList");
const Queue = require("../util/Queue");
const Graph = require("../graph/Graph");
function GraphBFS($g) {
var G = $g, visited = new Array(G.V()).fill(false), queue = new LinkedList(), order = [];
var bfs = function ($v) {
visited[$v] = true;
queue.add($v);
while (!queue.isEmpty()) {
var v = queue.remove();
order.push(v);
for (var w of G.adj(v)) {
if (!visited[w]) {
queue.add(w);
visited[w] = true;
}
}
}
}
for (var v = 0; v < G.V(); v++) {
if (!visited[v]) {
bfs(v);
}
}
this.order=function () {
return order;
}
}
var g = new Graph('data/图的BFS实现/g.txt');
var graphBFS = new GraphBFS(g);
console.log('图的广度优先遍历结果：', graphBFS.order())上面GraphBFS中的queue不管是实现的Queue还是LinkedList都能实现图的广度优先遍历。从代码上看Queue的性能是优于LinkedList的，不知道老师为何在实现这个queue采用的是链表呢？还是因为JAVA中关于LinkedList是跟我这里是有本质区别的？
正在回答
1回答
Java 中 Queue 是一个接口（而不是一个具体的数据结构。）开发者可以选择用链表实例化这个接口，也可以选择用动态数组实例化这个接口。对于小数据量，基本没有区别；对于大数据量，确实链表的性能是差的。
===========
但是我简单看了一下你的代码，你所看到的性能差距，大概率不是这两种数据结构在大规模数据下产生的性能差距。
对于 js，你这样手动写一个链表，效率肯定低于你手写的这个 queue。这是因为你手写的这个queue，本质是对 js 数组的一次在封装，背后的数据结构，本质使用的是数组；而你手写的这个链表，是真正的没有使用 js 的任何原生数据结构，从底层搭建了一个数据结构的增删改查和所有的内存的声明和销毁。
对于大多数脚本语言，前者一定远远快于后者。这是因为前者通常都是被类似 C/C++ 这样的语言在底层被实现优化出来的，而后者是你在上层实现出来的，运行时再被解释器解析，效率远远低于前者，即使是同样的复杂度。
这就是为什么，对于算法和数据结构的底层性能的考察，我是不建议使用脚本语言的。（当然，学习逻辑是没有问题的）。因为使用脚本语言，性能的优劣很有可能关键因素并非是算法，而是具体的实现。同样的算法思路，在脚本语言上，一个“好的实现”，很有可能是比“差的实现”快几十倍甚至上百倍的，而在大多数编译型语言中，通常是不会有这么大的性能差距的。而所谓的“好的实现”，在通常情况下，更多的是是否足够了解这个脚本语言提供的标准库，并且充分利用这个标准库。
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
