JavaScript数据结构-18.图结构广度优先和最短路径

  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             //保存从一个顶点到下一个顶点的所有边
 32             this.edgeTo = [];
 33             
 34             this.pathTo = pathTo;
 35             this.hasPathTo = hasPathTo;
 36             
 37         }
 38         function addEdge(v,w){
 39             this.adj[v].push(w);
 40             this.adj[w].push(v);
 41             this.edges++;
 42         }
 43         
 44         function showGraph(){
 45             for(var i =0;i < this.vertices;i++){
 46                 for(var j = 0;j < this.vertices;j++){
 47                     if(this.adj[i][j] != undefined){
 48                         console.log(i+"->"+this.adj[i][j])
 49                     }
 50                 }
 51             }
 52         }
 53             
 54         //广度优先
 55         function bfs(s){
 56             var queue = [];
 57             this.marked[s] = true;
 58             queue.push(s);
 59             while(queue.length > 0){
 60                 var v = queue.shift();
 61                 if(v != undefined){
 62                     console.log("已访问 ："+v);
 63                 }
 64                 for(var k in this.adj[v]){            
 65                     var w = this.adj[v][k];
 66                     if(!this.marked[w]){
 67                         this.edgeTo[w] = v;
 68                         this.marked[w] = true;
 69                         queue.push(w);
 70                     }
 71                 }
 72             }        
 73         }
 74         
 75         function pathTo(v){
 76             var source = 0;
 77             if(!this.hasPathTo(v)){
 78                 return undefined;
 79             }
 80             var path = [];
 81             for(var i = v;i != source;i=this.edgeTo[i]){
 82                 path.push(i);
 83             }
 84             path.push(source);
 85             return path;
 86         }
 87         function hasPathTo(v){
 88             return this.marked[v];
 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         console.log("------------")
 99         obj.bfs(0);
100         var paths = obj.pathTo(3);
101         console.log(paths,"123");
102         while(paths.length >0){
103             if(paths.length >1){
104                 console.log(paths.pop() + "-");
105             }else{
106                 console.log(paths.pop());
107             }
108         }
109       //打印结果 0-2-4  表示在这个图中 顶点0到顶点4的距离为2;
110      </script>
111     </body>
112 </html>