图结构

什么是图？

图结构是一种与树结构有些相似的数据结构，图论是数学的一个分支，并且在数学的概念上，树是图的一种，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法，主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系。

图的特点：

一组顶点：通常用V（Vertex）表示顶点的集合

一组边：通常用E（Edge）表示边的集合

　　边是顶点和顶点之间的连线

　　边可以是有向的，也可以是无向的，A----B表示无向的，A--->表示有向的

 图的表示

邻接矩阵：让每个节点和一个整数相关联，该整数作为数组的下标值，用一个二维数组来表示顶点之间的连接

邻接表：邻接表由图中每个顶点以及顶点相邻的顶点列表组成，这个列表有很多中方式来存储：数组/链表/字典（哈希表）都可以

 封装图结构

添加方法

    function Graph() {
        this.vertexes = []  //顶点
        this.edges = new Dictionary()   //边
        //添加顶点的方法
        Graph.prototype.addVertex = function (v) {
            this.vertexes.push(v)
            this.edges.set(v, [])
        }
        // 添加边的方法
        Graph.prototype.addEdge = function (v1, v2) {
            this.edges.get(v1).push(v2)
            this.edges.get(v2).push(v1)
        }
        Graph.prototype.toString = function () {
            var result = ''
            for (var i = 0; i < this.vertexes.length; i++) {
                result += this.vertexes[i] + '->'
                var vedges = this.edges.get(this.vertexes[i])
                for(var j=0;j < vedges.length; j++) {
                    result += vedges[j]+ ' '
                }
            result += "\n"
            }
            return result
        }
    }

测试：

 var g = new Graph()
    //添加顶点
    var vert = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
    for (var i = 0; i < vert.length; i++) {
        g.addVertex(vert[i])
    }
    //添加边
    g.addEdge('a', 'b')
    g.addEdge('a', 'c')
    g.addEdge('a', 'd')
    g.addEdge('c', 'd')
    g.addEdge('c', 'g')
    g.addEdge('d', 'g')
    g.addEdge('d', 'h')
    g.addEdge('b', 'e')
    g.addEdge('b', 'f')
    g.addEdge('e', 'i')
    alert(g.toString())

图的遍历

广度优先搜索（Breadth-First Search，BFS），基于队列，入队列的顶点先被探索

深度优先搜索（Deapth-First Search，DFS），基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问

两种遍历算法，都需要明确指明第一个被访问的顶点

 广度优先搜索的实现