关于本章邻接表的JS实现和一些相关的疑问

来源:2-6 邻接表的实现

qq_crusader_1

2022-05-11

还是根据老师的视频和JAVA的实现改写的JS,代码如下:
首先,因为JS中没有自带的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.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;
    }
    this.contains = function(element) {
        var current = head;
        while(current) {
            if (current.element == element) return true;
            current = current.next;
        }
        return false;
    }
    this.length = function() {
        return length;
    }
    this.elements = function() {
        var current = head;
        var tmpArr = [];
        while(current) { 
            console.log('elements',current)
            tmpArr.push(current.element);
            current = current.next;
        }
        return tmpArr;
    }
}

module.exports = LinkedList;

然后是AdjList实现:

const LinkedList = require('../util/LinkedList');
const fs = require('fs');
const path = require('path');
var _privateMap = new WeakMap();
var _keys = {'V': new String(), 'E': new String(), 'ADJ': new String()}
function AdjList(filename) {
    var V, E, adj = new LinkedList(), index = 0;
    var file = fs.readFileSync(filename, 'utf8');
    var vertices = file.split(/\s\n?/g)
    V = +vertices[index++];
    _privateMap.set(_keys.V,    { writable: true, value: 0 })
    _privateMap.set(_keys.E,    { writable: true, value: 0 })
    _privateMap.set(_keys.ADJ,  { writable: true, value: 0 })
    adj = [];
	for (let i = 0; i < V; i++) {
1)  	adj[i] = new LinkedList();
    }
    E = vertices[index++];
    this.$privateSet(_privateMap, _keys.V, V);
    this.$privateSet(_privateMap, _keys.E, E);
    for (var i = 0; i < E; i++) {
        let a = +vertices[index++];
        this.validateVertex(a);
        let b = +vertices[index++];
        this.validateVertex(b);
2)      adj[a].add(b);
3)      adj[b].add(a);
    }
    this.$privateSet(_privateMap, _keys.ADJ, adj);
    console.log('adj', adj)
    return this;
}
AdjList.prototype = {
    V: function(){
        return this.$privateGet(_privateMap, _keys['V'])
    },
    E: function() {
        return this.$privateGet(_privateMap, _keys['E'])
    },
    elements: function() {
        var adj = this.$privateGet(_privateMap, _keys.ADJ);
        var V = this.$privateGet(_privateMap, _keys.V);
        var str = ``;
        for (var i = 0; i < V; i++) {
            str += `第${i}个点的邻边是:`
4)          for(var j of adj[i].elements()) {
5)                str += `${j}、`
6)          }
        }
        str.substring(0, str.length - 2) + '\n'
        return str;
    },
    hasEdge: function(v, w) {
        this.validateVertex(v);
        this.validateVertex(w);
        var adj = this.$privateGet(_privateMap, _keys.ADJ);
7)      return adj[v].contains(w);
    },
    validateVertex(v) {
        var V = this.$privateGet(_privateMap, _keys['V']);
        if (v < 0 || v >= V) throw new RangeError("vertex " + v + " is invalid");
    },
    degree: function(v) {
        var adj = this.$privateGet(_privateMap, _keys.ADJ);
8)      return adj[v].length();
    },
    adj: function(v) {
        this.validateVertex(v);
        var adj = this.$privateGet(_privateMap, _keys.ADJ);
9)      return adj[v].elements();
    },
    $privateSet: function($map, $key, $value) {
        var descriptor = $map.get($key);
        console.log('$privateSet', $value)
        descriptor.value = $value;
    },
    $privateGet: function($map, $key) {
        return $map.get($key).value;
    }
}
var adjList = new AdjList(`${__dirname}/g.txt`)

console.log(`图有${adjList.V()}个顶点,有${adjList.E()}条边, 顶点1有${adjList.degree(0)}条邻边,它的邻边是${adjList.adj(0)},
顶点0和顶点5${adjList.hasEdge(0, 5) ? '存在' : '不存在'}邻边,${adjList.elements()}`)

但是发现我这个LinkedList实现其中的contains时间复杂度不是最优的,并且下标访问元素的时间复杂度也不低,所以暂时舍弃使用这个LinkedList,转而改为js中的Set这样更简单直接,所以针对上述代码改动如下:
1)处改为:

adj[i]=new Set()

2)处改为

adj[a].add(b);
adj[b].add(a);

4)-6)处改为:

for (var j of adj[i]) {
	str += `${j}、`
}

7)改为

return adj[v].has(w);

8)改为

return adj[v].size;

9)改为

return [...adj[v]];

目前还不清楚如何实现LinkedList.contains使它的时间复杂度为O(1),还有也无法自己实现LinkedList通过使用下标访问元素的时间复杂度为O(1)?看Set的这些API跟JAVA中的LinkedList很像,也不清楚Set是否是链表的一种实现?

写回答

1回答

liuyubobobo

2022-05-12

LinkedList 无法做到 O(1),LinkedList 就是 O(n) 的。


如果想要高效实现 contains 和 erase 操作,需要使用 Set。通常语言标准库中的 Set,使用的是红黑树或者哈希表,期时间复杂度可以达到 O(logn) 或者 O(1)。课程在下一小节也将使用 Set 来实现邻接表。


继续加油!:)

0
2
qq_crusader_1
非常感谢!
2022-06-23
共2条回复

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1599 学习 · 330 问题

查看课程