数据结构 --图

图

特点

• 一组顶点: 通常用V(Vertex)表示顶点的集合

• 一组边: 通常用E(Edge)表示边的集合

  • 边是顶点和顶点之间的连线
  • 可有向可无向

• 相邻节点:一条边连接在一起的顶点

• 度: 指和该顶点相关联的边数

• 路径:

  • 简单路径:不包含重复的节点
  • 回路:第一个顶点和最后一个顶点相同

• 无向图 有向图 无权图

• 有权图:带权图表示边有一定的权重

• 两种表示方式:邻接矩阵 邻接表

• 邻接矩阵:让每个节点和一个整数相关联 该整数作为数组的下标值

  • 二维数组表示顶点之间连接
  • 0表示没有连线 1表示有连线
  • 无向图 邻接矩阵是对称的
  • 问题:如果图是稀疏图 矩阵中有大量的0 浪费存储空间

• 邻接表:每个顶点以及和顶点相邻的顶点列表组成

• 图的遍历:

  • 广度优先搜索(BFS) Breadth-First Search :基于队列 入队列的定点先被探索
  • 深度优先搜索(DFS) Depth-First Search :基于栈或者使用递归,通过将顶点存入栈中,顶点是沿着路径被探索的,存在新的相邻顶点就去访问
  • 都需要明确指出第一个被访问的顶点
  • 三种了颜色记录状态
    • 白色:表示顶点没有被访问
    • 灰色:表示被访问过但是没有被探索过
    • 黑色:被访问过并且被完全探索过

• 代码实现

function Graph() {
           //属性：顶点（数组） /  边（字典）
           this.vertexes = []  //顶点
           this.edges = new Dictionay()

           //方法
           //添加方法
           //1.添加顶点的方法
           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)
           }
           //实现toString方法
           Graph.prototype.toString =function(){           //这里是Object中有toString方法  Graph.prototype.__proto__==Object.prototype
               //1 定义字符串，保存最终的结果
               let resultString=""
               //2 遍历所有的顶点，以及顶点对应的边
               for(let i =0;i<this.vertexes.length;i++ ){
                  resultString += this.vertexes[i]+ "->"
                  let vEdges=this.edges.get(this.vertexes[i])
                  for(let j=0;j<vEdges.length;j++){
                      resultString += vEdges[j] + " "
                  }
                  resultString +='\n'
               }
               return resultString
           }
           //初始化状态颜色
           Graph.prototype.initializeColor=function(){
               var colors= []
               for(var i=0;i<this.vertexes.length;i++){
                   colors[this.vertexes[i]]="white"
               }
               return colors
           }
           //实现广度优先搜索(BFS)
           Graph.prototype.bfs=function(initv,handler){
               //1.初始化颜色
               let colors= this.initializeColor()
               //2.创建队列
               let queue = new Queue()
               //3.顶点加入到队列中
               queue.enqueue(initv)
               //4.循环从队列中取出元素
               while(!queue.isEmpty()){
                   //4.1从队列中取出一个顶点
                   let v=queue.dequeue()
                   //4.2获取和顶点相邻的其他顶点
                   let vList=this.edges.get(v)

                   //4.3将v的颜色设置成灰色
                   colors[v]='gray'
                   //4.4遍历所有的顶点 ，加入到队列中
                   for(let i=0;i<vList.length;i++){
                       let e = vList[i]
                       if(colors[e]=='white'){
                           colors[e]='gray'
                           queue.enqueue(e)
                       }
                   }
                   //4.5访问顶点
                   handler(v)

                   //4.6将顶点设置为黑色
                   colors[v]='black'                
               }
           }
           //深度优先遍历（DFS）
           Graph.prototype.dfs=function(init,handler){
               //1.初始化颜色
               var colors=this.initializeColor()
               //2.从某个顶点开始依次递归访问
               this.dfsVisit(init,colors,handler)
           }
           Graph.prototype.dfsVisit=function(v,colors,handler){
               //1.颜色设置为灰色
               colors[v]='gray'
               //2.处理v顶点
               handler(v)
               //3.访问v相连其他顶点
               var vList=this.edges.get(v)
               for(var i =0; i<vList.length;i++){
                   var e = vList[i]
                   if(colors[e]=='white'){
                       this.dfsVisit(e,colors,handler)
                   }
               }
               //4.将v设置为黑色
               colors[v]='black'

           }
       }