JS数据结构-图

这一篇介绍图这一数据结构，之后也会放上leetcode的题。

基础代码实现

基础类的定义

顶点类的定义

1
2
3
function Vertex(label) {
    this.label = label;
}

图类的定义

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
function Graph(v) {
    //顶点个数
    this.number_vertice = v;
    //边的条数
    this.number_edge = 0;
    //
    this.edgeTo = [];
    //用于存储图的邻接矩阵
    this.adj = [];
    //初始化邻接矩阵
    for (var i = 0; i < this.number_vertice; i++) {
        this.adj[i] = [];
        this.adj[i].push("");
    }
    //用于在搜索算法中判定是否已经被读过
    this.marked = [];
    for (var i = 0; i < this.number_vertice; i++) {
        this.marked[i] = false;
    }
    //构建边
    this.addEdge = addEdge;
    //将图以邻接矩阵的形式进行输出
    this.showGraph = showGraph;
    //深度优先搜索
    this.depthFirstSearch = depthFirstSearch;
    //广度优先搜索
    this.breadthFirstSearch = breadthFirstSearch;
}

方法的实现

增加边

1
2
3
4
5
function addEdge(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.number_edge++;
}

将图以邻接矩阵的形式进行输出

1
2
3
4
5
6
7
8
9
10
11
12
function showGraph() {
    var str = "";
    for (var i = 0; i < this.number_vertice; i++) {
        str = i + "->";
        for (var j = 0; j < this.number_vertice; j++) {
            if (this.adj[i][j] != undefined) {
                str += this.adj[i][j] + " ";
            }
        }
        debug(str);
    }
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
function depthFirstSearch(v) {
    this.marked[v] = true;
    if (this.adj[v] != undefined) {
        debug("Vertex Visted:" + v);
        for (var i = 0; i < this.adj[v].length; i++) {
            if (!this.marked[this.adj[v][i]]) {
                this.depthFirstSearch(this.adj[v][i]);
            }
        }
    }
}

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function breadthFirstSearch(vertex) {
    var queue = [];
    this.marked[vertex] = true;
    //将参数推到队列末尾
    queue.push(vertex);
    while (queue.length > 0) {
        //将队列首元素移除
        var top = queue.shift();
        if (this.adj[top] != undefined) {
            debug("Vertex Visited:" + top);
            for (var i = 0; i < this.adj[top].length; i++) {
                if (!this.marked[this.adj[top][i]]) {
                    this.marked[this.adj[top][i]] = true;
                    queue.push(this.adj[top][i]);
                }
            }
        }
    }
}