用js来实现那些数据结构15（图01）

function Map () {
    //......其他各种方法，详见前面的字典部分
}

//代码很简单，但是还是要解释一下。
function Graph() {
    //vertices数组存放我们图中所有的顶点
    var vertices = [];
    //adjList存放我们的邻接表。adjList会使用顶点来作为键，邻接顶点列表作为值
    var adjList = new Map();
    //添加顶点的方法。
    this.addVertices = function (v) {
        //存放到顶点数组中
        vertices.push(v);
        //生成一个还没有邻接顶点列表的Map，因为这时我们已经有顶点了，所以要生成以待使用
        adjList.set(v,[]);
    }
    //这里有个小细节我们需要注意，哦对，这是为图添加边的方法。要注意的是，实际上，在代码中，我们是没有一个东西（变量或者其他什么）来代表边的。
    //我们为两个顶点之间添加一个边实际上只是为两个顶点的邻接表中加入彼此。这样就代表了这两个顶点是相邻的。
    this.addEdge = function (v,w) {
        //而这里我们所实现的图是无向图，所以需要给两个顶点所对应的邻接表加入彼此。
        //而如果是有向图的话，只需要根据方向添加一个就可以了。
        adjList.get(v).push(w);
        adjList.get(w).push(v);
    }

    // 为了方便观察，我们再实现一个toString方法
    // 没啥好说的，双重循环遍历两个数组。
    this.toString = function () {
        var s = "";

        for(var i = 0;i < vertices.length;i++) {
            s += vertices[i] + "->";
            var neighbors = adjList.get(vertices[i]);
            for(var j = 0; j < neighbors.length; j++) {
                s += neighbors[j] + '  ';
            }
            s += '\n';
        }
        return s;
    }
}

//我们来试一下
var graph = new Graph();

var verticesArray = ['A','B','C','D','E','F','G','H','I'];

for(var i = 0; i < verticesArray.length; i++) {
    graph.addVertices(verticesArray[i]);
}

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');


console.log(graph.toString());
/*
A->B  C  D  
B->A  E  F  
C->A  D  G  
D->A  C  G  H  
E->B  I  
F->B  
G->C  D  
H->D  
I->E  
*/