图的连接表构建，广度遍历，深度遍历，无权最短路径

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
function Graph() {              // 连接表表示图结构
    this.vertices = [];         // 顶点
    this.edges = 0;             // 边
    this.vertexEdges = {};      // 顶点到达的边
    this.marked = {};
    this.dist = [];      // 路径长度
    this.path = [];      // 父节点
}
Graph.prototype = {
    addVertex: function(v) {
        this.vertices.push(v);
        this.vertexEdges[v] = [];
        this.marked[v] = false;
        this.dist[v] = -1;
        this.path[v] = -1;
    },
    addEdge: function(v, w) {
        this.vertexEdges[v].push(w);
        this.vertexEdges[w].push(v);
        this.edges++;
    },
    show: function() {
        for (var i = 0, len = this.vertices.length; i < len; i++) {
            var v  = this.vertices[i];
            var ves = this.vertexEdges[v];
            var str = v + ' -> '; 
            for (var j = 0, subl = ves.length; j < subl; j++) {
                str += ' ' + ves[j] + ' ';
            }
            console.log(str + '\n');
        }
    },
    bfsTraverse: function(v) {
        this.marked[v] = true;
        
        var queue = [];
        queue.push( v );
        while (queue.length > 0) {
            var v = queue.shift();
            var ves = this.vertexEdges[v];
            console.log(v);
            for (var i = 0, len = ves.length; i < len; i++) {
                if ( !this.marked[ ves[i] ] ) {
                    this.marked[ ves[i] ] = true;
                    queue.push(ves[i]);
                }
            }
        }
    },
    dfsTraverse: function(v) {
        this.marked[v] = true;
        var ves = this.vertexEdges[v];
        console.log(v);
        for (var i = 0, len = ves.length; i < len; i++) {
            if ( !this.marked[ ves[i] ] ) {
                this.marked[ ves[i] ] = true;
                this.dfsTraverse(ves[i])
            }
        }
    },
    bfsFindPath: function(v) {      // 单源无权图最短路径
        this.dist[v] = 0;
        var queue = [];
        queue.push( v );
        while (queue.length > 0) {
            var v = queue.shift();
            var ves = this.vertexEdges[v];
            for (var i = 0, len = ves.length; i < len; i++) {
                if ( this.dist[ ves[i] ] == -1 ) {
                    this.dist[ ves[i] ] = this.dist[ v ] + 1;
                    this.path[ ves[i] ] = v;
                    queue.push(ves[i]);
                }
            }
        }
        console.log(this.dist, this.path)
    },
}
var graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(function(v) {
    graph.addVertex(v)
});
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('E', 'I')
// graph.show();
// graph.bfsTraverse('H')
// graph.dfsTraverse('H')
graph.bfsFindPath('H')