JavaScript数据结构-17.图结构

  1 <!DOCTYPE html>
  2 <html>
  3     <head>
  4         <meta charset="UTF-8">
  5         <title>图的实现</title>
  6     </head>
  7     <body>        
  8       <script type="text/javascript">
  9     
 10         function Graph(v){
 11             this.vertices = v;
 12             this.edges = 0;
 13             this.adj = [];
 14             for(var i = 0; i<this.vertices;i++){
 15                 this.adj[i] = [];
 16                 // 原书有这句，多余  没什么用。
 17 //                this.adj[i].push("");
 18             }
 19             this.addEdge = addEdge;
 20             this.toString = toString;
 21             this.showGraph = showGraph;
 22             
 23             //记录已经访问过的顶点
 24             this.marked = [];
 25             for(var i = 0;i < this.vertices;i++){
 26                 this.marked[i] = false;
 27             }
 28             this.dfs = dfs;
 29             this.bfs = bfs;        
 30         }
 31         function addEdge(v,w){
 32             this.adj[v].push(w);
 33             this.adj[w].push(v);
 34             this.edges++;
 35         }
 36         
 37         function showGraph(){
 38             for(var i =0;i < this.vertices;i++){
 39                 for(var j = 0;j < this.vertices;j++){
 40                     if(this.adj[i][j] != undefined){
 41                         console.log(i+"->"+this.adj[i][j])
 42                     }
 43                 }
 44             }
 45         }
 46         //深度优先搜索
 47         function dfs(v){
 48             this.marked[v] = true;
 49             //输出一下 
 50             if(this.adj[v] != undefined){
 51                 console.log("已访问 ："+v);
 52                 console.log(this.marked,"adj")
 53             }
 54             //原书写法   这里用for in 得到的只是顶点的索引,并且会把非整数索引也循环，这里有坑
 55             /*
 56             for (var w in this.adj[v] ){            
 57                 if(!this.marked[this.adj[v][w]]){
 58                     this.dfs(this.adj[v][w]);
 59                 }
 60             }
 61             */
 62 
 63            for(var i = 0;i<this.adj[v].length;i++){
 64                    var w = this.adj[v][i];
 65                    if(!this.marked[w]){
 66                     console.log("123456")
 67                     this.dfs(w);
 68                   }
 69             }
 70         }                
 71         //广度优先
 72         function bfs(s){
 73             var queue = [];
 74             this.marked[s] = true;
 75             queue.push(s);
 76             while(queue.length > 0){
 77                 var v = queue.shift();
 78                 if(v != undefined){
 79                     console.log("已访问 ："+v);
 80                 }
 81                 for(var k in this.adj[v]){            
 82                     var w = this.adj[v][k];
 83                     if(!this.marked[w]){
 84                         this.marked[w] = true;
 85                         queue.push(w);
 86                     }
 87                 }
 88             }        
 89         }
 90         
 91         var obj = new Graph(5);
 92         obj.addEdge(0,1);
 93         obj.addEdge(0,2);
 94         obj.addEdge(1,3);
 95         obj.addEdge(2,4);
 96         obj.showGraph();
 97         //深度优先搜索
 98 //        obj.dfs(0);
 99         console.log("------------")
100         obj.bfs(0);
101         
102         
103         //由于标记数组定义在对象里  所以在这儿不能同时调用深度优先和广度优先。。
104      </script>
105     </body>
106 </html>